Avioparien ongelma

Kombinatoriikassa avioparien ongelma tai vieraiden ongelma ( eng.  ménage problem , fr.  problème des ménages ) kysyy , kuinka monella eri tavalla avioparit voidaan istua pyöreän pöydän ääreen , jotta samaa sukupuolta olevat eivät istu vierekkäin vierekkäin, eikä myöskään yksikään puolisopari istunut viereisillä istuimilla.

Eduard Luca muotoili ongelman vuonna 1891, ja Peter Tat käsitteli sitä itsenäisesti useita vuosia aikaisemmin solmuteorian yhteydessä [ 1] . Parien lukumäärälle 3, 4, 5, ... haluttu istumamenetelmien lukumäärä on yhtä suuri kuin

12, 96, 3120, 115200 , 5836320 , 382072320 , 31488549120 , … (sekvenssi A059375 OEIS : ssä ).

Istumamenetelmien lukumäärälle löytyy eksplisiittiset ja toistuvat kaavat . Sen lisäksi, että niitä käytetään etiketti- ja solmuteoriassa , näillä numeroilla on myös tulkinta graafiteoriassa - ne antavat osuuksien ja Hamiltonin syklien määrän joissakin graafiperheissä .

Kaavat

Olkoon M n istumajärjestyksen lukumäärä n parille. Tushar [2] oli ensimmäinen, joka sai kaavan:

kantaa nyt hänen nimeään. On monia teoksia, joissa on todisteita Touchard-kaavasta ja sen yleistyksistä, joissa parien osien sallitaan istua vierekkäin.

Toinen kaava , joka ilmaisee M n :n varjotavalla ensimmäisen tyyppisillä Chebyshev-polynomeilla, ovat Wymanin ja Moserin antamat [3] .

Istumajärjestelyjen määrä ja "naiset ensin" -lähestymistapa

Ennen Bugartin ja Doylen [4] työtä avioparien ongelman ratkaisu tehtiin laittamalla ensin naiset istuimiin ja laskemalla sitten herrasmiesten istumapaikat, joissa aviomies ja vaimo eivät istuneet vierekkäin. Bugart ja Doyle osoittivat kuitenkin, että Touchardin kaava voidaan johtaa suoraan ilman naisten etukäteistä istuttamista [5] .

Naiset mahtuu istumaan 2 n ! tavoilla, koska paikkajoukon valitsemiseen on kaksi vaihtoehtoa ja n ! tapoja istua valituissa paikoissa. Jokaiselle istumamenetelmälle on olemassa

herrasmiesten istumistapoja, joka eroaa Touchardin kaavasta vain kertoimella 2 · n ! . Tämän kaavan avulla voit saada sarjan istumaparien lukumäärää (alkaen n = 3 :sta ):

1, 2, 13, 80, 579, 4738, 43387 , 439792 , … (sekvenssi A000179 OEIS : ssä ).

Se täyttää rekursiivisen suhteen : [6]

ja yksinkertaisempi toistuvuussuhde: [7]

joiden avulla on helppo laskea istuinparien lukumäärä.

Kaaviotulkinnat

Avioparien istumajärjestykset voidaan tulkita graafiteorian kannalta suunnattuina Hamiltonin sykleinä kruunugraafissa . Kruunu saadaan poistamalla täydellinen vastaavuus täydellisestä kaksiosaisesta graafista K n , n . Siinä on 2 n kahden värin kärkeä, ja jokainen kärkipiste on yhdistetty toisen värin kaikkiin reunoihin yhtä kärkeä lukuun ottamatta. Pariongelmassa kärjet edustavat miehiä ja naisia, ja reunat edustavat uros- ja naaraspareja, jotka voivat istua vierekkäin. Tämä kaavio saadaan täydellisestä kaksiosaisesta kaaviosta poistamalla täydellinen yhteensopivuus, jossa reunat yhdistävät puolisoiden pareja. Mikä tahansa oikea parien sijoittuminen voidaan kuvata kärkijonolla, joka on Hamiltonin sykli graafissa. Kaksi Hamiltonin sykliä katsotaan kuitenkin ekvivalenttiksi, jos ne yhdistävät samat kärjet samassa järjestyksessä lähtöpisteestä riippumatta, kun taas aviopariongelmassa lähtökohta on merkitsevä - jos, kuten Alicen teekutsuissa , kaikki vieraat liikkuisivat yhdellä istuimella, se olisi täysin erilainen istuin, vaikka se on sama sykli graafiteorian näkökulmasta. Siten orientoituneiden Hamiltonin syklien määrä kruunussa on kertoimella 2 n pienempi kuin istumapaikkojen määrä [8] , mutta enemmän kertoimella ( n -1)! istumalukuihin verrattuna. Tällaisten kaavioiden syklien lukumäärä (kuten edellä, alkaen n = 3 )

