Полином Ладьи

	а	б	с	д	и	ж	г	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	с	д	и	ж	г	час

Одно из возможных расстановок ладей на шахматной доске 8 × 8, где никакие две фигуры не находятся в одном ряду или столбце.

В комбинаторной математике ладейный полином — это производящий полином числа способов разместить неатакующие ладьи на доске , похожей на шахматную доску ; то есть никакие две ладьи не могут находиться в одной строке или столбце. Доска — это любое подмножество квадратов прямоугольной доски с m строками и n столбцами; мы думаем об этом как о полях, на которые можно поставить ладью. Доска представляет собой обычную шахматную доску, если разрешены все клетки и m = n = 8, и шахматную доску любого размера, если разрешены все клетки и m = n . Коэффициент ​ ​ х  ^к в ладейном полиноме R _B ( x ) — это количество способов , которыми k ладей, ни одна из которых не атакует другую, можно расположить в клетках B . Ладьи расположены таким образом, чтобы в одном ряду или столбце не было пары ладей. В этом смысле расстановка — это расположение ладей на статичной неподвижной доске; расположение не изменится, если доску вращать или отражать, сохраняя при этом квадраты неподвижными. Полином также остается неизменным, если меняются местами строки или столбцы.

Термин «ладейный полином» был придуман Джоном Риорданом . Несмотря на происхождение названия от шахмат , толчком к изучению ладейных полиномов является их связь с подсчетом перестановок (или частичных перестановок ) с ограниченными позициями. Доска B , являющаяся подмножеством шахматной доски n × n, соответствует перестановкам n объектов, которые мы можем принять за числа 1, 2, ..., n , так что число a _j в j -й позиции в перестановке должен быть номер столбца разрешенного квадрата в строке j строки B . Известные примеры включают количество способов разместить n неатакующих ладей:

• целая шахматная доска размера n × n , представляющая собой элементарную комбинаторную задачу;
• та же доска с запрещенными диагональными клетками; это проблема расстройства или «проверки шляпы» (это частный случай проблемы встреч );
• та же доска без клеток по диагонали и непосредственно над ней (и без нижнего левого квадрата), что существенно для решения задачи о менажах .

Интерес к ладейным расстановкам возникает в чистой и прикладной комбинаторике, теории групп , теории чисел и статистической физике . Особая ценность ладейных полиномов обусловлена ​​полезностью метода производящей функции, а также тем фактом, что нули ладейного полинома доски предоставляют ценную информацию о ее коэффициентах, то есть о количестве неатакующих размещений k ладей. .

Определение

Ладейный полином R _B ( x ) доски B является производящей функцией количества расстановок неатакующих ладей:

$R_{B}(x)=\sum _{k=0}^{\min {(m,n)}}r_{k}(B)x^{k},$

где $r_{k}(B)$ количество способов разместить k неатакующих ладей на доске B. — Существует максимальное количество неатакующих ладей, которые может держать доска; действительно, ладей не может быть больше, чем количество строк или количество столбцов на доске (отсюда и предел $\min(m,n)$).

Полные доски

Для прямоугольных m × n досок B _{m , n} пишем R _m,n := R _{B m , n} , а если m = n , R _n := R _{m , n} .

Первые несколько ладейных полиномов на досках размером n × n :

${\begin{aligned}R_{1}(x)&=x+1\\R_{2}(x)&=2x^{2}+4x+1\\R_{3}(x)&=6x^{3}+18x^{2}+9x+1\\R_{4}(x)&=24x^{4}+96x^{3}+72x^{2}+16x+1.\end{aligned}}$

На словах это означает, что на доске 1×1 1 ладью можно расставить 1 способом, а ноль ладей можно расставить также 1 способом (пустая доска); на полной доске 2×2 2 ладьи можно расставить 2 способами (по диагоналям), 1 ладью — 4 способами, а нулевые ладьи — 1 способом; и так далее для досок большего размера.

