Problemet med gifta par

Inom kombinatoriken frågar problemet med gifta par eller problemet med gäster ( eng.  ménage problem , fr.  problème des ménages ) hur många olika sätt kan gifta par sitta vid ett runt bord så att personer av samma kön inte sitter vid sidan av vid sidan av, och inte heller satt några makar på de intilliggande platserna.

Problemet formulerades 1891 av Eduard Luca och ansågs självständigt flera år tidigare av Peter Tat i samband med knutteorin [1] . För antalet par 3, 4, 5, ... är det önskade antalet sittsätt lika med

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

Explicita och återkommande formler finns för antalet sittmetoder . Förutom att användas i etikett- och knutteori har dessa siffror också en tolkning inom grafteorin - de ger antalet matchningar och Hamilton-cykler i vissa graffamiljer.

Formler

Låt M n beteckna antalet sittplatser för n par. Tushar [2] var den första som fick formeln:

nu bär hans namn. Det finns många verk med bevis på Touchard-formeln och dess generaliseringar, där delar av paren får sitta sida vid sida.

En annan formel som uttrycker M n på ett skuggsätt i termer av Chebyshev-polynom av det första slaget ges av Wyman och Moser [3] .

Antal sittplatser och tillvägagångssättet "damerna först"

Före arbetet med Bugart och Doyle [4] genomfördes lösningen av problemet med gifta par genom att först placera damerna och sedan räkna antalet herrar där man och hustru inte satt sida vid sida. Emellertid visade Bugart och Doyle att Touchards formel kan härledas direkt, utan föregående sittande av damerna [5] .

Damer kan sitta 2 n ! sätt, eftersom det finns 2 alternativ för att välja en uppsättning platser och n ! sätt att sitta på utvalda platser. För varje sittsätt finns det

sätt att sitta herrar, som skiljer sig från Touchards formel bara med en faktor 2 · n ! . Denna formel låter dig få en sekvens av antalet sittande par (som börjar med n = 3 ):

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

Det uppfyller det rekursiva förhållandet : [6]

och en enklare återfallsrelation: [7]

som gör det enkelt att beräkna antalet sittplatser.

Graftolkningar

Sittplatserna för gifta par kan tolkas i termer av grafteori som riktade Hamiltonska cykler i krongrafen . Kronan erhålls genom att ta bort en perfekt matchning från den kompletta tvådelade grafen K n , n . Den har 2 n hörn av två färger, och varje vertex är ansluten till alla kanter av den andra färgen, förutom en vertex. I parproblemet representerar hörn hanar och honor, och kanter representerar par av hanar och honor som kan sitta sida vid sida. Denna graf erhålls från en komplett tvådelad graf genom att ta bort en perfekt matchning där kanter förbinder par av makar. Varje korrekt placering av par kan beskrivas av en sekvens av hörn, som är en Hamiltonsk cykel i en graf. Två Hamiltonska cykler anses dock vara likvärdiga om de kopplar samman samma hörn i samma ordning, oavsett utgångspunkt, medan utgångsläget i det gifta parets problem är betydande - om, som i fallet med Alices tebjudning , alla gästerna skulle flytta på en plats, det skulle vara en helt annan sittplats, även om det är samma cykel ur grafteorinsynpunkt. Således är antalet orienterade Hamilton-cykler i kronan mindre med en faktor 2 n jämfört med antalet sittplatser [8] , men fler med en faktor på ( n -1)! jämfört med antalet sittplatser. Sekvensen av antalet cykler i sådana grafer (som tidigare, med start från n =3 )

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

En annan beskrivning av problemet med gifta par i termer av grafteori är också möjlig. Om kvinnorna sitter, kan de möjliga sittplatserna för männen beskrivas som perfekta matchningar i grafen som bildas genom att ta bort en Hamilton-cykel från en komplett tvådelad graf. Grafen har kanter som förbinder tomma platser med män, och borttagandet av cykeln motsvarar förbudet för män att sitta i sätena intill sina makar. Antalet matchningar i en tvådelad graf, och därmed antalet platser, kan beräknas som en permanent av någon 0-1 matris . Dessutom, för problemet med gifta par, är denna matris en cirkulerande [9] .

Samband med knutteori

Anledningen som fick Theta att studera problemet med gifta par kom från att försöka hitta en komplett lista över matematiska knutar med ett givet antal skärningspunkter , säg n . I Dowkers notation för knutdiagram, en tidig form av vilken Tet använde, var de 2 n punkterna knutskärningar, som är numrerade längs knuten med nummer från 1 till 2 n . I det reducerade diagrammet kan två skärningsetiketter inte vara på varandra följande siffror, så uppsättningen av etikettpar vid varje korsning, som används i Dowker-notation för att beteckna en nod, kan förstås som en perfekt matchning i en graf med siffror från 1 till 2 n som hörn och kanter mellan varje par av tal som har olika paritet och inte är 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 par av tal med olika paritet). Således är antalet matchningar i en sådan graf lika med antalet sittarrangemang. För alternerande knutar räcker denna matchning för att beskriva knutdiagrammet. För andra noder måste ett plus eller minus anges för varje korsning för att beskriva vilken av korsningens två trådar som ligger överst.

Dock har knutuppräkningsproblemet ytterligare symmetrier som inte finns i problemet med gifta par - om vi utgår från en annan korsning får vi en annan Dowker-notation, och alla dessa notationer bör betraktas som representationer av samma diagram. Av dessa skäl bör två matchningar som endast skiljer sig åt i cyklisk permutation betraktas som likvärdiga och bör endast räknas en gång. Hilbert [10] löste detta problem genom att visa att antalet distinkta matchningar ges av sekvensen:

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

Anteckningar

  1. ↑ Dutka, 1986 .
  2. ↑ Touchard, 1934 .
  3. ↑ Wyman, Moser, 1958 .
  4. ↑ Bogart, Doyle, 1986 .
  5. ↑ Gleick, 1986 .
  6. ↑ Muir, 1882 ; Laisant, 1891 . Något mer komplexa återkommande formler har beskrivits tidigare av Cayley och 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 .

Litteratur

Länkar