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

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

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

Задача сформулирована в 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. В обозначениях Довкера для диаграмм узлов, раннюю форму которых использовал Тэт, n точек были пересечениями узла, которые пронумерованы вдоль узла числами от 1 до n. В сокращённой диаграмме две метки пересечения не могут быть последовательными числами, так что множество пар меток на каждом пересечении, использованных в обозначениях Довкера для обозначения узла, можно понимать как совершенное паросочетание в графе, имеющем в качестве вершин числа от 1 до n и рёбра между каждой парой чисел, имеющих различную чётность и не идущих подряд по модулю 2n. Этот граф образуется удалением гамильтонова цикла (соединяющего последовательные числа) из полного двудольного графа (соединяющего пары чисел с различной чётностью). Таким образом, число паросочетаний в таком графе равно числу рассаживаний. Для чередующихся узлов это паросочетание достаточно для описания диаграммы узла. Для других узлов необходимо указывать плюс или минус для каждого пересечения, чтобы описать, которая из двух нитей пересечения лежит сверху.

Однако задача перечисления узлов имеет дополнительные симметрии, не присутствующие в задаче о супружеских парах — если начать с другого пересечения, получим другую запись Довкера и все эти записи должны считаться представлением той же самой диаграммы. По этим причинам два паросочетания, отличающиеся только циклической перестановкой, следует считать эквивалентными и должны учитываться только один раз. Гильберт[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. Gleick, 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. — 1986.
  • 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. Архивировано 19 сентября 2006 года.
  • 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. doi:10.4153/CJM-1958-045-6.

Ссылки

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.