§ 21. Перестановки с запретными положениями. Размещение по ячейкам

Задача о встречах и задача о супружеских парах — частные случаи задач, описываемых булевыми матрицами с ограничениями на расположение единиц (рис. 37 и 38). Эти две задачи можно решать с помощью перманента соответствующих булевых матриц, но процесс его вычисления в большинстве случаев неэффективен. Поэтому попытаемся применить к задачам такого рода метод производящих функций.

Булеву матрицу можно рассматривать в некотором смысле как шахматную доску. Заштрихованным клеткам в булевой матрице соответствуют нули, а незаштрихованным — единицы.

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

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

Аналогично можно подсчитать, что число сот размера равно

С точки зрения пересчета не все соответствующие задачи нужно различать. Например, все задач с одной запретной

ячейкой, по существу, неразличимы. Поэтому общее число различных с этой точки зрения задач трудно определить.

Задачи такого типа будем называть задачами о размещении неразличимых объектов в соты размера К ним относятся, например, некоторые задачи § 18 с сотами размера и без запретных ячеек.

Будем предполагать, что выполняются условия:

соты имеют порядок

в ячейке не более одного объекта (т. е. О или 1);

каждая строка и каждый столбец содержат не более одного объекта.

Рис. 42.

Рис. 43.

Эту задачу часто называют задачей о ладьях, если имеются в виду ладьи на шахматной доске, не бьющие друг друга, или задачей о назначениях работников на должностей, причем каждый работник может занять только одну должность и каждая должность может быть занята только одним работником. В § 61 мы увидим, что эта задача связана с понятием паросочетания в теории графов. На рис. 42 представлен пример такой задачи с и рис. 43 показывает, как поместить пять объектов в соты.

Для решения таких задач с помощью денумераторов будем пользоваться формулой включения и исключения из § 12.

Рассмотрим свойств, порядок :

Некоторые из этих свойств совместимы, другие — нет, например, если в какую-либо ячейку уже помещен объект, то ни в какую ячейку в том же столбце или той же строке нельзя поместить

другой объект. Пусть подмножество перестановок со свойством а подмножество перестановок со свойством Тогда

Выберем свойств из (указанных Тогда объектов можно разместить способами по остальным ячейкам. Обозначим через число непустых пересечений вида Тогда в силу (12.17) с

имеем

и

где через обозначено число перестановок в точности с свойствами. Согласно (12.54)

Рис. 44

Запишем производящую функцию для

Производящие функции для задач о будем обозначать через

Полиномы называются ладейными многочленами, а —многочленами попаданий.

Пример. На рис. 44 изображены соты порядка 6 с шестью запретными ячейками Подсчитаем

Имеем

Заметим, что пары и несовместимы. Следовательно,

Легко убедиться, что 11 неупорядоченных 3-выборок из общего числа несовместимы. Поэтому

Аналогично получаем

Следовательно,

Отсюда в силу (21.3) находим

Вычисляя

имеем

Это же получается и из (21.6):

Разложение на минимальные непересекающиеся подсоты. Будем рассматривать подсоты сот порядка Например, соты на рис. 46 — подсоты сот на рис. 45.

Пусть подсоты сот С. Назовем непересекающимися, если запретные ячейки не лежат на столбцах и строках, образующих Например, на рис. 47 подсоты, образованные строками и столбцами соответственно 1, 2, 3 и 4, 5, 6, 7, не пересекаются.

Для разложения сот на минимальные непересекающиеся подсоты достаточно заметить, что если запретна ячейка то строки и столбцы с индексами принадлежат одним и тем же подсотам.

Рис. 45.

Рис. 46.

Рис. 47.

Возьмем, например, соты на рис. 48.

Выписываем в столбец индексы, соответствующие одним и тем же подсотам, начиная с 1:

Таким образом, получаем следующие 5 минимальных непересекающихся подсот: с индексами с индексами с индексом 4 (без запретных ячеек), с индексами с индексом 2 (см. рис. 49).

Разложение на минимальные непересекающиеся подсоты единственно, что легко доказать.

Теорема. Пусть непересекающиеся подсоты, на которые разлагается С. Тогда

где соответствующие ладейные многочлены для

Доказательство. В самом деле, пусть число -выборок, соответствующих всевозможным непротиворечивым свойствам. Имеем

где равно числу -выборок с непротиворечивыми свойствами из или

Рис. 48

Рис. 49.

Учитывая (7.19), имеем

Пример (рис. 50). Запретные клетки обозначены через .

Легко получаем

а также

Отсюда

Рис. 50.

Замечание. Легко убедиться, что соотношение не влечет подобного соотношения для а также и для Формула (21.23)

обобщается на случай минимальных непересекающихся подсот:

Частичные соты для заданных сот. Если в заданных сотах аннулировать запреты на некоторые ячейки, то полученные соты называются частичными. На рис. 52 изображены частичные соты для сот на рис. 51.

Понятие частичных сот вводится с целью получить представление функции через более простые функции.

Рис. 51.

Рис. 52.

Теорема. Пусть заданы соты К. Через обозначим частичные соты для К, которые получаются снятием запрета с ячейки а через частичные соты, которые получаются из К снятием запрета со всех ячеек в строке и столбце. Тогда

где ладейные многочлены соответственно для

Доказательство. Обозначим через свойство, соответствующее ячейке а через подмножество перестановок с этим свойством. Любым множествам с непустым пересечением, не содержащим однозначно соответствуют множеств из а любым множествам с непустым пересечением, содержащим однозначно соответствуют множеств из и наоборот. Теорема доказана.

Проиллюстрируем эту теорему на примере.

Через обозначены соты на рис. 53, 54 и 55, где

— ячейка

Выпишем непустые пересечения для С при :

Таким образом,

Аналогично непустые пересечения для при

т. е. а непустые пересечения для при :

т. е. Отсюда видим, что пересечения из (21.39) и (21.41) дают все пересечения из (21.39).

Рис. 53.

Рис. 54.

Рис. 55.

Легко выписать теперь соотношение для производящих функций:

где

В самом деле,

Так как то имеем

Замечание. Функция определяется только лишь взаимным расположением запретных ячеек, а размеры сот несущественны. Так функция

одна и та же для всех сот на рис. 56.

Функционально эквивалентные соты. Двое сот с одной и той же функцией называются функционально эквивалентными.

Рис. 56.

Рис. 57.

Это отношение является отношением эквивалентности (поскольку оно рефлексивно, симметрично и транзитивно). Пример двух функционально эквивалентных сот с

приведен на рис. 57 (изображены лишь запретные ячейки).

Следовательно, двое функционально эквивалентных сот имеют совпадающие функции как так и В [36] приведены таблицы различных функций

Разложение сот на более простые частные соты. Как мы видели раньше (см. (21.42)),

Введем соответствующую (21.50) операцию над сотами:

Аналогично можно поступать с

Тогда

Поступаем так столько раз, сколько нужно.

(кликните для просмотра скана)

Приведем пример (рис. 58).

Символом К с нечетными индексами обозначаются частичные соты, где запрет снят с одной ячейки, а символом К с четными индексами обозначаются соты, где запрет снят с ячеек в одной строке и одном столбце. Разумеется, описанное разложение не единственно, и пересчет таких разложений является трудной за дачей.

Дополнение сот. Дополнением сот С являются соты С, где запретны все ячейки, которые не были запретными в С и наоборот. Соответствующий пример приведен на рис. 59.

Не существует простой формулы, позволяющей выразить через (об этом см. [36]).

УПРАЖНЕНИЯ

(см. скан)

(см. скан)