Математика / Дискретная математика

Ладейный многочлен: назначения с запретами

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

Опубликовано: Обновлено:

Формула

$$N(B)=\sum_{k=0}^{n}(-1)^k r_k(B)(n-k)!,\qquad r_0(B)=1$$
Схема Две разные доски запретов
R=1+2x+x²R=1+2x

Оранжевые клетки запрещены. Слева r₂=1, справа r₂=0: две клетки общей строки не могут нарушаться одновременно.

Обозначения

$n$
число различных объектов и позиций, шт.
$B$
набор запрещённых клеток таблицы n×n, —
$r_k(B)$
число способов поставить k невзаимобьющих ладей на запрещённые клетки, шт.
$N(B)$
число назначений без попадания в B, шт.

Условия применения

Есть n различимых объектов и n различимых мест; каждый объект занимает ровно одно место, все места заняты. B содержит именно запрещённые клетки, а r_k считает размещения ладей внутри B без общих строк и столбцов. Все ограничения задаются отдельными парами объект–место.

Ограничения

Для повторяющихся объектов, вместимости места больше одного или групповых ограничений формулу нужно менять. Ладьи здесь ставят на запрещённую доску для вычисления поправок, а итоговые назначения избегают этой доски. Перепутать разрешённую и запрещённую доску — значит решать другую задачу.

Подробное объяснение

Клетка (i,j) означает событие: объект i назначен на место j. Включения и исключения начинают со всех n! перестановок, вычитают перестановки с каждым отдельным нарушением, прибавляют двойные нарушения и продолжают чередование. Требуется подсчитать, какие наборы нарушений вообще могут произойти одновременно.

Если две выбранные клетки имеют общую строку, они требуют от одного объекта двух мест. Если общий столбец — требуют двух объектов в одном месте. Оба набора невозможны. Совместимы только наборы без общих строк и столбцов: именно такие наборы изображают невзаимобьющие ладьи. После фиксации k пар оставшиеся n−k объектов размещаются (n−k)! способами.

Ладейный многочлен R_B(x)=Σr_kx^k хранит все необходимые коэффициенты. Для одной запрещённой клетки R=1+x. Для двух клеток в разных строках и столбцах R=(1+x)², а для двух клеток одной строки R=1+2x: второй порядок отсутствует. Это различие сохраняет структуру конфликтов, которую простое число запретов теряет.

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

Как пользоваться формулой

  1. Нарисуйте квадратную таблицу объект–место и отметьте запрещённые клетки; проверьте, что запреты относятся к отдельным парам.
  2. Найдите r₀=1 и r₁=числу запретов; затем перечислите пары и большие наборы клеток без общей строки или столбца.
  3. Умножьте каждый r_k на (n−k)! и сложите члены со знаками плюс, минус, плюс, начиная с полного числа n!.
  4. Проверьте целочисленность и границы 0≤N≤n!; для малой таблицы сравните ответ с независимым перебором допустимых назначений.

Историческая справка

Ладейные многочлены связывают задачи размещения шахматных фигур с классическим подсчётом перестановок с ограничениями. Шахматная терминология выражает конкретную совместимость: отсутствие общих строк и столбцов совпадает с требованием взаимно однозначного назначения. Многочлен нужен как конечная производящая функция, а не как приближение или геометрическая модель движения фигуры.

В университетских заметках Джона Грина к курсу Math 5366 осени 2015 года рассматриваются ладейные коэффициенты и рекурсия удаления клетки или её строки и столбца. В курсе Александра Йонга за 2025 год они применяются к запретным позициям через включения и исключения. Эти современные учебные изложения подтверждают способ вычисления; из дат курсов нельзя делать вывод о дате открытия метода или приписывать его преподавателям.

Историческая линия формулы

Это стандартный метод комбинаторики ограниченных перестановок. Приведённые учебные курсы используются для проверки определения и формулы, а не для установления первооткрывателя. Ладейный многочлен и включения–исключения выполняют разные шаги одного подсчёта: совместимость и устранение нарушений.

Пример

Три различных сотрудника получают три различных задания. Первому запрещено первое задание, второму — второе. Остальные пары разрешены. Нужно найти число взаимно однозначных назначений без нарушений, а не вероятность при независимом выборе заданий. На запрещённой доске две клетки (1,1) и (2,2) в разных строках и столбцах. Поэтому r₀=1, r₁=2, r₂=1, r₃=0. N=3!−2·2!+1·1!=6−4+1=3. Прямой список допустимых перестановок мест: (2,1,3), (2,3,1), (3,1,2). Здесь запись перечисляет задания первого, второго и третьего сотрудников. Все три удовлетворяют запретам, и третьему сотруднику достаётся оставшееся место. Число 3 лежит между нулём и 6.

Частая ошибка

Нельзя ставить две ладьи одной строки при вычислении r₂: такой набор нарушений невозможен. Нельзя заменять r_k обычным выбором k запрещённых клеток без проверки столбцов. Факториал относится к оставшимся n−k объектам. Доску B нельзя автоматически считать разрешённой: в формуле с чередующимися знаками она состоит из запретов.

Практика

Задачи с решением

Один запрет

Условие. Четыре объекта размещают по четырём местам, запрещена только клетка (1,1). Найдите N.

Решение. R=1+x, поэтому N=4!−3!=24−6=18.

Ответ. 18 назначений.

Два запрета одной строки

Условие. При n=3 запрещены (1,1) и (1,2). Найдите N.

Решение. R=1+2x, r₂=0 из-за общей строки. N=6−2·2=2. Первый объект обязан занять третье место, остальные меняются двумя способами.

Ответ. 2 назначения.

Дополнительные источники

  • https://www.d.umn.edu/~jgreene/Combinatorics/Fall_2015/Rook_polynomials.pdf
  • https://ayong.web.illinois.edu/Spring2025Math413/lecture16.html

Связанные формулы

Математика

Распределение числа совпадений в перестановке

$D_{n,k}=\binom nk !(n-k)$

Число перестановок с ровно k неподвижными точками получается выбором совпавших мест и беспорядком на остальных позициях. Деление на n! даёт вероятность ровно k совпадений в случайной перестановке.

Математика

Лемма Бёрнсайда: число объектов с учётом симметрий

$|X/G|=\frac1{|G|}\sum_{g\in G}|\operatorname{Fix}(g)|$

Число классов объектов относительно конечной группы симметрий равно среднему числу объектов, неподвижных при её элементах. Лемма Бёрнсайда учитывает симметричные объекты с меньшими орбитами.

Математика

Число перестановок без повторений

$P_n=n!$

Формула описывает прием «перестановки разных объектов» для подсчета конечных объектов без полного перебора. Она фиксирует, что именно считается: случаи, шаги, группы, пересечения, рекуррентные члены или пары вершин, и помогает избежать двойного счета.