Ладейный полином прямоугольной шахматной доски тесно связан с обобщенным полиномом Лагерра L _n ^а ( x ) по тождеству

$R_{m,n}(x)=n!x^{n}L_{n}^{(m-n)}(-x^{-1}).$

Соответствующие полиномы

Ладейный полином — это частный случай одного из видов совпадающего полинома , который является производящей функцией количества k -ребер паросочетаний в графе.

Ладейный полином , _{Rm n (} x ) полному двудольному графу   Km _{, . n} соответствует Ладейный полином общей доски B ⊆ B _{m , n} соответствует двудольному графу с левыми вершинами v ₁ , v ₂ , ..., v _m и правыми вершинами w ₁ , w ₂ , ..., w _n и ребро v _i w _j всякий раз, когда квадрат ( i , j ) разрешен, т. е. принадлежит B . Таким образом, теория ладейных полиномов в некотором смысле содержится в теории совмещения многочленов.

Выведем важный факт о коэффициентах r _k , который мы напоминаем, учитывая количество неатакующих размещений k ладей в B : эти числа унимодальны , т. е. они возрастают до максимума, а затем уменьшаются. Это следует (стандартным рассуждением) из теоремы Хейльмана и Либа о нулях согласующего многочлена (отличного от того, который соответствует ладейному многочлену, но эквивалентного ему при замене переменных), что означает, что все нули ладейного многочлена являются отрицательными действительными числами.

Подключение к матричным перманентам

Для неполных квадратов n × n досок (т. е. ладьями нельзя играть на каком-то произвольном подмножестве клеток доски) вычисление количества способов разместить n ладей на доске эквивалентно вычислению перманента матрицы 0–1. .

Полные прямоугольные доски

Проблемы с ладьями

	а	б	с	д	и	ж	г	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	с	д	и	ж	г	час

Рис. 1. Максимальное количество неатакующих ладей на шахматной доске 8×8 равно 8. Ладья + точки обозначают количество полей на ранге, доступных каждой ладье после расстановки ладей на нижних горизонтах.

Предшественником ладейного полинома является классическая «Задача восьми ладей» Х. Э. Дюдени. в которой он показывает, что максимальное количество неатакующих ладей на шахматной доске равно восьми, располагая их на одной из главных диагоналей (рис. 1). Задается вопрос: «Сколькими способами можно расставить восемь ладей на шахматной доске 8×8 так, чтобы ни одна из них не атаковала другую?» Ответ такой: «Очевидно, что в каждой строке и каждом столбце должна быть ладья. Начиная с нижнего ряда, ясно, что первую ладью можно поставить на любое из восьми различных полей (рис. 1). Где бы она ни находилась размещены, есть возможность выбрать семь полей для второй ладьи во втором ряду. Затем есть шесть полей, из которых можно выбрать третий ряд, пять в четвертом и так далее. Следовательно, количество различных способов должно быть 8 ×. 7 × 6 × 5 × 4 × 3 × 2 × 1 = 40 320 дюймов (то есть 8!, где «!» — факториал ) .

Тот же результат можно получить несколько другим способом. Присвоим каждой ладье позиционный номер, соответствующий номеру ее ранга, и присвоим ей имя, соответствующее названию ее вертикали. Таким образом, ладья a1 имеет позицию 1 и имя «a», ладья b2 имеет позицию 2 и имя «b» и т. д. Затем упорядочим ладьи в упорядоченный список ( последовательность ) по их позициям. Диаграмма на рис. 1 тогда преобразуется в последовательность (a,b,c,d,e,f,g,h). Размещение любой ладьи на другой вертикали означало бы перемещение ладьи, которая до сих пор занимала вторую вертикали, на вертикали, освобожденные первой ладьей. Например, если ладья a1 перенесена на линию «b», ладья b2 должна быть перемещена на линию «a», и теперь они станут ладьей b1 и ладьей a2. Новая последовательность будет иметь вид (b,a,c,d,e,f,g,h). В комбинаторике эта операция называется перестановкой , а последовательности, полученные в результате перестановки, являются перестановками данной последовательности. Общее количество перестановок, содержащих 8 элементов из последовательности из 8 элементов, равно 8! ( факториал 8).

Чтобы оценить эффект наложенного ограничения «ладьи не должны атаковать друг друга», рассмотрим задачу без такого ограничения. Сколькими способами можно расставить восемь ладей на шахматной доске 8×8? Это будет общее количество комбинаций из 8 ладей на 64 полях:

${64 \choose 8}={\frac {64!}{8!(64-8)!}}=4,426,165,368.$

Таким образом, ограничение «ладьи не должны атаковать друг друга» уменьшает общее количество допустимых позиций от комбинаций до перестановок, что составляет примерно 109 776 раз.

Ряд задач из разных сфер человеческой деятельности можно свести к задаче о ладьях, придав им «ладейную формулировку». Например: компания должна нанять n работников на n различных работах, и каждая работа должна выполняться только одним работником. Сколькими способами можно осуществить это назначение?

Расположим рабочих по рядам шахматной доски n × n , а рабочие места — по рядам. Если рабочий i назначается на работу j , ладья ставится на поле, где горизонталь i пересекает вертикаль j . Поскольку каждую работу выполняет только один рабочий и каждый рабочий назначается только на одну работу, то во всех вертикалях и шеренгах будет только одна ладья в результате расстановки на доске n ладей, т. е. ладьи не атакуют друг друга.

Ладейный полином как обобщение проблемы ладей

Классическая задача о ладьях сразу дает значение r ₈ , коэффициента перед членом высшего порядка ладейного полинома. Действительно, его результат состоит в том, что 8 неатакующих ладей можно расставить на шахматной доске 8 × 8 при r ₈ = 8! = 40320 способов.

Обобщим эту проблему, рассмотрев доску размером m × n , то есть доску с m рангами (строками) и n файлами (столбцами). Возникает проблема: сколькими способами можно расставить k ладей на доске m × n так, чтобы они не атаковали друг друга?

Ясно, что для того, чтобы задача была разрешима, k должно быть меньше или равно меньшему из чисел m и n ; в противном случае нельзя избежать размещения пары ладей на вертикали или вертикали. Пусть это условие будет выполнено. Тогда расстановку ладей можно провести в два приема. Сначала выберите набор из k рядов, на которых разместите ладьи. Поскольку число рангов равно m , из которых k , этот выбор можно сделать в необходимо выбрать ${\binom {m}{k}}$ пути. Аналогичным образом можно выбрать набор из k вертикалей, на которых будут расставляться ладьи. ${\binom {n}{k}}$ пути. Поскольку выбор файлов не зависит от выбора рангов, согласно правилу продуктов существуют ${\binom {m}{k}}{\binom {n}{k}}$ способы выбора поля, на которое можно поставить ладью.

Однако задача еще не решена, поскольку k рангов и k файлов пересекаются в k ² квадраты. Удалив неиспользуемые ряды и файлы и уплотнив оставшиеся ряды и файлы вместе, можно получить новую доску из k рангов и k файлов. Уже было показано, что на такой доске k ладей можно расставить по k ! способами (чтобы они не нападали друг на друга). Следовательно, общее количество возможных расстановок неатакующих ладей равно:

$r_{k}={\binom {m}{k}}{\binom {n}{k}}k!={\frac {n!m!}{k!(n-k)!(m-k)!}}.$

Например, на обычной шахматной доске (8×8) можно разместить 3 ладьи в $\textstyle {\frac {8!8!}{3!5!5!}}=18,816$ пути. Для k = m = n приведенная выше формула дает r _k = n ! что соответствует результату, полученному для классической задачи о ладьях.

Ладейный полином с явными коэффициентами теперь имеет вид:

