Проблема с менажем - Ménage problem

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

В комбинаторная математика, то проблема с мужем или же проблема мужчин^[1] спрашивает, сколько разных способов можно усадить пары мужчина-женщина за круглый обеденный стол, чтобы мужчины и женщины чередовались, и никто не садился рядом со своим партнером. Эта проблема была сформулирована в 1891 г. Эдуард Лукас и независимо, несколькими годами ранее, Питер Гатри Тейт в связи с теория узлов.^[2] Для количества пар, равного 3, 4, 5, ... количество посадочных мест равно

12, 96, 3120, 115200, 5836320, 382072320, 31488549120, ... (последовательность A059375 в OEIS ).

Математики разработали формулы и рекуррентные уравнения для вычисления этих чисел и связанных последовательностей чисел. Эти числа не только применимы к этикету и теории узлов, но и имеют теоретический график интерпретация: они подсчитывают количество совпадения и Гамильтоновы циклы в некоторых семействах графов.

Формула Тушара

Позволять M_п обозначают количество посадочных мест для п пары. Тушар (1934) вывел формулу

{displaystyle M_ {n} = 2cdot n! sum _ {k = 0} ^ {n} (- 1) ^ {k} {frac {2n} {2n-k}} {2n-k выбрать k} (nk) !.}

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

Отличающийся мрачный формула для M_п с участием Многочлены Чебышева первого рода был дан Вайман и Мозер (1958).

Номера Ménage и решения для женщин

Есть 2 ×п! способы рассадки женщин: есть два набора сидений, которые можно расположить для женщин, и есть п! способы рассадки их на определенный набор сидений. Для каждой рассадки для женщин предусмотрены

{displaystyle A_ {n} = sum _ {k = 0} ^ {n} (- 1) ^ {k} {frac {2n} {2n-k}} {2n-k выбрать k} (n-k)!}

способы рассадки мужчин; эта формула просто опускает 2 ×п! фактор из формулы Тушара. Полученные меньшие числа (опять же, начиная с п = 3),

1, 2, 13, 80, 579, 4738, 43387, 439792, ... (последовательность A000179 в OEIS )

называются числа сотрудников. Фактор ${displaystyle {frac {2n} {2n-k}} {2n-k choose k}}$ количество способов формирования $k$ неперекрывающиеся пары соседних сидений или, что то же самое, количество совпадения из $k$ края в график цикла из $2 п$ вершины. Выражение для $А п$ является непосредственным результатом применения принцип включения – исключения для схем, в которых люди, сидящие на концах каждого края соответствия, должны быть парой.

До работы Богарт и Дойл (1986) Решение проблемы с менажем принималось в форме сначала нахождения всех расстановок для женщин, а затем подсчета для каждого из этих частичных расстановок сидений, количества способов их завершения, рассаживая мужчин подальше от их партнеров. Богарт и Дойл утверждали, что формулу Тушара можно вывести напрямую, рассматривая все расстановки сидений сразу, а не исключая участие женщин.^[3] Тем не мение, Кирусис и Контогеоргиу (2018) нашли еще более прямолинейное решение, описанное выше, «сначала дамы», используя несколько идей Богарта и Дойла (хотя они постарались переформулировать аргумент на негендерном языке).

Числа продаж удовлетворяют отношение повторения^[4]

{displaystyle A_ {n} = nA_ {n-1} + {frac {n} {n-2}} A_ {n-2} + {frac {4 (-1) ^ {n-1}} {n- 2}}}

и более простое четырехчленное повторение^[5]

{displaystyle displaystyle A_ {n} = nA_ {n-1} + 2A_ {n-2} - (n-4) A_ {n-3} -A_ {n-4},}

из которых могут быть легко вычислены сами числовые показатели.

Теоретико-графические интерпретации

Графы короны с шестью, восемью и десятью вершинами. Внешний цикл каждого графа образует гамильтонов цикл; графы с восемью и десятью вершинами также имеют другие гамильтоновы циклы.

Решения проблемы найма можно интерпретировать в теоретико-графовый сроки, как направленный Гамильтоновы циклы в графы короны. Граф короны формируется путем удаления идеальное соответствие из полный двудольный граф K_{п, п}; он имеет 2п вершины двух цветов, и каждая вершина одного цвета соединена со всеми вершинами другого цвета, кроме одной. В случае задачи о мужчинах вершины графа представляют мужчин и женщин, а ребра представляют пары мужчин и женщин, которым разрешено сидеть рядом друг с другом. Этот граф формируется путем удаления идеального соответствия, образованного парами мужчина-женщина, из полного двудольного графа, который связывает каждого мужчину с каждой женщиной. Любое допустимое расположение сидячих мест можно описать последовательностью людей за столом, которые образуют гамильтонов цикл на графике. Однако два гамильтоновых цикла считаются эквивалентными, если они соединяют одни и те же вершины в одном и том же циклическом порядке независимо от начальной вершины, в то время как в задаче о множестве начальная позиция считается значимой: если, как в Алиса Во время чаепития все гости меняются местами на одно место, это считается разным расположением сидений, хотя оно описывается одним и тем же циклом. Следовательно, количество ориентированных гамильтоновых циклов в графе короны меньше в 2 раза.п чем количество посадочных мест,^[6] но больше в (п - 1)! чем количество людей. Последовательность номеров циклов в этих графах (как и раньше, начиная с п = 3) является

