Задача Люка

В комбінаториці задача про подружні пари, задача про гостей, або задача Люка (Шаблон:Lang-en, Шаблон:Lang-fr) запитує, скількома різними способами можна розсадити подружні пари за круглим столом так, щоб особи однієї статі не сиділи поруч, а також щоб ніяка подружня пара не сиділа на сусідніх місцях.

Завдання сформульоване в 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{2 n}{2 n - k} (\binom{2 n - k}{k}) (n - k)!$

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

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

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

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

$A_{n} = \sum_{k = 0}^{n} (- 1)^{k} \frac{2 n}{2 n - k} (\binom{2 n - k}{k}) (n - k)!$

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

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

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

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

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

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

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

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

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

Див. також

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

Література

Шаблон:Refbegin

Шаблон:Refend

Задача Люка

Зміст

Формули

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

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

Зв'язок з теорією вузлів

Див. також

Література

Навігаційне меню

Задача Люка

Формули

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

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

Зв'язок з теорією вузлів

Див. також

Література

Навігаційне меню

Пошук