$R_{m,n}(x)=\sum _{k=0}^{\min(m,n)}{\binom {m}{k}}{\binom {n}{k}}k!x^{k}=\sum _{k=0}^{\min(m,n)}{\frac {n!m!}{k!(n-k)!(m-k)!}}x^{k}.$

Если ограничение «ладьи не должны атаковать друг друга» снято, нужно выбрать любые k полей из m × n полей. Это можно сделать в:

${\binom {mn}{k}}={\frac {(mn)!}{k!(mn-k)!}}$ пути.

Если k ладей чем-то отличаются друг от друга, например, помечены или пронумерованы, все полученные к настоящему моменту результаты необходимо умножить на k !, количество перестановок k ладей.

Симметричные расположения

В качестве дальнейшего усложнения проблемы ладей потребуем, чтобы ладьи не только не атаковали, но и располагались на доске симметрично. В зависимости от типа симметрии это эквивалентно вращению или отражению доски. Симметричные расположения приводят ко многим проблемам, в зависимости от условия симметрии.

	а	б	с	д	и	ж	г	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	с	д	и	ж	г	час

Рис. 2. Симметричное расположение неатакующих ладей вокруг центра шахматной доски 8×8. Точками отмечены 4 центральных квадрата, окружающих центр симметрии.

Самая простая из таких расстановок — когда ладьи расположены симметрично относительно центра доски. Обозначим через G _n количество расстановок, в которых n ладей расставлены на доске с n шеренгами и n вертикалью. Теперь давайте сделаем так, чтобы на доске было 2 n рядов и 2 n файлов. Ладья на первой вертикали может быть размещена на любом из 2n полей этой вертикали. По условию симметрии размещение этой ладьи определяет расположение ладьи, стоящей на последней вертикали – она должна располагаться симметрично первой ладье относительно центра доски. Удалим первую и последнюю вертикали и ряды, на которых стоят ладьи (поскольку рядов четное, удаленные ладьи не могут стоять на одной горизонтали). Это даст доску из 2 n − 2 рядов и 2 n − 2 рядов. Ясно, что каждому симметричному расположению ладей на новой доске соответствует симметричное расположение ладей на исходной доске. Следовательно, G _{2 n} = 2 nG _{2 n − 2} (множитель 2 n в этом выражении обусловлен возможностью первой ладьи занять любую из 2 n квадратов в первом файле). Повторяя приведенную выше формулу, можно прийти к случаю доски 2 × 2, на которой имеются 2 симметричных расположения (по диагоналям). В результате этой итерации окончательное выражение имеет вид G _{2 n} = 2 ^н н ! Для обычной шахматной доски (8×8) G ₈ = 2 ⁴ × 4! = 16 × 24 = 384 центрально-симметричных расположения из 8 ладей. Одна из таких компоновок показана на рис. 2.

Для досок нечетного размера (содержащих 2 n + 1 рядов и 2 n + 1 рядов) всегда есть клетка, у которой нет своего симметричного дубля — это центральная клетка доски. На этом поле всегда должна стоять ладья. Удалив центральную вертикаль и горизонталь, получим симметричное расположение 2 n ладей на доске 2 n × 2 n . Следовательно, для такой доски снова G _{2 n + 1} = G _{2 n} = 2. ^н н !.

Чуть более сложная задача — найти количество неатакующих расстановок, которые не меняются при повороте доски на 90°. Пусть на доске 4 n вертикалей и 4 n рядов, а количество ладей тоже равно 4 n . В этом случае ладья, находящаяся на первой вертикали, может занимать любое поле на этой вертикали, кроме угловых (ладья не может находиться на угловом поле, потому что после поворота на 90° две ладьи будут атаковать друг друга). Есть еще 3 ладьи, которые соответствуют этой ладье и стоят они соответственно на последней шеренге, последней вертикали и первой шеренге (они получаются из первой ладьи поворотами на 90°, 180° и 270°). Удалив вертикали и ряды этих ладей, получим расположение ладей для доски (4 n − 4) × (4 n − 4) с необходимой симметрией. следующее рекуррентное соотношение Таким образом, получается : R _{4 n} = (4 n − 2) R _{4 n − 4} , где R _n — количество расстановок для доски размера n × n . Итерируя, получаем, что R _{4 n} = 2 n (2 n − 1)(2 n − 3)...1. Количество расстановок для (4 доска n + 1) × (4 n + 1) такая же, как и для доски 4 n × 4 n ; это потому, что на доске (4 n + 1) × (4 n + 1) одна ладья обязательно должна стоять в центре и, таким образом, центральный рядовой может быть удален. Следовательно р _{4 п + 1} знак равно р _{4 п} . Для традиционной шахматной доски ( n = 2) R ₈ = 4 × 3 × 1 = 12 возможных расстановок с вращательной симметрией.

