§ 20. Задача о супружеских парах, или задача Люка

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

Рассмотрим, например, рис. 16—18. Им соответствуют булевы матрицы на рис. 34—36, в которых предполагается, что на незанятых местах стоят нули. Такие матрицы иногда называют «матрицами назначений».

Поставим следующий вопрос: как пересчитать подстановки (или перестановки, см. стр. 87), для которых единицы не могут находиться на некоторых фиксированных местах? В главе IV, § 46 мы решим задачу перечисления таких подстановок.

В § 14 уже рассматривалась подобная задача: задача о беспорядках. В булевой матрице беспорядка на главной диагонали не могут стоять единицы (рис. 37). Сейчас рассмотрим другую такую задачу.

За круглым столом рассаживаются супружеских пар, мужчины и женщины через одного, причем муж не должен сидеть рядом со своей женой. Эту задачу Люка назвал задачей о супружеских парах. Разместим сначала жен, что можно сделать способами. Тогда каждый муж может занять любое место, кроме мест справа и слева от своей жены, и число размещений мужей не зависит от размещения жен. Итак, задача сводится к задаче о соответствующем размещении мужей. Перенумеруем мужей от 1 до Теперь задача состоит в том, чтобы пересчитать перестановки такие, что элемент не может стоять на местах элемент на местах На рис. 38 изображены эти запрещенные места при На рис. 38 приведено одно из решений, которое в виде подстановки изображено на рис. 40, и рис. 39 показывает соответствующее расположение семи супружеских пар за круглым столом (номер жены тот же, что и у ее мужа, только со штрихом).

Пусть булева матрица порядка с элементами

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

Полагаем

Обозначая через число перестановок супружеских пар таких, что муж — не сосед своей жены, получаем

Можно вычислить исходя из но этот способ неэффективен, и приведенный ниже пример показывает, что нельзя непосредственно получить простую формулу вида (15.37) или (15.47).

Рис. 39.

Рис. 40.

Для вычисления иногда можно воспользоваться формулой Тушара. Предварительно рассмотрим пример (используем (15.28)).

Пусть

(см. скан)

(см. скан)

Очевидно, что , образованы из нулей, поэтому Итак

Мы видим, что не все равны между собой; по этой причине трудно получить непосредственно простые формулы вида (15.37) или (15.47).

Тушар вывел следующую формулу, использовав две леммы Капланского;

Применим эту формулу к случаю

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

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

Очевидно,

Пусть Разобьем множество таких наборов на два подмножества: наборы, содержащие первый объект, и наборы, не содержащие его. Так как набор, содержащий первый объект, не содержит второго, то число наборов в соответствующем подмножестве равно

Но число наборов, не содержащих первого объекта, равно

поэтому

Теперь применяем индукцию. Пусть (20.10) выполняется для всех множеств с числом объектов, меньшим

Тогда

и (20.10) доказано.

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

Например, при (рис. 41)

Эти наборы

Как и раньше, разобьем множество наборов на два подмножества: наборы, содержащие первый объект, и наборы, не содержащие его. Так как число наборов первого подмножества равно

а второго

то

и (20.18) доказано.

Рассмотрим теперь перестановки элементов Обозначим через свойство: в перестановке объект стоит на месте; через — свойство: в перестановке объект стоит на месте и через свойство: объект стоит на первом месте.

Рис. 41.

Рассмотрим эти свойств в следующем порядке:

Фиксируем из них. Число перестановок, удовлетворяющих этим свойствам, равно если свойства не противоречивы, и нулю в протнвном случае. Если обозначим через число наборов из непротиворечивых свойств, а через число перестановок, не удовлетворяющих ни одному из свойств (20.23), то по формуле решета (12.20) с

имеем

Применяя теперь вторую лемму Капланского к множеству (20.23), получаем

Подставляя (20.26) в (20.25), находим

УПРАЖНЕНИЯ

(см. скан)