Ménage problem

Ett bord med tio kuvert. Det finns 3120 olika sätt på vilka fem manliga-kvinnliga par kan sitta vid det här bordet så att män och kvinnor alternerar och ingen sitter bredvid sin partner.

Inom kombinatorisk matematik frågar ménageproblemet eller problème des ménages efter antalet olika sätt på vilka det är möjligt att placera en uppsättning manliga-kvinnliga par vid ett runt matbord så att män och kvinnor växlar och ingen sitter bredvid hans eller hennes partner. ( Ménage är det franska ordet för "hushåll", här syftar på ett manligt-kvinnligt par.) Detta problem formulerades 1891 av Édouard Lucas och oberoende några år tidigare av Peter Guthrie Tait i samband med knutteorin . För ett antal par lika med 3, 4, 5, ... är antalet sittplatser

12, 96, 3120, 115200, 5836320, 382072320, 31488549120, ... (sekvens A059375 i OEIS ).

Matematiker har utvecklat formler och återkommande ekvationer för att beräkna dessa tal och relaterade talföljder . Tillsammans med deras tillämpningar på etikett och knutteori har dessa siffror också en grafteoretisk tolkning: de räknar antalet matchningar och Hamilton-cykler i vissa graffamiljer .

Touchards formel

Låt M _n beteckna antalet sittplatser för n par. Touchard (1934) härledde formeln

M_{n}=2\cdot n!\sum _{k=0}^{n}(-1)^{k}{\frac {2n}{2n-k}}{2n-k \ välj k}(nk)!.

Mycket efterföljande arbete har lagts ner på alternativa bevis för denna formel och på olika generaliserade versioner av problemet.

En annan formel för Mn _som involverar Chebyshev-polynom av första slag gavs av Wyman & Moser (1958) .

Ménage siffror och ladies-first lösningar

Det finns 2× n ! sätt att sitta kvinnorna: det finns två set med sittplatser som kan ordnas för kvinnorna, och det finns n ! sätt att placera dem på en viss uppsättning platser. För varje sittarrangemang för kvinnorna finns

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

sätt att sitta männen; denna formel utelämnar helt enkelt 2× n ! faktor från Touchards formel. De resulterande mindre talen (igen, med början från n = 3),

1, 2, 13, 80, 579, 4738, 43387, 439792, ... (sekvens A000179 i OEIS )

kallas ménagetal . Faktorn ${\frac {2n}{2n-k}}{2n-k \choose k}$ är antalet sätt att bilda $k$ icke-överlappande par av intilliggande säten eller, ekvivalent, antalet matchningar av $k$ kanter i en cykelgraf med $2 n$ hörn . Uttrycket för $A n$ är det omedelbara resultatet av att tillämpa principen om inkludering–uteslutning på arrangemang där personerna som sitter vid ändpunkterna av varje kant av en matchning måste vara ett par.

Bogart & Doyles (1986) arbete tog lösningar på ménageproblemet formen av att man först hittade alla sittplatser för kvinnorna och sedan räknade, för var och en av dessa partiella sittarrangemang, antalet sätt att slutföra det genom att sitta män borta från sina partners. Bogart och Doyle hävdade att Touchards formel kan härledas direkt genom att överväga alla sittplatser på en gång snarare än genom att ta bort kvinnornas deltagande. Kirousis & Kontogeorgiou (2018) hittade dock den ännu enklare ladies-first-lösningen som beskrivs ovan genom att använda sig av några av Bogart och Doyles idéer (även om de passade på att omarbeta argumentet till ett icke-könet språk).

Ménagetalen uppfyller återfallsrelationen

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

och det enklare återfall i fyra perioder

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

varifrån själva ménagetalen lätt kan beräknas.

Grafteoretiska tolkningar

Krona grafer med sex, åtta och tio hörn. Den yttre cykeln av varje graf bildar en Hamiltonsk cykel; de åtta och tio vertexgraferna har också andra Hamilton-cykler.