Для (4 n + 2) × (4 n + 2) и (4 n + 3) × (4 n + 3) досок число решений равно нулю. Для каждой ладьи возможны два случая: либо она стоит в центре, либо не стоит в центре. Во втором случае эта ладья входит в ладейный квартет, который меняет поля при повороте доски на 90°. Следовательно, общее количество ладей должно быть либо 4 n (когда на доске нет центрального поля), либо 4 n + 1. Это доказывает, что R _{4 n + 2} = R _{4 n + 3} = 0.

Количество расстановок n неатакующих ладей, симметричных одной из диагоналей (для определенности, диагонали, соответствующей a1–h8 на шахматной доске) на доске n × n , задается телефонными номерами , определяемыми рекуррентностью Q _n = Q _{п - 1} + ( п - 1) Q _{п - 2} . Это повторение получается следующим образом. Обратите внимание, что ладья на первой вертикали либо стоит на нижнем угловом поле, либо на другом поле. В первом случае удаление первой вертикали и первой горизонтали приводит к симметричному расположению n − 1 ладей на ( n − 1) × ( n − 1) доске. Число таких расположений равно Q _{n − 1} . Во втором случае вместо исходной ладьи есть другая ладья, симметричная первой относительно выбранной диагонали. Удаление вертикалей и рядов этих ладей приводит к симметричному расположению n - 2 ладей на доске ( n - 2) × ( n - 2). Поскольку число таких расстановок равно Q _{n − 2} и ладью можно поставить на n − 1 поле первой вертикали, то существует ( n − 1) Q _{n − 2} способов сделать это, что немедленно дает указанную выше рекуррентность. . Тогда количество диагонально-симметричных расположений определяется выражением:

$Q_{n}=1+{\binom {n}{2}}+{\frac {1}{1\times 2}}{\binom {n}{2}}{\binom {n-2}{2}}+{\frac {1}{1\times 2\times 3}}{\binom {n}{2}}{\binom {n-2}{2}}{\binom {n-4}{2}}+\cdots .$

Это выражение получается путем разделения всех ладейных расстановок на классы; к классу s относятся те расстановки, в которых s пар ладей не стоят на диагонали. Точно так же можно показать, что количество расстановок n -ладей на доске размером n × n , таких, что они не атакуют друг друга и симметричны обеим диагоналям, определяется рекуррентными уравнениями B _{2 n} = 2 B _{2 n - 2} + (2 n - 2) B _{2 n - 4} и B _{2 n + 1} знак равно B _{2 n} .

Расположение, подсчитанное по классам симметрии

Другой тип обобщения - это тот, при котором расстановки ладей, полученные друг из друга в результате симметрии доски, считаются за одну. Например, если поворот доски на 90 градусов допускается как симметрия, то любое расположение, полученное поворотом на 90, 180 или 270 градусов, считается «таким же», как исходный рисунок, даже если эти расположения учитываются. отдельно в исходной задаче, где плата закреплена. Для таких задач Дудени замечает: «Сколько существует способов, если простые развороты и отражения не считать разными, еще не определено; это трудная проблема». Проблема сводится к подсчету симметричных расположений с помощью леммы Бернсайда .