Menage problem - Ménage problem

Stół z dziesięcioma nakryciami. Istnieje 3120 różnych sposobów, w jakie pięć par damsko-męskich może usiąść przy tym stole, tak że mężczyźni i kobiety na przemian i nikt nie siedzi obok partnera.

W kombinatorycznych matematyki The Problem ménage lub problème des ménages prosi o wiele różnych sposobów, w których jest to możliwe, aby pomieścić komplet męski-żeński pary przy okrągłym stołem tak, że mężczyźni i kobiety na przemian i nikt nie siedzi obok niego lub jej partner. Problem ten został sformułowany w 1891 roku przez Édouarda Lucasa i niezależnie, kilka lat wcześniej, przez Petera Guthrie Taita w związku z teorią węzłów . Dla liczby par równej 3, 4, 5, ... liczba miejsc siedzących wynosi

12, 96, 3120, 115200, 5836320, 382072320, 31488549120, ... (sekwencja A059375 w OEIS ).

Matematycy opracowali formuły i równania rekurencyjne do obliczania tych liczb i powiązanych sekwencji liczb. Wraz z ich zastosowaniem w teorii etykiety i teorii węzłów, liczby te mają również interpretację teoretyczną grafów : zliczają liczby dopasowań i cykli Hamiltona w pewnych rodzinach grafów.

Formuła Toucharda

Niech M _n oznacza liczbę rozmieszczeń dla n par. Touchard (1934) wyprowadził formułę

${\ Displaystyle M_ {n} = 2 \ cdot n! \ suma _ {k = 0} ^ {n} (-1) ^ {k} {\ Frac {2n} {2n-k}} {2n-k \ wybierz k}(nk)!.}$

Wiele późniejszych prac poświęcono alternatywnym dowodom tej formuły i różnym uogólnionym wersjom problemu.

Innym Umbral formuła M _n udziałem Czebyszewa wielomianów pierwszego rodzaju podano w Wyman i Moser (1958) .

Liczby Menage i rozwiązania dla pań

Jest 2× n ! sposoby sadzania kobiet: są dwa zestawy siedzeń, które można ustawić dla kobiet, i jest n ! sposoby sadzania ich na określonym zestawie siedzeń. Dla każdego układu siedzeń dla kobiet są

${\ Displaystyle A_ {n} = \ suma _ {k = 0} ^ {n} (-1) ^ {k} {\ Frac {2n} {2n-k}} {2n-k \ wybierz k} (nk )!}$

sposoby sadzania mężczyzn; ta formuła po prostu pomija 2× n ! współczynnik ze wzoru Toucharda. Wynikowe mniejsze liczby (ponownie, zaczynając od n  = 3),

1, 2, 13, 80, 579, 4738, 43387, 439792, ... (sekwencja A000179 w OEIS )

nazywane są numerami menażowymi . Czynnik jest kilka sposobów formowania k nie zachodzące na siebie sąsiadujących par miejsc lub równoważnie liczba skojarzeń z k krawędzi w wykres cyklu z 2 n wierzchołków. Wyrażenie na A _n jest bezpośrednim rezultatem zastosowania zasady włączenia-wykluczenia do układów, w których osoby siedzące na końcach każdej krawędzi dopasowania muszą być parą. ${\ Displaystyle {\ Frac {2n} {2n-k}} {2n-k \ wybierz k}}$

Do czasu pracy Bogarta i Doyle'a (1986) rozwiązania problemu menażowego przybierały formę najpierw znalezienia wszystkich ustawień miejsca siedzącego dla kobiet, a następnie policzenia, dla każdego z tych częściowych układów siedzeń, liczby sposobów jego uzupełnienia poprzez posadzenie mężczyźni z dala od swoich partnerów. Bogart i Doyle argumentowali, że wzór Toucharda można wyprowadzić bezpośrednio, biorąc pod uwagę wszystkie ustawienia miejsc siedzących jednocześnie, a nie wykluczając udział kobiet. Jednak Kirousis i Kontogeorgiou (2018) znaleźli jeszcze prostsze rozwiązanie opisane powyżej, wykorzystując kilka pomysłów Bogarta i Doyle'a (chociaż zadbali o przekształcenie argumentacji w języku niepłciowym).

Liczby menażowe spełniają relację powtarzalności

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

i prostsze czterookresowe nawroty

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

z którego można łatwo obliczyć same numery menażowe.

Interpretacje grafowo-teoretyczne

Wykresy koron z sześcioma, ośmioma i dziesięcioma wierzchołkami. Zewnętrzny cykl każdego wykresu tworzy cykl Hamiltona; wykresy ośmio- i dziesięciowierzchołkowe mają również inne cykle hamiltonowskie.

Rozwiązania problemu menażowego można interpretować w kategoriach teorii grafów , jako ukierunkowane cykle hamiltonowskie w grafach koronowych . Wykres korony tworzy się przez usunięcie idealnego dopasowania z kompletnego grafu dwudzielnego K _n,n ; ma 2 n wierzchołków dwóch kolorów, a każdy wierzchołek jednego koloru jest połączony ze wszystkimi wierzchołkami drugiego koloru oprócz jednego. W przypadku problemu menażowego wierzchołki grafu reprezentują mężczyzn i kobiety, a krawędzie pary kobiet i mężczyzn, którym wolno siedzieć obok siebie. Wykres ten powstaje poprzez usunięcie idealnego dopasowania utworzonego przez pary damsko-męskie z kompletnego wykresu dwudzielnego, który łączy każdego mężczyznę z każdą kobietą. Dowolne prawidłowe rozmieszczenie miejsc siedzących można opisać za pomocą kolejności osób wokół stołu, co tworzy na wykresie cykl hamiltonianu. Jednak dwa cykle hamiltonowskie są uważane za równoważne, jeśli łączą te same wierzchołki w tej samej kolejności cyklicznej, niezależnie od wierzchołka początkowego, podczas gdy w problemie menażowym pozycja wyjściowa jest uważana za znaczącą: jeśli, jak w herbacie Alicji , wszystkie goście przesuwają swoje pozycje o jedno miejsce, uważa się to za inny układ siedzeń, mimo że jest opisany tym samym cyklem. W związku z tym liczba zorientowanych cykli hamiltonowskich w grafie koronowym jest mniejsza o czynnik 2 n od liczby ułożeń osadzenia, ale większa o czynnik ( n  − 1)! niż numery menażowe. Sekwencja liczb cykli na tych wykresach (jak poprzednio, zaczynając od n  = 3) to

2, 12, 312, 9600, 416880, 23879520, 1749363840,... (sekwencja A094047 w OEIS ).

Możliwy jest również drugi opis problemu w teorii grafów. Po zajęciu miejsca siedzącego przez kobiety możliwe układy siedzeń pozostałych mężczyzn można opisać jako idealne dopasowania w grafie utworzonym przez usunięcie pojedynczego cyklu Hamiltona z kompletnego grafu dwudzielnego; wykres ma krawędzie łączące otwarte siedzenia z mężczyznami, a usunięcie cyklu odpowiada zakazowi zajmowania przez mężczyzn jednego z otwartych miejsc sąsiadujących z ich żonami. Problem zliczania dopasowań w grafie dwudzielnym, a zatem a fortiori problem obliczania liczb menażowych, można rozwiązać za pomocą stałych pewnych macierzy 0-1 . W przypadku problemu zarządzania macierzą wynikającą z tego spojrzenia na problem jest macierz cyrkulacyjna, w której wszystkie oprócz dwóch sąsiadujących elementów rzędu generującego są równe 1 .

Teoria węzłów

Motywacja Taita do studiowania problemu menażowego wynikała z próby znalezienia pełnej listy węzłów matematycznych o określonej liczbie skrzyżowań , powiedzmy n . W notacji Dowkera dla diagramów węzłów, której wczesna forma została użyta przez Taita, 2 n punktów, w których węzeł przecina się w kolejności wzdłuż węzła, są oznaczone 2 n liczbami od 1 do 2 n . Na diagramie skróconym dwie etykiety na skrzyżowaniu nie mogą następować po sobie, więc zestaw par etykiet na każdym skrzyżowaniu, używany w notacji Dowkera do reprezentowania węzła, może być interpretowany jako idealne dopasowanie w grafie, który ma wierzchołek dla każdą liczbę z zakresu od 1 do 2 n oraz krawędź pomiędzy każdą parą liczb, która ma różną parzystość i nie są następujące po sobie modulo 2 n . Wykres ten powstaje przez usunięcie cyklu Hamiltona (łączącego kolejne liczby) z kompletnego grafu dwudzielnego (łączącego wszystkie pary liczb o różnej parzystości), a więc ma liczbę dopasowań równą liczbie menażowej. W przypadku węzłów naprzemiennych to dopasowanie wystarczy do opisania samego diagramu węzła; w przypadku innych węzłów należy określić dodatkowy znak dodatni lub ujemny dla każdej pary krzyżujących się, aby określić, która z dwóch nici krzyżowania leży nad drugą nitką.

Jednak problem z listą sęków ma pewne dodatkowe symetrie, nieobecne w problemie połączenia: otrzymuje się różne notacje Dowkera dla tego samego schematu węzła, jeśli zaczyna się etykietowanie w innym punkcie przecięcia, a wszystkie te różne notacje powinny być liczone jako reprezentujące to samo diagram. Z tego powodu dwa dopasowania, które różnią się od siebie permutacją cykliczną, należy traktować jako równoważne i liczyć tylko raz. Gilbert (1956) rozwiązał ten zmodyfikowany problem wyliczenia, pokazując, że liczba różnych dopasowań wynosi

1, 2, 5, 20, 87, 616, 4843, 44128, 444621, ... (sekwencja A002484 w OEIS ).

Zobacz też

• Problem Oberwolfach , inny problem matematyczny polegający na rozmieszczeniu gości przy stołach
• Problème des rencontres , podobny problem dotyczący częściowych zaburzeń

Uwagi

Bibliografia

Zewnętrzne linki

• Weisstein, Eric W. „Problem małżeństw” . MatematykaŚwiat .
• Weisstein, Eric W. „Formuła nawrotu Laisanta” . MatematykaŚwiat .