Lösningar på ménageproblemet kan tolkas i grafteoretiska termer, enligt Hamiltonska cykler i krongrafer . En krona graf bildas genom att ta bort en perfekt matchning från en komplett tvådelad graf K _n,n ; den har 2 n hörn av två färger, och varje hörn i en färg är ansluten till alla utom en av hörn i den andra färgen. När det gäller ménageproblemet representerar grafens hörn män och kvinnor, och kanterna representerar par av män och kvinnor som får sitta bredvid varandra. Den här grafen skapas genom att ta bort den perfekta matchningen som bildas av man-kvinnliga par från en komplett tvådelad graf som förbinder varje man med varje kvinna. Alla giltiga sittarrangemang kan beskrivas av sekvensen av personer i ordning runt bordet, som bildar en Hamiltonsk cykel i grafen. Två Hamilton-cykler anses dock vara likvärdiga om de förbinder samma hörn i samma cykliska ordning oavsett startpunkt, medan i ménageproblemet anses startpositionen vara signifikant: om, som i Alices tebjudning , alla gästerna ändrar sina positioner med en plats, det anses vara ett annat sittarrangemang även om det beskrivs av samma cykel. Därför är antalet orienterade Hamilton-cykler i ett krondiagram mindre med en faktor på 2 n än antalet sittplatser, men större med en faktor på ( n − 1)! än ménagenumren. Sekvensen av antalet cykler i dessa grafer (som tidigare, med början vid n = 3) är

2, 12, 312, 9600, 416880, 23879520, 1749363840, ... (sekvens A094047 i OEIS ).

En andra grafteoretisk beskrivning av problemet är också möjlig. När kvinnorna väl har fått plats kan de möjliga sittarrangemangen för de återstående männen beskrivas som perfekta matchningar i en graf som bildas genom att ta bort en enda Hamiltonsk cykel från en komplett tvådelad graf; grafen har kanter som förbinder öppna säten med män, och borttagandet av cykeln motsvarar att förbjuda männen att sitta i någon av de öppna sätena intill sina fruar. Problemet med att räkna matchningar i en tvådelad graf , och därför a fortiori problemet med att beräkna ménagetal, kan lösas med hjälp av permanenterna för vissa 0-1-matriser . När det gäller ménageproblemet matrisen som härrör från denna syn på problemet den cirkulerande matrisen där alla utom två angränsande element i den genererande raden är lika med 1.

Knutteori

Taits motivation för att studera ménageproblemet kom från att försöka hitta en komplett lista över matematiska knutar med ett givet antal korsningar, säg n . I Dowker-notation för knutdiagram, vars tidig form användes av Tait, är de 2 n punkterna där en knut korsar sig själv, i följd längs knuten, märkta med de 2 n talen från 1 till 2 n . I ett reducerat diagram kan de två etiketterna vid en korsning inte vara på varandra följande, så uppsättningen av etikettpar vid varje korsning, som används i Dowker-notation för att representera knuten, kan tolkas som en perfekt matchning i en graf som har en vertex för varje tal i intervallet från 1 till 2 n och en kant mellan varje par av tal som har olika paritet och är icke-konsekutiva modulo 2 n . Denna graf bildas genom att ta bort en Hamiltonsk cykel (förbinder på varandra följande tal) från en komplett tvådelad graf (förbinder alla par av tal med olika paritet), och så har den ett antal matchningar lika med ett ménagetal. För alternerande knutar räcker denna matchning för att beskriva själva knutdiagrammet; för andra knutar måste ytterligare ett positivt eller negativt tecken anges för varje korsande par för att avgöra vilken av korsningens två trådar som ligger ovanför den andra tråden.

Emellertid har knutlistningsproblemet några ytterligare symmetrier som inte finns i ménageproblemet: man får olika Dowker-notationer för samma knutdiagram om man börjar märkningen vid en annan korsningspunkt, och dessa olika notationer ska alla räknas som representerande samma diagram. Av denna anledning bör två matchningar som skiljer sig från varandra genom en cyklisk permutation behandlas som likvärdiga och endast räknas en gång. Gilbert (1956) löste detta modifierade uppräkningsproblem och visade att antalet olika matchningar är

1, 2, 5, 20, 87, 616, 4843, 44128, 444621, ... (sekvens A002484 i OEIS ).

Se även

Oberwolfach problem , ett annorlunda matematiskt problem som involverar arrangemang av matgäster vid bord
Problème des rencontres , ett liknande problem som involverar partiella störningar

Anteckningar