2, 12, 312, 9600, 416880, 23879520, 1749363840, ... (последовательность A094047 в OEIS ).

Также возможно второе теоретико-графическое описание проблемы. После того, как женщины расселятся, возможные варианты рассадки оставшихся мужчин можно описать следующим образом: идеальное соответствие в графе, образованном удалением одного гамильтонова цикла из полного двудольного графа; у графа есть ребра, соединяющие открытые места с мужчинами, и удаление цикла соответствует запрету мужчинам сидеть на любом из открытых сидений рядом с их женами. Проблема подсчета паросочетаний в двудольном графе и, следовательно, a fortiori проблема вычисления численности персонала, может быть решена с помощью перманенты определенных 0-1 матрицы. В случае проблемы с оплатой матрица, возникающая из этого взгляда на проблему, является циркулянтная матрица в котором все элементы образующей строки, кроме двух, равны $1$ .^[7]

Теория узлов

Мотивация Тэта к изучению проблемы с мужчинами возникла из попытки найти полный список математические узлы с данным количество переходов, сказать п. В Обозначение Даукера для узловых диаграмм, ранняя форма которых использовалась Тэтом, 2п точки, где узел пересекает сам себя, в последовательном порядке вдоль узла, помечены 2п числа от 1 до 2п. В сокращенной диаграмме две метки на перекрестке не могут быть последовательными, поэтому набор пар меток на каждом перекрестке, используемый в нотации Даукера для представления узла, можно интерпретировать как идеальное совпадение в графе, имеющем вершину для каждое число в диапазоне от 1 до 2п и ребро между каждой парой чисел, которые имеют разную четность и не являются последовательными по модулю 2п. Этот граф формируется путем удаления гамильтонова цикла (соединения последовательных чисел) из полного двудольного графа (соединяющего все пары чисел с разной четностью), и поэтому он имеет количество совпадений, равное количеству чисел. За чередующиеся узлы, этого сопоставления достаточно, чтобы описать саму диаграмму узла; для других узлов необходимо указать дополнительный положительный или отрицательный знак для каждой пары пересечения, чтобы определить, какая из двух нитей пересечения лежит над другой цепью.

Однако проблема перечисления узлов имеет некоторые дополнительные симметрии, отсутствующие в задаче о разводе: для одной и той же диаграммы узлов получаются разные нотации Даукера, если начинать разметку в другой точке пересечения, и все эти разные обозначения следует рассматривать как представляющие одну и ту же диаграмму. диаграмма. По этой причине два сопоставления, которые отличаются друг от друга на циклическая перестановка должны рассматриваться как эквивалентные и учитываться только один раз. Гилберт (1956) решил эту модифицированную проблему перечисления, показав, что количество различных соответствий равно

1, 2, 5, 20, 87, 616, 4843, 44128, 444621, ... (последовательность A002484 в OEIS ).

Смотрите также

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

Примечания

^ "Ménage" - это Французский слово для «домашнего хозяйства» (здесь имеется в виду пара мужчина-женщина).
^ Дутка (1986).
^ Глейк (1986).
^ Мьюир (1882); Лайсан (1891). Более сложные рецидивы были описаны ранее Кэли и Мьюир (1878).
^ Мьюир (1882); Кэнфилд и Вормальд (1987).
^ Пассмор (2005).
^ Мьюир (1878); Идс, Прегер и Себери (1983); Кройтер (1984); Хендерсон (1975).

внешняя ссылка

[1] "Ménage" - это Французский слово для «домашнего хозяйства» (здесь имеется в виду пара мужчина-женщина).

[2] Дутка (1986).

[3] Глейк (1986).

[4] Мьюир (1882); Лайсан (1891). Более сложные рецидивы были описаны ранее Кэли и Мьюир (1878).

[5] Мьюир (1882); Кэнфилд и Вормальд (1987).

[6] Пассмор (2005).

[7] Мьюир (1878); Идс, Прегер и Себери (1983); Кройтер (1984); Хендерсон (1975).

[1]

[2]

[3]

[4]

[5]

[6]

[7]