h.hofstede (h.hofstede@hogeland.nl)

Koolstofketens.
       
In deze les over permutatiegroepen leerden we over de cykelindex, en hoe je die kunt gebruiken om aantallen mogelijke permutaties te tellen. Even een klein minivoorbeeldje om je geheugen op te frissen en om op voort te borduren:

Stel je hebt rode, groene en blauwe knikkers en die wil je op de hoekpunten van een gelijkzijdige driehoek leggen. We beginnen eenvoudig door te eisen dat we alleen de identieke permutatie toestaan. Dat betekent dat we alle anderen als verschillend van elkaar zien, dus dat in de cykelindex alleen  f 13  voorkomt.
Als je je afvraagt hoeveel mogelijkheden er nu zijn met bijvoorbeeld 2 rode knikkers, dan gaat dat zo:

(r + g + b) invullen geeft   (r + g + b)3 = r3 + g3 + b3 + 3r2g + 3r2b + 3g2r + 3g2b + 3b2r + 3b2g + 6rbg 
dus bijvoorbeeld lees je snel af uit deze cofficinten:
met 2 rood en 1 blauw zijn er 3 mogelijkheden  (de cofficint van 3r2b) maar dat wist je natuurlijk z ook wel:  je kunt degene die je blauw kleurt uit 3 kiezen.
met 2 verschillende kleuren zijn er 18 mogelijkheden (al die cofficinten 3 samen)
in totaal zijn er 27 mogelijkheden:  dh, voor elk hoekpunt 3, dus 33 . Logisch.
       
Verdieping 1.

Maar nou komt het idee. Als we nou in plaats van knikkers geen knikkers maar groepjes knikkers op de hoekpunten gaan leggen......
We zijn een hele nacht druk geweest en hebben een aantal nieuwe knikkers gemaakt door anderen aan elkaar te lijmen. Zo hebben we nu een pot met RB knikkers, een pot met BB knikkers en nog losse G knikkers, zoals hieronder.
       

       
Als ik nu weer zulke "knikkers" op de hoekpunten van een driehoek zou leggen, dan zou ik zulke vreemde driehoeken kunnen krijgen:
       

       
Noem eerst RG even X en BB even Y.
Dan krijg je voor de cykelindex: 
(X + Y + g)3 = X3 + Y3 + g3 + 3X2Y + 3X2g + 3Y2X + 3Y2g + 3g2X + 3g2Y + 6XYg  

En nou komt de grote truc:  als je van je eindresultaat wilt weten hoeveel rode, blauwe en groene knikkers er nou in totaal zijn gebruikt, dan vervang je de X gewoon door rb  en die Y door bb
Dan staat er:

(X + Y + g)3
r3b3 + b3b3 + g3 + 3r2b2bb + 3r2b2g + 3b2b2rb + 3b2b2g + 3g2rb + 3g2bb + 6rbbbg
= r
3b3 + b6 + g3 + 3r2b3 + 3r2b2g + 3b5r + 3b4g + 3g2rb + 3g2b2 + 6rb3g

En nou kun je weer direct zien dat er bijvoorbeeld 3 manieren zijn met  2 rode, 2 blauwe en een groene knikker:  de cofficint van  3r2b2g.  Je hoeft je niet meer druk te maken om de manieren waarop dat tot stand kan komen (alhoewel je vast wel ziet dat het die rechterdriehoek hierboven met zijn neefjes is).

Verdieping 2.

Een tweede mogelijkheid zou zijn, dat er van n kleur verschillende soorten knikkers zijn. Stel bijvoorbeeld dat er ronde, vierkante en driehoekige rode knikkers zijn.
De cyklindex gaf 
(r + g + b)3 = r3 + g3 + b3 + 3r2g + 3r2b + 3g2r + 3g2b + 3b2r + 3b2g + 6rbg 
Maar elke term met een r erin staat nu eigenlijk voor 3 verschillende mogelijkheden, want der kan rond, vierkant of driehoekig zijn. En elke term met r2 staat voor 9 mogelijkheden: drie voor de eerste r en drie voor de tweede.
Je zult al wel doorhebben dat we daar rekening mee kunnen houden door r te vervangen door 3r:
(3r + g + b)3 = 27r3 + g3 + b3 + 27r2g + 27r2b + 9g2r + 3g2b + 9b2r + 3b2g + 18rbg 
 
