Перегляд вихідного коду сторінки Задача Люка

{{без виносок|дата=27 листопада 2019}}
[[Файл:Wedding Banquet setting.jpeg|міні|215x215пкс|Круглий стіл на десять персон. Існує 3120 різних способів розсаджування п'яти подружніх пар так, щоб стать гостей чергувалася, а також ніяка подружня пара не сиділа на сусідніх місцях.]]
В [[Комбінаторика|комбінаториці]] '''задача про подружні пари''', '''задача про гостей''', або '''задача Люка''' ({{lang-en|Ménage problem}}, {{lang-fr|Problème des ménages}}) запитує, скількома різними способами можна розсадити подружні пари за круглим столом так, щоб особи однієї статі не сиділи поруч, а також щоб ніяка подружня пара не сиділа на сусідніх місцях.

Завдання сформульоване в [[1891]] року [[Едуард Люка|Едуардом Люка]] і розглядалося незалежно кількома роками раніше [[Пітер Гатрі Тет|Пітером Тетом]] у зв'язку з [[Теорія вузлів|теорією вузлів]]. Для кількості пар 3, 4, 5, … шукане число способів розсаджування дорівнює

: 12, 96, 3120, 115 200, 5 836 320, 382 072 320, 31 488 549 120, … (послідовність [[oeis:A059375|A059375]] в [[OEIS]]).

Для кількості способів розсаджування знайдені явні і [[Рекурентне співвідношення|рекурентні формули]]. Крім застосування в [[етикет]]і і [[Теорія вузлів|теорії вузлів]], ці числа мають також інтерпретацію в [[Теорія графів|теорії графів]]&nbsp;— вони дають число [[Парування (теорія графів)|парувань]] і [[Гамільтонів цикл|гамільтонових циклів]] в деяких родинах [[Граф (математика)|графів]].

== Формули ==
Нехай <math>M_n</math> позначає кількість розсаджування для ''n'' пар. Тушар перший отримав формулу:

<math>M_n = 2 \cdot n! \sum_{k=0}^n (-1)^k \frac{2n}{2n-k} {2n-k\choose k} (n-k)!</math>

яка тепер носить його ім'я. Існує безліч робіт з доказами формули Тушара і її узагальнень, в яких частинам пар дозволяється сидіти поруч. Інша формула, {{нп|Тіньове обчислення|тіньовим образом|en|Umbral calculus}} виражає <math>M_n</math> через [[Поліноми Чебишова|многочлени Чебишева першого роду]], дана Вайманом і Мозером.

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

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

<math>A_n=\sum_{k=0}^n (-1)^k \frac{2n}{2n-k} {2n-k\choose k} (n-k)!</math>

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

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

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

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

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

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

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

== Графові інтерпретації ==
[[Файл:Crown_graphs.svg|міні|303x303пкс|[[Корона (теорія графів)|Корони]] з шістьма, вісьма і десятьма вершинами. Зовнішній цикл кожного графу утворює гамільтонів цикл, але графи з вісьмома і десятьма вершинами мають ще інші гамільтонові цикли.]]
Розсаджування подружніх пар можна інтерпретувати в термінах [[Теорія графів|теорії графів]] як орієнтовані [[Гамільтонів граф|гамільтонові цикли]] в [[Корона (теорія графів)|графі корона]]. Корона виходить видаленням [[Парування (теорія графів)|досконалого парування]] з повного двочасткового графу {{Math}}''K''<sub>''n'',''n''</sub>. Вона має ''2 · n'' вершин двох кольорів, і кожна вершина з'єднана з усіма ребрами іншого кольору, за винятком однієї вершини. У задачі про подружні пари вершини представляють чоловіків і жінок, а ребра представляють пари чоловіків і жінок, які можуть сидіти поруч. Цей граф виходить з повного [[Двочастковий граф|двочасткового графу]] видаленням досконалого парування, де ребра з'єднують подружні пари. Будь-яке правильне розсаджування пар можна описати послідовністю вершин, що являє собою [[гамільтонів цикл]] в [[Граф (математика)|графі]]. Однак, два гамільтонових цикла вважаються еквівалентними, якщо вони з'єднують ті ж вершини в тому ж порядку, незалежно від початкової точки, в той час як у завданні про подружні пари початкова позиція істотна&nbsp;— якщо, як у випадку з чаюванням [[Аліса у Дивокраї|Аліси]], всі гості зрушили б на одне сидіння, це було б зовсім інше розсаджування, хоча і є тим же циклом з точки зору [[Теорія графів|теорії графів]]. Таким чином, число орієнтованих гамільтонових циклів в короні менше на множник ''2n'' в порівнянні з числом розсаджування, але більше на множник <math>(n-1)!</math> в порівнянні з числами розсаджування. Послідовність числа циклів в таких графах (як і раніше, починаючи з ''n'' = 3):

: 2, 12, 312, 9600, 416 880, 23 879 520, 1 749 363 840, … (послідовність [[oeis:A094047|A094047]] в [[OEIS]]).

Можливе й інший опис завдання про подружні пари в термінах теорії графів. Якщо розсадити жінок, можливі розсаджування чоловіків можна описати як вчинені парування в графі, утвореному видаленням одного гамільтонового циклу з повного двочасткового графу. Граф має ребра, що з'єднують вільні місця з чоловіками, а видалення циклу відповідає забороні чоловікові сидіти на місцях, сусідніх з їхніми дружинами. Кількість парувань в двочастковому графі, а тому і кількість розсаджувань, може бути обчислено як [[перманент]] деякої 0-1 [[Матриця (математика)|матриці]]. Більш того, для завдання про подружніх парах ця матриця є [[циркулянт]].

== Зв'язок з теорією вузлів ==
Причина, яка спонукала Тета вивчати завдання про подружні пари, прийшла зі спроб знайти повний список [[Вузол (математика)|математичних вузлів]] із заданим [[Число перетинів (теорія вузлів)|числом перетинів]], скажімо, ''n''. У позначеннях Довкера для діаграм вузлів, ранню форму яких використовував Тет, ''2·n'' точок були перетинами вузла, які пронумеровані уздовж вузла числами від ''1'' до ''2·n''. У скороченій діаграмі дві мітки перетину не можуть бути послідовними числами, так що безліч пар міток на кожному перетині, використаних в позначеннях Довкера для позначення вузла, можна розуміти як зроблене парування в графі, що має в якості вершин числа від ''1'' до ''2·n'' і ребра між кожною парою чисел, що мають різну парність і не йдуть підряд по модулю ''2n''. Цей граф утворюється видаленням [[Гамільтонів цикл|гамільтонового циклу]] (який з'єднує послідовні числа) з повного [[Двочастковий граф|двочасткового графу]] (який з'єднує пари чисел з різною парністю). Таким чином, число парувань в такому графі дорівнює числу розсаджування. Для вузлів які чергуються цього парування досить для опису діаграми вузла. Для інших вузлів необхідно вказувати плюс або мінус для кожного перетину, щоб описати, яка з двох ниток перетину лежить зверху.

Однак завдання перерахування вузлів має додаткові симетрії, не присутні в завданню про подружні пари&nbsp;— якщо почати з іншого перетину, отримаємо інший запис Довкера і всі ці записи повинні вважатися поданням тієї ж самої діаграми. З цих причин два парування, що відрізняються тільки [[Цикл (математика)|циклічною перестановкою]], слід вважати еквівалентними і повинні враховуватися тільки один раз. Гільберт вирішив цю задачу, показавши, що кількість різних парувань даються послідовністю:

: 1, 2, 5, 20, 87, 616, 4843, 44 128, 444 621, … (послідовність [[oeis:A002484|A002484]] в [[OEIS]]).

== Див. також ==
* [[Задача Обервольфаха]]&nbsp;— інша математична задача про розташування відвідувачів за столами.

== Література ==
{{refbegin|colwidth=30em}}
* {{статья
 | doi = 10.2307/2323022
 | автор = Kenneth P. Bogart, Peter G. Doyle
 | выпуск = 7
 | издание = [[American Mathematical Monthly]]
 | mr = 0856291
 | страницы = 514—519
 | заглавие = Non-sexist solution of the ménage problem
 | url = http://www.math.dartmouth.edu/~doyle/docs/menage/menage/menage.html
 | том = 93
 | год = 1986
 | jstor = 2323022
 | ref = Bogart, Doyle
}}
* {{статья
 | автор = Nguyen-Huu Bong
 | doi = 10.1080/0020739980290502
 | выпуск = 5
 | издание = International Journal of Mathematical Education in Science and Technology
 | mr = 1649926
 | страницы = 647—661
 | заглавие = Lucas numbers and the menage problem
 | том = 29
 | год = 1998
 | ref = Bong
}}
* {{статья
 | автор = E. Rodney Canfield, Nicholas C. Wormald
 | doi = 10.1016/0012-365X(87)90002-1
 | выпуск = 2–3
 | издание = [[Discrete Mathematics (journal)|Discrete Mathematics]]
 | mr = 0885491
 | страницы = 117—129
 | заглавие = Ménage numbers, bijections and P-recursiveness
 | том = 63
 | год = 1987
 | ref = Canfield, Wormald
}}.
* {{книга
 | автор = Heinrich Dörrie
 | вклад = Lucas' Problem of the Married Couples
 | isbn = 978-0-486-61348-2
 | страницы = 27—33
 | издательство = Dover
 | заголовок = 100 Great Problems of Elementary Mathematics
 | год = 1965
 | ref = Dörrie
}}.
* {{статья
 | doi = 10.1007/BF03025785
 | автор = Jacques Dutka
 | издание = [[The Mathematical Intelligencer]]
 | mr = 0846991
 | страницы = 18—33
 | заглавие = On the problème des ménages
 | выпуск = 3
 | том = 8
 | год = 1986
 | ref = Dutka
}}
* {{статья
 | last1 = Peter Eades, Cheryl E. Praeger, Jennifer R. Seberry
 | издание = Utilitas Mathematica
 | mr = 0703136
 | страницы = 145—159
 | заглавие = Some remarks on the permanents of circulant (0,1) matrices
 | том = 23
 | год = 1983
 | ref = Eades, Praeger, Seberry
}}
* {{статья
 | автор = E. N. Gilbert
 | издание = [[Scripta Mathematica]]
 | mr = 0090568
 | страницы = 228—233
 | заглавие = Knots and classes of ménage permutations
 | том = 22
 | год = 1956
 | ref = Gilbert
}}
* {{статья
 | автор = James Gleick
 | date = October 28, 1986
 | год = 1986
 | издание = [[New York Times]]
 | заглавие = Math + Sexism: A Problem
 | url = https://query.nytimes.com/gst/fullpage.html?sec=health&res=9A0DEEDB153BF93BA15753C1A960948260
 | ref = Gleick
}}
* {{статья
 | doi = 10.4153/CMB-1975-064-6
 | автор = J. R. Henderson
 | выпуск = 3
 | издание = Canadian Mathematical Bulletin
 | mr = 0399127
 | страницы = 353—358
 | заглавие = Permanents of (0,1)-matrices having at most two zeros per line
 | том = 18
 | год = 1975
 | ref = Henderson
}}
* {{статья
 | автор = Lars Holst
 | doi = 10.1016/0167-7152(91)90147-J
 | выпуск = 3
 | издание = Statistics and Probability Letters
 | mr = 1097978
 | страницы = 225—231
 | заглавие = On the ‘problème des ménages’ from a probabilistic viewpoint
 | том = 11
 | год = 1991
 | ref = Holst
}}
* {{статья
 | автор = Irving Kaplansky
 | doi = 10.1090/S0002-9904-1943-08035-4
 | издание = [[Bulletin of the American Mathematical Society]]
 | mr = 0009006
 | страницы = 784—785
 | заглавие = Solution of the problème des ménages
 | выпуск = 10
 | том = 49
 | год = 1943
 | ref = Kaplansky
}}
* {{статья
 | last1 = I. Kaplansky, J. Riordan
 | издание = [[Scripta Mathematica]]
 | mr = 0019074
 | страницы = 113—124
 | заглавие = The problème des ménages
 | том = 12
 | год = 1946
 | ref = Kaplansky, Riordan
}}
* {{статья
 | автор = Arnold Richard Kräuter
 | издание = [[Séminaire Lotharingien de Combinatoire]]
| language = German
 | заглавие = Über die Permanente gewisser zirkulanter Matrizen und damit zusammenhängender Toeplitz-Matrizen
 | url = http://www.mat.univie.ac.at/~slc/opapers/s11kraeu.html
 | том = B11b
 | год = 1984
 | ref = Kräuter
}}
* {{книга
 | автор = Charles-Ange Laisant
 | издание = Bulletin de la Société Mathématique de France
 | страницы = 105—108
 | вклад = Sur deux problèmes de permutations
 | заголовок = Vie de la société
 | url = http://www.numdam.org/item?id=BSMF_1891__19__93_1
 | том = 19
 | год = 1891
 | ref = Laisant
}}
* {{книга
 | автор = Édouard Lucas
 | место = Paris
 | страницы = 491—495
 | издательство = Gauthier-Villars
 | заголовок = Théorie des Nombres
 | год = 1891
 | ref = Lucas
}}
* {{статья
 | автор = [[Мьюр, Томас|Thomas Muir]]
 | издание = Proceedings of the Royal Society of Edinburgh
 | страницы = 382—391
 | заглавие = On Professor Tait's problem of arrangement
 | том = 9
 | год = 1878
 | ref = Muir
}}
* {{статья
 | автор = Thomas Muir
 | издание = Proceedings of the Royal Society of Edinburgh
 | страницы = 187—190
 | заглавие = Additional note on a problem of arrangement
 | том = 11
 | год = 1882
 | ref = Muir
}}
* {{статья
 |автор       = Amanda F. Passmore
 |заглавие = An elementary solution to the ménage problem
 |url              = http://people.umw.edu/~kmelling/URpapers/menage.pdf
 |год           = 2005
 |ref              = Passmore
 |deadlink         = да
 |archiveurl       = https://web.archive.org/web/20060919143759/http://people.umw.edu/~kmelling/URpapers/menage.pdf
 |archivedate      = 2006-09-19
}}
* {{статья
 | автор = John Riordan
 | doi = 10.1215/S0012-7094-52-01904-2
 | издание = Duke Mathematical Journal
 | mr = 0045680
 | страницы = 27—30
 | заглавие = The arithmetic of ménage numbers
 | выпуск = 1
 | том = 19
 | год = 1952
 | ref = Riordan
}}
* {{статья
 | автор = Lajos Takács
 | doi = 10.1016/S0012-365X(81)80024-6
 | выпуск = 3
 | издание = [[Discrete Mathematics (journal)|Discrete Mathematics]]
 | mr = 0675360
 | страницы = 289—297
 | заглавие = On the “problème des ménages”
 | том = 36
 | год = 1981
 | ref = Takács
}}
* {{статья
 | автор = J. Touchard
 | выпуск = 631—633
 | издание = [[Comptes rendus de l'Académie des sciences|C. R. Acad. Sciences Paris]]
 | заглавие = Sur un problème de permutations
 | том = 198
 | год = 1934
 | ref = Touchard
}}
* {{статья
 | last1 = Max Wyman, Leo Moser
 | выпуск = 3
 | издание = Canadian Journal of Mathematics
 | mr = 0095127
 | страницы = 468—480
 | заглавие = On the problème des ménages
 | том = 10
 | год = 1958
 | ref = Wyman, Moser
 | doi = 10.4153/CJM-1958-045-6
}}
{{refend}}

[[Категорія:Перестановка]]
[[Категорія:Теорія вузлів]]
[[Категорія:Рекурентні співвідношення]]
[[Категорія:1891 у науці]]