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

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

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

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

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

Определение

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

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

куда р_k это количество способов разместить k не атакующие ладьи на доске м ряды и п столбцы. Доска может удерживать максимальное количество не атакующих ладей; действительно, ладей не может быть больше, чем меньшее из числа рядов и столбцов на доске (отсюда и предел ${ Displaystyle мин (т, п)}$ ).^[2]

Полные доски

Первые несколько ладейных многочленов на квадрате п × п доски (с р_п = р_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 способом; и так далее для больших плат.

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

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

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

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

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

Ладейный многочлен р_м,п(Икс) соответствует полный двудольный граф K_м,п . Ладейный полином общей доски B ⊆ B_м,п соответствует двудольному графу с левыми вершинами v₁, v₂, ..., v_м и правые вершины ш₁, ш₂, ..., ш_п и край v_яш_j всякий раз, когда квадрат (я, j) разрешено, т.е. принадлежит B. Таким образом, теория ладейных многочленов в некотором смысле содержится в теории парных многочленов.

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

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

Для неполного квадрата п × п доски (то есть ладьи не могут быть сыграны на некотором произвольном подмножестве полей доски) вычисление количества способов размещения п ладьи на доске эквивалентны вычислению постоянный матрицы 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. Ладья + точки обозначают количество клеток в ряду, доступное каждой ладье после размещения ладей на нижних рядах.

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

Тот же результат можно получить несколько другим способом. Дадим каждой ладье порядковый номер, соответствующий номеру ее ранга, и присвоим ей имя, соответствующее названию ее вертикали. Таким образом, ладья 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 раз.

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

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

Полином ладьи как обобщение проблемы ладьи

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

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

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

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

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

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

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

{ 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 квадраты из м × п квадраты. Это можно сделать:

{ displaystyle { binom {mn} {k}} = { frac {(mn)!} {k! (mn-k)!}}}

способами.

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

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

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

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

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

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

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

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

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

Количество аранжировок п не атакующие ладьи, симметричные одной из диагоналей (для определенности, диагональ, соответствующая a1 – h8 на шахматной доске) на п × п доска предоставляется телефонные номера определяется повторяемостью Q_п = Q_п − 1 + (п − 1)Q_п − 2. Эта повторяемость выводится следующим образом. Обратите внимание, что ладья на первой вертикали стоит либо на нижнем угловом квадрате, либо на другом квадрате. В первом случае удаление первого ряда и первого ранга приводит к симметричному расположению п - 1 ладья на (п − 1) × (п - 1) доска. Количество таких договоренностей Q_п − 1. Во втором случае для исходной ладьи есть еще одна ладья, симметричная первой относительно выбранной диагонали. Удаление вертикалей и рядов этих ладей приводит к симметричному расположению п - 2 ладьи на (п − 2) × (п - 2) доска. Так как количество таких устройств Q_п − 2 и ладью можно поставить на п - 1 квадрат первого файла, есть (п − 1)Q_п − 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 пары ладей не стоят по диагонали. Точно так же можно показать, что количество пладьи на п × п доска, так что они не атакуют друг друга и симметричны обеим диагоналям, задается рекуррентными уравнениями B_2п = 2B_2п − 2 + (2п − 2)B_2п − 4 и B_2п + 1 = B_2п.

Расстановки с учётом классов симметрии

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