§ 22. Противоречивые перестановки

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

соответствуют соты на рис. 60.

Можно рассматривать перестановки, противоречащие нескольким заданным перестановкам. Эти перестановки удовлетво ряют ограничениям, вытекающим из рассмотрения сот, получающихся наложением сот, соответствующих каждой из заданных перестановок. Задача пересчета перестановок, противоречащих одной заданной перестановке, немедленно сводится (если переставить строки и столбцы в к задаче о встречах. Если задаются две перестановки, то одну из них можно считать тождественной.

Можно изучать также множества перестановок объектов, противоречащих одной (или нескольким) перестановкам из этих объектов

Рис. 60

Рис. 61

Рассмотрим теперь несколько задач о противоречивых перестановках.

Задача о встречах. Эта задача уже рассматривалась в § 14. Если через обозначить свойство: элемент занимает место то из рассмотрения сот на рис 61 легко получается

Отсюда

Имеем (см. 14.7))

Из (22.5) легко получить числа определяемые формулой (14.11).

С другой стороны,

Это — другое выражение для денумератора из (14.32), символически

Задача о супружеских парах. Задачу о супружеских парах из § 20 можно рассматривать как задачу об отыскании перестановок, противоречащих следующим двум Соответствующие соты указаны на рис. 62.

Рис. 62

Рис. 63

По второй лемме Капланскою имеем

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

и положить

то получим числа которые для от 2 до 8 приведены в таблице 22.1.

Таблица 22.1 (см. скан) Числа в задаче о супружеских парах

Видоизмененная задача о супружеских парах. Рассмотрим соты на рис. 63. Они соответствуют расположению супругов в задаче о супружеских парах, если эти пары рассаживаются вдоль одной из сторон прямоугольного стола, т. е. данные соты отличаются от сот на рис. 62 только ячейкой

По первой лемме Капланского

Если для этого случая обозначить через производящую функцию а через ее коэффициенты, то

В таблице 22.2 числа приведены для от 1 до 8.

Таблица 22.2 (см. скан) Числа в видоизмененной задаче о супружеских парах

Если индекс относится к задаче о супружеских парах, а индекс к видоизмененной задаче о супружеских парах, то в силу (21.38) и (21.42) имеем

и

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

Обобщенная задача о супружеских парах. Рассмотрим задачу пересчета перестановок, противоречащих двум заданным, одна из которых тождественна, а другая произвольная. Эта задача изучалась Тушаром и Риорданом [36].

На рис. 64 представлен пример при где две перестановки задаются нижними строками в

Рис. 64 показывает, что множества запретных ячеек, соответ ствующих

пересекаются. Напротив, если вторая подстановка является циклом (как на рис. 65), то приходим к задаче о супружеских парах.

Предположим, что подстановка, соответствующая второй перестановке, принадлежит классу

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

Рис. 64

Рис. 65.

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

где функции соответственно для сот порядка в задачах о супружеских парах. Пример (рис. 64). Пусть задана подстановка

Выписываем ее циклы:

т. е.

В силу (22.9)

Итак,

и

По формулам (21.3) и (21.8) вычисляем и

УПРАЖНЕНИЯ

(см. скан)