Een  belangrijke toepassing: Aliphatische Alcoholen.

Aliphatische alcoholen zijn alcoholen met moleculeformule  CnH2n + 1OH. Het gaat ons erom welke structuurformules (woord zegt het al;  welke ligging ten opzichte van elkaar de atomen hebben) bij welke n horen.
Voor het gemak teken ik in het vervolg niet al die H's meer. Omdat we weten dat aan elke C vier dingen moeten zitten is voldoende om de H's er verder steeds bij te denken als je dat wilt.

Voor n = 1 en n = 2 ziet dat er z uit:
 

       
Voor n = 3 ontstaat er voor het eerst wiskundig iets interessants:  er zijn twee verschillende mogelijkheden (twee isomeren)
       

       
De vraag is:  hoeveel isomeren horen er bij een bepaalde n?  Dat lijkt op het eerste gezicht misschien makkelijk, maar vergis je niet:  die koolstofatomen hoeven niet meer in een mooie rechte lijn te blijven liggen zoals tot nu toe!
Voor n = 4 zijn er daarom al 4:
       

       
Zo'n structuur als hierboven heet in de grafentheorie een boom  (er mogen geen lussen in zitten en hij moet helemaal aan elkaar zitten). Laten we het koolstofatoom waaraan de OH vastzit de wortel van die boom noemen.

