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

Материал из Википедии — свободной энциклопедии
(перенаправлено с «Задача о гостях»)
Перейти к: навигация, поиск
Круглый стол на десять персон. Существует 3120 различных способов рассаживания пяти супружеских пар так, чтобы пол сидящих гостей чередовался, а также никакая пара супругов не сидела на соседних местах.

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

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

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

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

Формула Тушара[править | править вики-текст]

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

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

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

Количество рассаживаний и подход «сначала дамы»[править | править вики-текст]

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

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

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

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

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

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

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

Графовые интерпретации[править | править вики-текст]

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

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

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

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

Связь с теорией узлов[править | править вики-текст]

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

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

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

Примечания[править | править вики-текст]

  1. Dutka, 1986.
  2. Touchard, 1934.
  3. Wyman, Moser, 1958.
  4. Bogart, Doyle, 1986.
  5. Glieck, 1986.
  6. Muir 1882; Laisant 1891. Несколько более сложные рекуррентные формулы были описаны до этого в работах Кейли и Мьюра(Muir 1878).
  7. Muir 1882; Canfield, Wormald 1987.
  8. Passmore, 2005.
  9. Muir 1878; Eades, Praeger, Seberry 1983; Kräuter 1984; Henderson 1975.
  10. Gilbert, 1956.

Литература[править | править вики-текст]

  • Kenneth P. Bogart, Peter G. Doyle Non-sexist solution of the ménage problem // American Mathematical Monthly. — 1986. — Т. 93, вып. 7. — С. 514—519. — DOI:10.2307/2323022.
  • Nguyen-Huu Bong Lucas numbers and the menage problem // International Journal of Mathematical Education in Science and Technology. — 1998. — Т. 29, вып. 5. — С. 647—661. — DOI:10.1080/0020739980290502.
  • E. Rodney Canfield, Nicholas C. Wormald Ménage numbers, bijections and P-recursiveness // Discrete Mathematics. — 1987. — Т. 63, вып. 2–3. — С. 117—129. — DOI:10.1016/0012-365X(87)90002-1..
  • Heinrich Dörrie. 100 Great Problems of Elementary Mathematics. — Dover, 1965. — С. 27—33. — ISBN 978-0-486-61348-2..
  • Jacques Dutka On the problème des ménages // The Mathematical Intelligencer. — 1986. — Т. 8, вып. 3. — С. 18—33. — DOI:10.1007/BF03025785.
  • Some remarks on the permanents of circulant (0,1) matrices // Utilitas Mathematica. — 1983. — Т. 23. — С. 145—159.
  • E. N. Gilbert Knots and classes of ménage permutations // Scripta Mathematica. — 1956. — Т. 22. — С. 228—233.
  • James Gleick Math + Sexism: A Problem // New York Times.
  • J. R. Henderson Permanents of (0,1)-matrices having at most two zeros per line // Canadian Mathematical Bulletin. — 1975. — Т. 18, вып. 3. — С. 353—358. — DOI:10.4153/CMB-1975-064-6.
  • Lars Holst On the ‘problème des ménages’ from a probabilistic viewpoint // Statistics and Probability Letters. — 1991. — Т. 11, вып. 3. — С. 225—231. — DOI:10.1016/0167-7152(91)90147-J.
  • Irving Kaplansky Solution of the problème des ménages // Bulletin of the American Mathematical Society. — 1943. — Т. 49, вып. 10. — С. 784—785. — DOI:10.1090/S0002-9904-1943-08035-4.
  • The problème des ménages // Scripta Mathematica. — 1946. — Т. 12. — С. 113—124.
  • Arnold Richard Kräuter Über die Permanente gewisser zirkulanter Matrizen und damit zusammenhängender Toeplitz-Matrizen (нем.) // Séminaire Lotharingien de Combinatoire. — 1984. — Т. B11b.
  • Charles-Ange Laisant. Vie de la société. — Bulletin de la Société Mathématique de France. — 1891. — Т. 19. — С. 105—108.
  • Édouard Lucas. Théorie des Nombres. — Paris: Gauthier-Villars, 1891. — С. 491—495.
  • Thomas Muir On Professor Tait's problem of arrangement // Proceedings of the Royal Society of Edinburgh. — 1878. — Т. 9. — С. 382—391.
  • Thomas Muir Additional note on a problem of arrangement // Proceedings of the Royal Society of Edinburgh. — 1882. — Т. 11. — С. 187—190.
  • Amanda F. Passmore An elementary solution to the ménage problem. — 2005.
  • John Riordan The arithmetic of ménage numbers // Duke Mathematical Journal. — 1952. — Т. 19, вып. 1. — С. 27—30. — DOI:10.1215/S0012-7094-52-01904-2.
  • Lajos Takács On the “problème des ménages” // Discrete Mathematics. — 1981. — Т. 36, вып. 3. — С. 289—297. — DOI:10.1016/S0012-365X(81)80024-6.
  • J. Touchard Sur un problème de permutations // C. R. Acad. Sciences Paris. — 1934. — Т. 198, вып. 631—633.
  • On the problème des ménages // Canadian Journal of Mathematics. — 1958. — Т. 10, вып. 3. — С. 468—480.

Ссылки[править | править вики-текст]