Задача о гостях

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

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

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

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

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

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

M_n = 2 \cdot n! \sum_{k=0}^n (-1)^k \frac{2n}{2n-k} {2n-k\choose k} (n-k)!.

Было выпущено много работ по доказательству этой формулы и её обобщённых версий, в которых части пар разрешается сидеть рядом. Другая формула, для Mn, использующая многочлены Чебышёва, была дана Вайманом и Мозером (Wyman, Moser 1958).

Числа размещения гостей и решения «сначала дамы»[править | править вики-текст]

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

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

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, 43387, 439792, ... (последовательность A000179 в OEIS)

Эта последовательность называется числа размещения гостей. Для этих чисел выполняется рекуррентное уравнение[3]

A_n = n A_{n-1} + \frac{n}{n-2} A_{n-2} + \frac{4(-1)^{n-1}}{n-2}

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

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

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

Интерпретация в теории графов[править | править вики-текст]

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

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

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

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

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

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

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

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

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

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

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

  • Kenneth P. Bogart, Peter G. Doyle Non-sexist solution of the ménage problem // American Mathematical Monthly. — 1986. — В. 7. — Т. 93. — С. 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. — В. 5. — Т. 29. — С. 647–661. — DOI:10.1080/0020739980290502.
  • E. Rodney Canfield, Nicholas C. Wormald Ménage numbers, bijections and P-recursiveness // Discrete Mathematics. — 1987. — В. 2–3. — Т. 63. — С. 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. — В. 3. — Т. 8. — С. 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. — В. 3. — Т. 18. — С. 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. — В. 3. — Т. 11. — С. 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. — В. 10. — Т. 49. — С. 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. — В. 1. — Т. 19. — С. 27–30. — DOI:10.1215/S0012-7094-52-01904-2.
  • Lajos Takács On the “problème des ménages” // Discrete Mathematics. — 1981. — В. 3. — Т. 36. — С. 289–297. — DOI:10.1016/S0012-365X(81)80024-6.
  • J. Touchard Sur un problème de permutations // C. R. Acad. Sciences Paris. — 1934. — В. 631–633. — Т. 198..
  • On the problème des ménages // Canadian Journal of Mathematics. — 1958. — В. 3. — Т. 10. — С. 468–480..

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