Tijd voor wat recursiewerkzaamheden:
Als je het wortel C-atoom weglaat uit de boom dan valt hij uiteen in een aantal sub-bomen.
Ok, laten we een ingewikkelde boom nemen (ik heb werkelijk geen enkel geen idee hoe deze alcohol heet en hoe 'e smaakt;  ik verzin dit ter plekke):
       

       
De wortel is die groene C en die laten we weg waardoor de boom in drie stukken uit elkaar valt. We beschouwen de C die oorspronkelijk aan de weggelaten C vastzat als de nieuwe wortel van elk van die sub-bomen.
       

       
Vraag jezelf af:  "zou ik van dit laatste plaatje de oorspronkelijke boom kunnen terugfabriceren?"
Natuurlijk!  Je zet al die drie groene C's gewoon vast aan een nieuwe C en plakt daar weer een OH aan. Gewoon het "filmpje terugdraaien", of de "schade herstellen"" als je dat beter vindt klinken. De volgorde waarin je die drie aan elkaar plakt doet er niet toe; ze zitten aan dezelfde C en het zijn er maar drie, dus dat levert dezelfde boom op.

Het zou natuurlijk ook kunnen dat er geen drie maar minder sub-bomen ontstaan (als de OH aan de rand zit). In zo'n geval doen we gewoon alsof er toch drie bomen te zijn door fictieve "lege" bomen toe te voegen.  Z bijvoorbeeld:
       

       
Als je die drie "sub-bomen" weer samenvoegt krijg je weer gewoon de oorspronkelijke boom. Er zouden zelfs 2 lege bomen kunnen zijn. Hoe dan ook; het komt er op deze manier elke keer op neer dat we drie sub-bomen samenvoegen om een nieuwe boom te krijgen.
Beschouw die drie sub-bomen als de "dingen" die om de hoekpunten van een driehoek worden gelegd. Net als de samengelijmde knikkers hierboven.

Een willekeurige boom kunnen we dus krijgen door drie bomen aan elkaar te zetten. Dat kunnen op zich weer bomen met 0, 1, 2, 3, 4... C-atomen zijn. En van al die bomen zijn er weer een aantal varianten mogelijk. Stel dat er van een boom met k C-atomen  in totaal Rk varianten mogelijk zijn  (dus  zoals we bij de alcoholen al zagen: R0 = 1, R1 = 1, R2 = 1, R3 = 2, R4 = 4, ....en de rest weten we nog niet)
Om dan het totaal aantal mogelijkheden op te schrijven moeten we de cykelindex van S3 gebruiken, maar met
f
  =  R0x0 + R1x1 + R2x2 + ....   
   De term met xn  staat voor het aantal sub-bomen met n C-atomen (de aan elkaar gelijmde knikkers van verdieping 1 hierboven)
   De factoren Rn  staan voor het aantal varianten van een sub-boom van n C-atomen  (de verschillende soorten knikkers van verdieping 2 hierboven) 
 

De cykelindex wordt dan:

       

       
Als je voor de f 's dat polynoom invult, en dan alle haakjes zou wegwerken (stel dat je dat zou kunnen) dan zou je een machtsreeks in x krijgen. De macht n van xn  daarin  stelt het totaal aantal C-atomen in de drie sub-bomen samen voor, en de cofficint ervan geeft het aantal manieren waarop het kan. De uiteindelijke boom die de drie sub-bomen samen gaan vormen heeft dus n + 1 C-atomen, immers je voegt bij het samendoen er n toe (plus een OH).
Dus als je de formule met x vermenigvuldigt, dan komt de cofficint van xn precies overeen met het aantal mogelijkheden voor een boom met n C-atomen. Als je er dan ook nog 1 bij optelt om rekening te houden met de lege boom, dan moet je als antwoord precies f(x) krijgen!!!
       

Het is gelukt!!!
We hebben een vergelijking voor de functie f.
Nou ja.... een soort van vergelijking. 't Is niet een gewone vergelijking f(x) = .... met x-en erachter. Dit hier is meer een soort recept waar f aan voldoet. Dat noemen we een functionaalvergelijking.
Nu nog even gewoon deze functionaalvergelijking omzetten in een "gewone" vergelijking. 

Helaas is dat tot nu toe nog niemand gelukt!

Het beste wat we kunnen doen is een reeksontwikkeling voor dat monster aan de linkerkant maken.
Stel f(x) = R0 + R1x + R2x2 + R3x3 + R4x4 + R5x5 + ..... 
Wacht even; we weten R0, R1, R2, R3 en R4 al:    f(x) = 1 + x + x2 + 2x3 + 4x4 + R5x5 + R6x6 + ..... 
Vul dit in in die functionaalvergelijking, werk alle haakjes weg en nemen gelijke machten van x samen.

Ik zal een beginnetje maken. Laat ik maar eens op zoek gaan naar R5, dus de cofficint van x5  Dat moet dan daar in die teller de cofficint van x4 zijn, want er staat ook nog een x voor.
Op jacht naar machten x4  dus:
  (de blauwe getallen hieronder zijn binomiaalcofficinten)
f
(x)3  krijgt als machten van x4 uiteindelijk  3 1 1 4x4 + 3 x x x2 + 3 1 x2 x26 1 x 2x3 = 30x4
3f(x)f(x2) krijgt als machten van x4 uiteindelijk  3 1 (x2)2  + 3 x2 (x2)1 + 3 4x4 12  = 18x4
2f(x3) heeft geen machten van x4
De uiteindelijke teller wordt dus 48x4
Delen door 6 en vermenigvuldigen met x geeft een term  8x5  dus  R5 = 8
       
Dan is de tussenstand    f(x) = 1 + x + x2 + 2x3 + 4x4 + 8x5 + R6x6 + ..... en kunnen we op zoek naar R6 
Typisch een werkje voor een computer-algebraprogramma.
Hier zijn wat resultaten:
       
R1 R2 R3 R4 R5 R6 R7 R8 R9 R10 R11 R12 R13 R14
1 1 2 4 8 17 39 89 211 507 1238 3057 7639 19241
       

h.hofstede (h.hofstede@hogeland.nl)