Математика · объяснение и практика

Как запрещённые позиции превращают перестановку в задачу включения-исключения

Как посчитать перестановки с произвольными запрещёнными позициями, учесть невозможные пересечения запретов и использовать совместимые клетки как ладейные числа.

Синяя и оранжевая половины складываются в целый круг.

В теме Доказательства и комбинаторные модели · Учебная карта

В маршруте Счёт через устройство объектов · 10 тем

Главная мысль

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

Один запрет создаёт множество нарушений

В таблице строки обозначают разные объекты, столбцы — разные места. Перестановка выбирает по одной клетке в каждой строке и каждом столбце. Запрещённая клетка задаёт событие: соответствующий объект оказался именно в этом месте. Для одного такого нарушения остаётся свободно переставить n−1 объектов, то есть получается (n−1)! перестановок.

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

Совместимые запреты как расстановка ладей

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

Обозначим через rₖ число способов выбрать k совместимых запретных клеток, причём r₀=1. Тогда допустимых перестановок Σ(−1)ᵏrₖ(n−k)!. Для трёх объектов и запретов (1,1),(1,2) имеем r₁=2, r₂=0. Ответ 6−2·2=2: первый объект обязан оказаться на третьем месте, а остальные можно менять местами.

Пример

Для четырёх объектов запрещены только клетки (1,1),(1,2),(2,2). Сколько допустимых перестановок?

Имеем r₁=3 и r₂=1: совместима лишь пара (1,1),(2,2). Более крупных совместимых наборов нет. Поэтому 4!−3·3!+1·2!=24−18+2=8.

Почему форма запретной доски важна

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

Классическая задача без неподвижных точек использует запреты на всей диагонали. Здесь рассмотрена более широкая доска, где запреты могут находиться произвольно. Подсчёт ладейных чисел сам может быть сложным, но для маленьких схем их легко проверить по совместимости. Перед применением нужно также убедиться, что речь действительно о взаимно однозначных назначениях без повторения мест.

От чтения к действию

А теперь — вы

Для четырёх объектов запрещены только клетки (1,1) и (2,2). Сколько перестановок избегают обоих запретов?

Частые вопросы

Почему число пустых наборов запретов равно одному?

Это один способ не закреплять ни одного нарушения. Его вклад n! возвращает исходное множество всех перестановок.

Что делать, если у двух запретов общая строка?

Их совместное нарушение невозможно, поэтому такая пара не включается в r₂ и не создаёт поправку за пересечение.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться