Eulercircuits

Hoe moet je berekenen hoeveel Eulercircuits K5 heeft?

henk
Student universiteit - dinsdag 23 september 2003

Antwoord

Hallo Henk,

Noem de toppen 1 t.e.m. 5. We berekenen hoeveel Eulercircuits er zijn van 1 tot 1. Elk Eulercircuit heeft de vorm 1,...,1,...,1 en bestaat uit elf cijfers (elk cijfer dubbel, de 1 driedubbel).
Hoe kunnen de puntjes ingevuld worden? Ik ga nu kijken naar hoeveel toppen er tussen de eerste twee enen staan, en hoeveel tussen de laatste twee. Dus als ik zeg 'Eerst 2, dan 6' dan bedoel ik bijvoorbeeld een circuit van de vorm 1,2,5,1,3,2,4,3,5,4,1 waarbij er twee toppen (nl 2 en 5) links van de middelste '1' staan, en 6 rechts.

- Eerst 1, dan 7: onmogelijk, bv 121... gebruikt tweemaal dezelfde boog (1,2).

- Eerst 2, dan 6: voor die twee kan je elk tweetal cd kiezen, dus 12 keuzes want de volgorde is belangrijk! Voor die 6 heb je dan nog over: aabbcd. Die moet je in een zodanige volgorde zetten dat de eerste en de laatste letter verschillen (anders heb je tweemaal de boog 1a b.v.), er mogen geen twee gelijke letters na elkaar komen, er mag niet twee keer xy staan, en ook niet yx samen met xy, en de letters c en d mogen niet op het einde of begin staan want de bogen 1c en 1d heb je al gebruikt. Wat schiet er nog over? abcadb, abdacb, acbadb, acbdab, adbacb, adbcab, bacbda, badbca, bcabda, bcadba, bdabca, bdacba. Dat zijn er dus 12. Conclusie: 144 van dit type. Ik heb dit lijstje alfabetisch opgesteld: je gaat gewoon na wat er mag en wat niet, en je weet ook dat a en b dezelfde rol spelen, en c en d ook, en dan krijg je vrij vlot dit lijstje.

- Eerst 3, dan 5: die drie moeten allemaal verschillen, dus dat zijn 24 drietallen (b,c,d). Voor die vijf kunnen we nog kiezen uit a,a,b,c,d. Ook hier moet je weer een lijstje maken: merk op dat de lijst niet met b of d mag beginnen of eindigen en dat je bc en cd niet meer mag gebruiken. cabda mag dus wel, en ook cadba. En ook nog abdac en adbac, en daar houdt het mee op. Dit geeft dus 24*4 = 96 circuits.

- Eerst 4, dan 4: die eerste vier kunnen vier verschillende zijn (a,b,c,d) en dan zijn er nog twee mogelijkheden om het circuit af te maken (dat zie je best op de figuur zelf), dus dit geeft 24*2=48 circuits. Het kan niet dat je toppen dubbel gebruikt in die eerste vier zonder bogen dubbel te gebruiken.

- Eerst 5, dan 3: 96

- Eerst 6, dan 2: 144

Alles samen: 144+96+48+96+144 = 528.
Je moet dit nog met 5 vermenigvuldigen omdat je niet op de 1 hoeft te vertrekken.
En je kan dit (eventueel) nog door twee delen omdat je elk circuit eens in de ene richting hebt, eens in de andere richting. Dus er zijn 2640 Eulercircuits in K5.

Ik hoop nu maar dat ik mij nergens misteld heb...
Met dank aan Anneke voor het nalezen en melden van fouten!

Groeten,
Christophe.

Christophe
dinsdag 23 september 2003

©2001-2024 WisFaq