Полином ладьи - Rook polynomial

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

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

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

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

Определение

Ладья многочлен Р _Б ( х ) из платы B является функцией генерации для чисел расположений , не являющихся атакующих ладей:

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

где r _k - количество способов разместить k не атакующих ладей на доске из m строк и n столбцов. На доске может находиться максимальное количество не атакующих ладей; действительно, ладей не может быть больше, чем меньшее из числа рядов и столбцов на доске (отсюда и предел ). ${\ Displaystyle \ мин (т, п)}$

Полные доски

Первые несколько ладейных многочленов на досках  размером n ×  n (при R _n = R _B ) равны :

${\ Displaystyle {\ begin {align} 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. \ конец {выровнено}}}$

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

Для полных прямоугольных досок  размером m ×  n B _{m , n} пишем R _{m, n}  : =  R _{B m , n}  . Меньшее из m и n может быть принято как верхний предел для k , поскольку, очевидно, r _k  = 0, если k > min ( m , n ). Это также показано в формуле для R _{m, n} ( x ).

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

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

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

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

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

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

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

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

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

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

	а	б	c	d	е	ж	грамм	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	c	d	е	ж	грамм	час

Рис. 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 поля:

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

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

Ряд задач из разных сфер человеческой деятельности можно свести к проблеме ладьи, дав им «ладейную формулировку». В качестве примера: компания должна нанять 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 , этот выбор можно сделать разными способами. Точно так же можно выбрать набор из k файлов, на которых можно разместить ладьи . Поскольку выбор вертикалей не зависит от выбора рангов, в соответствии с правилом произведений есть способы выбрать поле, на которое ставить ладью. ${\ displaystyle {\ binom {m} {k}}}$${\ Displaystyle {\ binom {п} {к}}}$${\ displaystyle {\ binom {m} {k}} {\ binom {n} {k}}}$

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

${\ displaystyle r_ {k} = {\ binom {m} {k}} {\ binom {n} {k}} k! = {\ frac {n! m!} {k! (nk)! (mk) !}}.}$

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

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

${\ displaystyle 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! (nk)! (mk)!}} x ^ {k}.}$

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

${\ displaystyle {\ binom {mn} {k}} = {\ frac {(mn)!} {k! (mn-k)!}}}$ способами.

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

Симметричные композиции

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

	а	б	c	d	е	ж	грамм	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	c	d	е	ж	грамм	час

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

Самый простой из этих вариантов - когда ладьи расположены симметрично относительно центра доски. Обозначим через G _n количество расстановок, при которых n ладей размещаются на доске с n рядами и n вертикалями. Теперь сделаем так, чтобы доска содержала 2 n рангов и 2 n файлов. Ладья на первой вертикали может быть размещена на любом из 2 n полей этой вертикали. По условию симметрии размещение этой ладьи определяет размещение ладьи, стоящей на последней вертикали - она ​​должна располагаться симметрично первой ладье относительно центра доски. Удалим первую и последнюю вертикали и ряды, которые занимают ладьи (так как рядов четное, удаленные ладьи не могут стоять в одном ряду). Это даст доску из 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 ⁿ n ! Для обычной шахматной доски (8 × 8) G ₈ = 2 ⁴  × 4! = 16 × 24 = 384 центрально-симметричных расстановок 8 ладей. Одно из таких устройств показано на рис.2.

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

Немного более сложная задача - найти количество не атакующих расстановок, которые не меняются при повороте доски на 90 °. Пусть на доске 4 n вертикалей и 4 n рядов, а количество ладей также равно 4 n . В этом случае ладья, которая находится на первой вертикали, может занимать любое поле на этой вертикали, кроме угловых (ладья не может находиться на угловом поле, потому что после поворота на 90 ° две ладьи будут атаковать друг друга). Есть еще 3 ладьи, соответствующие этой ладье, и они стоят, соответственно, на последней, последней и первой горизонталях (они получаются от первой ладьи поворотами на 90 °, 180 ° и 270 °). Удаляя ряды и ряды этих ладей, получаем расстановку ладей на  доске (4 n  - 4) × (4 n - 4) с требуемой симметрией. Таким образом, следующее рекуррентное соотношение получается: R _{4 п} = (4 п  - 2) R _{4 п  - 4} , где R _п есть число механизмов для п  ×  п плате. Итерируя, получаем, что 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) одна ладья обязательно должна стоять в центре, и, таким образом, центральная линия и вертикаль могут быть удалены. Следовательно, R _{4 n  + 1} = R _{4 n} . Для традиционной шахматной доски ( 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 _{n  - 1} + ( n  - 1) Q _{n  - 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} способов сделать это, что сразу дает указанное выше повторение. . Тогда количество диагонально-симметричных расположений определяется выражением:

${\ displaystyle 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 градусов, считается «таким же», как и исходный узор, даже если эти расположения учитываются. отдельно в исходной задаче, где фиксируется плата. Для таких проблем Дудени замечает: «Сколько существует способов, если простые перевороты и отражения не считаются разными, еще не определено; это трудная проблема». Проблема сводится к подсчету симметричных расположений с помощью леммы Бернсайда .

Ссылки