Bogart, Kenneth P.; Doyle, Peter G. (1986), "Non-sexist solution of the ménage problem" , American Mathematical Monthly , 93 (7): 514–519, doi : 10.2307/2323022 , JSTOR 2323022 , MR 085629 .
Bong, Nguyen-Huu (1998), "Lucas numbers and the menage problem", International Journal of Mathematical Education in Science and Technology , 29 (5): 647–661, doi : 10.1080/0020739980290502 , MR 1649926 .
Canfield, E. Rodney; Wormald, Nicholas C. (1987), "Ménage numbers, bijections and P-recursiveness", Discrete Mathematics , 63 (2–3): 117–129, doi : 10.1016/0012-365X(87) 90002-1 , 8549108 .
Dörrie, Heinrich (1965), "Lucas' Problem of the Married Couples", 100 Great Problems of Elementary Mathematics , Dover, s. 27–33, ISBN 978-0-486-61348-2 . Översatt av David Antin.
Dutka, Jacques (1986), "On the problème des ménages", The Mathematical Intelligencer , 8 (3): 18–33, doi : 10.1007/BF03025785 , MR 0846991 , S2CID 116433056 .
Eades, Peter ; Praeger, Cheryl E .; Seberry, Jennifer R. (1983), "Some remarks on the permanents of circulant (0,1) matrices", Utilitas Mathematica , 23 : 145–159, MR 0703136 .
Gilbert, EN (1956), "Knutar och klasser av ménage-permutationer", Scripta Mathematica , 22 : 228–233, MR 0090568 .
Gleick, James (28 oktober 1986), "Math + Sexism: A Problem", New York Times .
Henderson, JR (1975), "Permanenter av (0,1)-matriser med högst två nollor per rad", Canadian Mathematical Bulletin , 18 (3): 353–358, doi : 10.4153/CMB-1975-064-6 MR 0399127 . _
Holst, Lars (1991), "On the 'problème des ménages' from a probabilistic viewpoint", Statistics and Probability Letters , 11 (3): 225–231, doi : 10.1016/0167-7152(91)90147-J , MR 1097978 .
Kaplansky, Irving (1943), "Solution of the problème des ménages", Bulletin of the American Mathematical Society , 49 (10): 784–785, doi : 10.1090/S0002-9904-1943-08035-00 , 9005-6 00 .
Kaplansky, Irving ; Riordan, J. (1946), "The problème des ménages", Scripta Mathematica , 12 : 113–124, MR 0019074 .
Kirousis, L.; Kontogeorgiou, G. (2018), "102.18 The problème des ménages revisited", Mathematical Gazette , 102 (553): 147–149, arXiv : 1607.04115 , doi : 10.1017 / mag.270 .7C The
Kräuter, Arnold Richard (1984), "Über die Permanente gewisser zirkulanter Matrizen und damit zusammenhängender Toeplitz-Matrizen" , Séminaire Lotharingien de Combinatoire (på tyska), B11b .
Laisant, Charles-Ange (1891), "Sur deux problèmes de permutations" , Vie de la société, Bulletin de la Société Mathématique de France (på franska), 19 : 105–108 .
Lucas, Édouard (1891), Théorie des Nombres , Paris: Gauthier-Villars, s. 491–495 .
Muir, Thomas (1878), "On Professor Taits problem of arrangement" , Proceedings of the Royal Society of Edinburgh , 9 : 382–391, doi : 10.1017/S0370164600032557 . Inkluderar (sid. 388–391) ett tillägg av Arthur Cayley .
Muir, Thomas (1882), "Extra anmärkning om ett problem med arrangemang", Proceedings of the Royal Society of Edinburgh , 11 : 187–190 .
Passmore, Amanda F. (2005), En elementär lösning på ménageproblemet , CiteSeerX 10.1.1.96.8324 .
Riordan, John (1952), "The aritmetic of ménage numbers", Duke Mathematical Journal , 19 (1): 27–30, doi : 10.1215/S0012-7094-52-01904-2 , MR 0045680 .
Takács, Lajos (1981), "On the "problème des ménages" ", Discrete Mathematics , 36 (3): 289–297, doi : 10.1016/S0012-365X(81)80024-6 , MR 067536 .
Touchard, J. (1934), "Sur un problème de permutations" , CR Acad. Sci. Paris , 198 (631–633) .
Wyman, Max; Moser, Leo (1958), "On the problème des ménages", Canadian Journal of Mathematics , 10 (3): 468–480, doi : 10.4153/cjm-1958-045-6 , MR 0095127 .

externa länkar