Математика / Дискретная математика
Ладейный многочлен: назначения с запретами
Ладейные числа считают совместимые наборы запрещённых назначений. Чередующаяся сумма с факториалами затем даёт число перестановок, которые избегают всех запрещённых клеток таблицы.
Формула
Оранжевые клетки запрещены. Слева 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: второй порядок отсутствует. Это различие сохраняет структуру конфликтов, которую простое число запретов теряет.
При вычислении можно выбрать клетку и разделить размещения на случаи с ладьёй и без неё. В первом удаляются вся строка и весь столбец этой клетки, во втором — только сама клетка. Проверка итоговой суммы прямым перебором перестановок удобна для малых таблиц. Все коэффициенты целые и неотрицательные, но чередующаяся итоговая сумма требует точной арифметики.
Как пользоваться формулой
- Нарисуйте квадратную таблицу объект–место и отметьте запрещённые клетки; проверьте, что запреты относятся к отдельным парам.
- Найдите r₀=1 и r₁=числу запретов; затем перечислите пары и большие наборы клеток без общей строки или столбца.
- Умножьте каждый r_k на (n−k)! и сложите члены со знаками плюс, минус, плюс, начиная с полного числа n!.
- Проверьте целочисленность и границы 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
Связанные формулы
Математика
Распределение числа совпадений в перестановке
Число перестановок с ровно k неподвижными точками получается выбором совпавших мест и беспорядком на остальных позициях. Деление на n! даёт вероятность ровно k совпадений в случайной перестановке.
Математика
Лемма Бёрнсайда: число объектов с учётом симметрий
Число классов объектов относительно конечной группы симметрий равно среднему числу объектов, неподвижных при её элементах. Лемма Бёрнсайда учитывает симметричные объекты с меньшими орбитами.
Математика
Эйлеровы числа: перестановки с заданным числом спусков
Эйлерово число A(n,k) считает перестановки n различных чисел с ровно k спусками между соседними позициями. Рекурсия строит распределение по k вставкой нового наибольшего элемента.
Математика
Число перестановок без повторений
Формула описывает прием «перестановки разных объектов» для подсчета конечных объектов без полного перебора. Она фиксирует, что именно считается: случаи, шаги, группы, пересечения, рекуррентные члены или пары вершин, и помогает избежать двойного счета.