Problém manželských párů

V kombinatorice se problém manželských párů nebo problém hostů ( eng.  ménage problem , fr.  problème des ménages ) ptá , kolika různými způsoby mohou být manželské páry usazeny u kulatého stolu , aby vedle sebe neseděli osoby stejného pohlaví . vedle sebe a také žádný pár manželů neseděl na sousedních místech.

Problém formuloval v roce 1891 Eduard Luca a o několik let dříve se samostatně zabýval Peter Tat v souvislosti s teorií uzlů [1] . Pro počet párů 3, 4, 5, ... je požadovaný počet způsobů sezení roven

12, 96, 3120, 115200 , 5836320 , 382072320 , 31488549120 , … (sekvence A059375 v OEIS ).

Pro počet způsobů sezení lze nalézt explicitní a opakující se vzorce . Kromě toho, že se používají v etiketě a teorii uzlů , mají tato čísla také výklad v teorii grafů - dávají počet shod a Hamiltonovské cykly v některých rodinách grafů.

Vzorce

Nechť M n označuje počet uspořádání sedadel pro n párů. Tushar [2] byl první, kdo získal vzorec:

nyní nese jeho jméno. Existuje mnoho prací s důkazy Touchardova vzorce a jeho zobecnění, v nichž části dvojic mohou sedět vedle sebe.

Další formuli vyjadřující M n stínově pomocí Čebyševových polynomů prvního druhu uvádí Wyman a Moser [3] .

Počet uspořádání sedadel a přístup „na prvním místě dámy“

Před působením Bugarta a Doyla [4] , řešení problému manželských párů probíhalo tak, že se nejprve usadily dámy, poté se spočítaly počty sezení pánů, ve kterých neseděli manželé vedle sebe. Bugart a Doyle však ukázali, že Touchardův vzorec lze odvodit přímo, bez předchozího usazení dam [5] .

Dámy mohou sedět 2 n ! způsoby, protože existují 2 možnosti pro výběr sady míst a n ! způsoby sezení na vybraných místech. Pro každý způsob sezení existuje

způsoby sezení pánové, který se od Touchardova vzorce liší jen faktorem 2 · n ! . Tento vzorec vám umožňuje získat posloupnost počtu párů sedadel (počínaje n = 3 ):

1, 2, 13, 80, 579, 4738, 43387 , 439792 , … (sekvence A000179 v OEIS ).

Splňuje rekurzivní vztah : [6]

a jednodušší vztah opakování: [7]

které usnadňují výpočet počtu dvojic sedadel.

Interpretace grafů

Uspořádání sedadel manželských párů lze interpretovat z hlediska teorie grafů jako řízené hamiltonovské cykly v korunovém grafu . Koruna se získá odstraněním dokonalé shody z úplného bipartitního grafu Kn , n . Má 2 n vrcholů dvou barev a každý vrchol je spojen se všemi hranami druhé barvy, kromě jednoho vrcholu. V párovém problému představují vrcholy muže a ženy a hrany představují páry mužů a žen, které mohou sedět vedle sebe. Tento graf je získán z úplného bipartitního grafu odstraněním dokonalé shody tam, kde hrany spojují páry manželů. Každé správné usazení párů lze popsat posloupností vrcholů, což je hamiltonovský cyklus v grafu. Dva hamiltonovské cykly jsou však považovány za ekvivalentní, pokud spojují stejné vrcholy ve stejném pořadí, bez ohledu na výchozí bod, zatímco v problému manželského páru je výchozí pozice významná - pokud, jako v případě Alice's tea party , všechny hosté by se pohybovali na jednom sedadle, bylo by to úplně jiné sezení, byť jde z pohledu teorie grafů o stejný cyklus. Počet orientovaných hamiltonovských cyklů v koruně je tedy menší o faktor 2 n ve srovnání s počtem sezení [8] , ale více o faktor ( n -1)! v porovnání s počtem sedadel. Posloupnost počtu cyklů v takových grafech (jako dříve, počínaje n = 3 )

2, 12, 312, 9600, 416880 , 23879520 , 1749363840 , … (sekvence A094047 v OEIS ).

Je možný i jiný popis problému manželských párů z hlediska teorie grafů. Pokud sedí ženy, možná místa usazení mužů lze popsat jako dokonalé shody v grafu vytvořeném odstraněním jednoho hamiltonovského cyklu z kompletního bipartitního grafu. Graf má hrany spojující prázdná sedadla s muži a odstranění cyklu odpovídá zákazu mužů sedět na místech sousedících s jejich manželi. Počet shod v bipartitním grafu, a tedy i počet sezení, lze vypočítat jako permanent nějaké matice 0-1 . Navíc pro problém manželských párů je tato matrice cirkulantem [9] .

Spojení s teorií uzlů

Důvod, který vedl Thetu ke studiu problému manželského páru, pochází ze snahy najít úplný seznam matematických uzlů s daným počtem průsečíků , řekněme n . V Dowkerově notaci pro diagramy uzlů, jejichž ranou formu Tet používal, byly body 2 n průsečíky uzlů, které jsou číslovány podél uzlu čísly od 1 do 2 n . Ve zmenšeném diagramu nemohou být dvě značky průniku po sobě jdoucí čísla, takže množinu dvojic značek na každém průsečíku, používanou v Dowkerově notaci k označení uzlu, lze chápat jako dokonalou shodu v grafu s čísly od 1 do 2 n jako vrcholy a hrany mezi každou dvojicí čísel, které mají různou paritu a nejsou po sobě jdoucí modulo 2 n . Tento graf je vytvořen odstraněním hamiltonovského cyklu (spojování po sobě jdoucích čísel) z úplného bipartitního grafu (spojování dvojic čísel s různou paritou). Počet shod v takovém grafu se tedy rovná počtu uspořádání sedadel. Pro střídavé uzly toto párování stačí k popisu diagramu uzlů. U ostatních uzlů musí být pro každý průsečík specifikováno plus nebo mínus, aby se popsalo, které ze dvou vláken průsečíku leží nahoře.

Problém výčtu uzlů má však další symetrie, které nejsou přítomny v problému manželských párů – pokud začneme z jiného průsečíku, dostaneme jiný Dowkerův zápis a všechny tyto zápisy by měly být považovány za reprezentace stejného diagramu. Z těchto důvodů by dvě shody, které se liší pouze cyklickou permutací , měly být považovány za ekvivalentní a měly by být započítány pouze jednou. Hilbert [10] vyřešil tento problém tím, že ukázal, že počet odlišných shod je dán posloupností:

1, 2, 5, 20, 87, 616, 4843, 44128 , 444621 , … (sekvence A002484 v OEIS ).

Poznámky

  1. ↑ Dutka, 1986 .
  2. ↑ Touchard, 1934 .
  3. ↑ Wyman, Moser, 1958 .
  4. ↑ Bogart, Doyle, 1986 .
  5. ↑ Gleick, 1986 .
  6. ↑ Muir, 1882 ; Laisant, 1891 . Poněkud složitější opakující se vzorce již dříve popsali Cayley a Muir ( Muir 1878 ).
  7. ↑ Muir, 1882 ; Canfield, Wormald, 1987 .
  8. ↑ Passmore, 2005 .
  9. ↑ Muir, 1878 ; Eades, Praeger, Seberry, 1983 ; Krauter, 1984 ; Henderson, 1975 .
  10. ↑ Gilbert, 1956 .

Literatura

Odkazy