2, 12, 312, 9600, 416880 , 23879520 , 1749363840 , … (sekvenssi A094047 OEIS : ssä ).

Myös toinen kuvaus avioparien ongelmasta graafiteorian kannalta on mahdollista. Jos naiset istuvat, miesten mahdollisia istumapaikkoja voidaan kuvata täydellisiksi yhteensopivuuksiksi kaaviossa, joka muodostetaan poistamalla yksi Hamiltonin sykli täydellisestä kaksiosaisesta graafista. Kaaviossa on reunat, jotka yhdistävät tyhjät istuimet miehiin, ja pyörän poisto vastaa miesten kieltoa istua puolisonsa viereisillä paikoilla. Kaksiosaisen kaavion osumien määrä ja siten istumapaikkojen määrä voidaan laskea pysyväksi jonkin 0-1 matriisin . Lisäksi avioparien ongelmalle tämä matriisi on kiertokirje [9] .

Yhteys solmuteoriaan

Syy , joka sai Thetan tutkimaan aviopariongelmaa , tuli siitä , että yritettiin löytää täydellinen luettelo matemaattisista solmuista , joissa on tietty määrä risteyksiä , sanotaanko n . Dowkerin solmukaavioiden merkinnässä , jonka varhaista muotoa Tet käytti, 2 n pistettä olivat solmuleikkauksia, jotka on numeroitu solmua pitkin numeroilla 1 - 2 n . Supistetussa kaaviossa kaksi risteysmerkkiä ei voi olla peräkkäisiä lukuja, joten Dowker-merkinnöissä solmun merkitsemiseen käytetty tarraparien joukko kussakin risteyksessä voidaan ymmärtää täydelliseksi yhteensopivuudeksi kaaviossa, jonka numerot ovat 1-2 n . pisteinä ja reunoina kunkin lukuparin välillä, joilla on erilainen pariteetti ja jotka eivät ole peräkkäisiä modulo 2 n . Tämä graafi muodostetaan poistamalla Hamiltonin sykli (yhdistää peräkkäiset luvut) täydellisestä kaksiosaisesta graafista (liittää lukupareja eri pariteetilla). Näin ollen yhteensopivuuksien määrä tällaisessa kaaviossa on yhtä suuri kuin istumajärjestelyjen lukumäärä. Vuorotteleville solmuille tämä vastaavuus riittää kuvaamaan solmukaaviota . Muille solmuille on määritettävä plus- tai miinusmerkki kullekin leikkauspisteelle kuvaamaan, kumpi risteyksen kahdesta säikeestä on päällä.

Solmujen numerointiongelmassa on kuitenkin lisäsymmetrioita, joita ei ole aviopariongelmassa - jos aloitamme eri leikkauspisteestä, saadaan erilainen Dowker-merkintä, ja kaikkia näitä merkintöjä tulee pitää saman kaavion esityksinä. Näistä syistä kahta yhteensopivuutta, jotka eroavat vain syklisestä permutaatiosta , tulisi pitää vastaavina ja ne tulisi laskea vain kerran. Hilbert [10] ratkaisi tämän ongelman osoittamalla, että erillisten vastaavuuksien lukumäärä saadaan sekvenssistä:

1, 2, 5, 20, 87, 616, 4843, 44128 , 444621 , … (sekvenssi A002484 OEIS : ssä ).

Muistiinpanot

  1. ↑ Dutka, 1986 .
  2. ↑ Touchard, 1934 .
  3. ↑ Wyman, Moser, 1958 .
  4. ↑ Bogart, Doyle, 1986 .
  5. ↑ Gleick, 1986 .
  6. ↑ Muir, 1882 ; Laisant, 1891 . Hieman monimutkaisempia toistuvia kaavoja ovat aiemmin kuvanneet Cayley ja 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 .

Kirjallisuus

Linkit