Задача о супружеских парах

В комбинаторике задача о супружеских парах или задача о гостях (англ. ménage problem, фр. problème des ménages) спрашивает, сколькими различными способами можно рассадить супружеские пары за круглым столом так, чтобы лица одного пола не сидели рядом, а также никакая пара супругов не сидела на соседних местах.

Задача сформулирована в 1891 году Эдуардом Люка и рассматривалась независимо несколькими годами раньше Питером Тэтом в связи с теорией узлов. Для количества пар 3, 4, 5, … искомое число способов рассаживания равно

12, 96, 3120, 115 200, 5 836 320, 382 072 320, 31 488 549 120, … (последовательность A059375 в OEIS).

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

Формулы

Пусть Mn обозначает количество рассаживаний для n пар. Тушар первым получил формулу:

M n = 2 ⋅ n ! ∑ k = 0 n ( − 1 ) k 2 n 2 n − k ( 2 n − k k ) ( n − k ) ! , {displaystyle M_{n}=2cdot n!sum _{k=0}^{n}(-1)^{k}{frac {2n}{2n-k}}{2n-k choose k}(n-k)!,}

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

Другая формула, теневым образом выражающая Mn через многочлены Чебышёва первого рода, дана Вайманом и Мозером.

Количество рассаживаний и подход «сначала дамы»

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

Дам можно рассадить 2·n! способами, поскольку имеется 2 варианта выбора набора мест и n! способов рассаживания на выбранных местах. Для каждого способа рассаживания имеется

A n = ∑ k = 0 n ( − 1 ) k 2 n 2 n − k ( 2 n − k k ) ( n − k ) ! {displaystyle A_{n}=sum _{k=0}^{n}(-1)^{k}{frac {2n}{2n-k}}{2n-k choose k}(n-k)!}

способов рассаживания джентльменов, что отличается от формулы Тушара как раз на множитель 2·n!. Эта формула позволяет получит последовательность количества рассаживаний пар (начиная с n=3):

1, 2, 13, 80, 579, 4738, 43 387, 439 792, … (последовательность A000179 в OEIS).

Для неё выполняется рекуррентное соотношение:

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

и более простое рекуррентное соотношение:

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

которые позволяют легко вычислять количество рассаживаний пар.

Графовые интерпретации

Рассаживания супружеских пар можно интерпретировать в терминах теории графов как ориентированные гамильтоновы циклы в графе корона. Корона получается удалением совершенного паросочетания из полного двудольного графа Kn,n. Она имеет 2·n вершин двух цветов, и каждая вершина соединена со всеми рёбрами другого цвета, за исключением одной вершины. В задаче о супружеских парах вершины представляют мужчин и женщин, а рёбра представляют пары мужчин и женщин, которые могут сидеть рядом. Этот граф получается из полного двудольного графа удалением совершенного паросочетания, где рёбра соединяют пары супругов. Любое правильное рассаживание пар можно описать последовательностью вершин, представляющую собой гамильтонов цикл в графе. Однако, два гамильтоновых цикла считаются эквивалентными, если они соединяют те же вершины в том же порядке, независимо от начальной точки, в то время как в задаче о супружеских парах начальная позиция существенна — если, как в случае с чаепитием Алисы, все гости сдвинулись бы на одно сиденье, это было бы совсем другое рассаживание, хотя и является тем же циклом с точки зрения теории графов. Таким образом, число ориентированных гамильтоновых циклов в короне меньше на множитель 2n по сравнению с числом рассаживаний, но больше на множитель (n—1)! по сравнению с числами рассаживание. Последовательность числа циклов в таких графах (как и ранее, начиная с n=3)

2, 12, 312, 9600, 416 880, 23 879 520, 1 749 363 840, … (последовательность A094047 в OEIS).

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

Связь с теорией узлов

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

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

1, 2, 5, 20, 87, 616, 4843, 44 128, 444 621, … (последовательность A002484 в OEIS).