Banenformule/kettingprobleem

De vraag is:
Je hebt een ketting die bestaat uit 5 bolvormige kralen aan een gesloten ketting die elk rood, wit, blauw of oranje zijn. De kralen kunnen vrij bewegen langs de ketting. Hoeveel verschillende kettingen zijn er?

Ik weet dat het totaal aantal mogelijke kettingen gelijk is aan 4 tot de 5de, oftewel 1028, maar ik weet niet hoe je kan berekenen hoeveel van deze kettingen 'dubbel' zijn. Dat moet waarschijnlijk met de 'banenformule' van William Burnside, maar die snap ik niet helemaal. Weten jullie hoe ik te werk moet gaan?

Donald
Student universiteit - woensdag 13 april 2005

Antwoord

Hallo Donald,

Eerst gaan we het eens proberen zonder de formule van Burnside. Het gaat dus over zo’n soort baby rammelaar. 5 kralen aan een ring. Iedere kraal kan rood, blauw, wit of oranje zijn.
We gaan uit van de 4⁵ = 1024 mogelijke ringen als we geen rekening houden met draaiingen en omkeringen.( door draaien gaat bv een ring $<$ r w b w w $>$ over in $<$ w b w w r $>$ , door omkering kan hij overgaan in bv $<$ r w w b w $>$ )
a) Als we alleen rekenig houden met draaiingen zijn er 4 + (1020)/5 = 208 mogelijke ringen.(4 met maar één kleur en alle andere 1020 ringen zijn 5 keer geteld dus dat delen we door 5)
b) Van deze 208 ringen zijn er S symmetrisch.(bv $<$ r b w b r $>$ Deze veranderen niet bij omkering en A asymmetrisch deze zijn dus dubbel geteld. Het echte aantal verschillende ringen is dus gelijk aan S + A/2 . We gaan nu S bepalen. S = 4 (ringen met 1 kleur) + 36 (met 2 kleuren, 12 van type $<$a b b b a$>$, 12 van type $<$ a a b a a $>$, 12 van type $<$ a b a b a$>$ , steeds 12 omdat we de 2 kleuren op 4·3 = 12 manieren kunnen kiezen ) + 24 (met 3 kleuren van type $<$ a b c b a $>$ ) Dus S = 4 + 36 +24 = 64. En A = 208 – 64 = 144. Zo komen we dus op 64 + 72 = 136 verschillende ringen

Nu gaan we proberen dit aantal te bepalen mbv de formule van Burnside.
We gaan weer uit van de verzameling X van alle 1024 ringen. Op deze verzameling werkt de groep G = { e, d1,d2, d3, d4, s1,s2, s3, s4, s5} (dit is de zg dihedrale groep D5) Hierin is dk draaien over k maal 72º ,bv d2(abcde) = (cdeab) en sk is de omklapping waarbij de kde kraal op zijn plaats blijft.
Verder is de zg baan (orbit) B(x) van een ring x uit X de verzameling van alle ringen die uit x ontstaan door toepassing van alle operaties van G. Bv als x een ring met 1 kleur dan bestaat B(x) slechts uit 1 element: | B(x)| = 1. Voor x een symmetrische ring is | B(x) |=5 en voor een asymmetrische ring | B(x)| = 10.
Het aantal banen is dus precies het aantal verschillende ringen dat we wilden bepalen. Met de formule van Burnside kunnen we het aantal banen bepalen.
Dat gaat zo. Bij iedere g van G is er een verzameling Fix(g) = {x: gx = x} van elementen van X die niet veranderen bij operatie g.
De formule van Burnside zegt nu dat het aantal banen gelijk is aan
($<$sum$>$ over alle g , | Fix(g)| ) / |G|
Dit geeft de volgende berekening: | Fix(e)| = 1024
| Fix(dk)| = 4 (alleen de ringen met één kleur) Dit geeft een bijdrage 4x₄ = 16.
|Fix( sk)| = 64( alle symmetrische ringen ). Bijdrage 5 x 64 = 320
Dus totale $<$sum$>$ wordt 1024 + 16 + 320 = 1360 gedeeld door | G| = 10 en joepie! weer 136. Leve de groepentheorie. Bij rammelaars met 5 kralen was het nog te doen zonder Burnside. Bij 6 kralen is Burnside echt reuze handig.
Ik hoop dat je nu verder kunt . Succes en gegroet.

JCS
maandag 18 april 2005

Re: Banenformule/kettingprobleem

©2001-2024 WisFaq