Задача Люка

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

В комбінаториці задача про подружні пари, задача про гостей, або задача Люка (англ. 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).

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

Формули

Нехай $M_{n}$ позначає кількість розсаджування для n пар. Тушар перший отримав формулу:

$M_{n}=2\cdot n!\sum _{k=0}^{n}(-1)^{k}{\frac {2n}{2n-k}}{2n-k \choose k}(n-k)!$

яка тепер носить його ім'я. Існує безліч робіт з доказами формули Тушара і її узагальнень, в яких частинам пар дозволяється сидіти поруч. Інша формула, тіньовим образом виражає $M_{n}$ через многочлени Чебишева першого роду, дана Вайманом і Мозером.

Кількість розсаджування та підхід «спочатку дами»

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

Дам можна розсадити $2\cdot n!$ способами, оскільки є 2 варіанти вибору набору місць і n! способів розсаджування на обраних місцях. Для кожного способу розсаджування є

$A_{n}=\sum _{k=0}^{n}(-1)^{k}{\frac {2n}{2n-k}}{2n-k \choose k}(n-k)!$

способів розсаджування джентльменів, що відрізняється від формули Тушара якраз на множник $2\cdot n!$. Ця формула дозволяє отримати послідовність кількості розсаджування пар (починаючи з n=3):

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

Для неї виконується рекурентне співвідношення:

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

і більш просте рекурентне співвідношення:

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

які дозволяють легко обчислювати кількість розсаджування пар.

Графові інтерпретації

Корони з шістьма, вісьма і десятьма вершинами. Зовнішній цикл кожного графу утворює гамільтонів цикл, але графи з вісьмома і десятьма вершинами мають ще інші гамільтонові цикли.

Розсаджування подружніх пар можна інтерпретувати в термінах теорії графів як орієнтовані гамільтонові цикли в графі корона. Корона виходить видаленням досконалого парування з повного двочасткового графу K_n,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).

Див. також

• Задача Обервольфаха — інша математична задача про розташування відвідувачів за столами.

Література

• 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. — JSTOR 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. — 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é. — Т. 19.
• Édouard Lucas. Théorie des Nombres.
• 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 : [арх. 19 вересня 2006]. — 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. — DOI:10.4153/CJM-1958-045-6.