Cykelindex

Inom kombinatorik är cykelindex ett polynom med flera variabler, vilket är strukturerat så att det sätt på vilket en permutationsgrupp verkar på en mängd enkelt kan utläsas från polynomets koefficienter och exponenter. Detta kompakta sätt att uttrycka information på ett algebraiskt sätt används ofta vid uppräkningar. 

Varje permutation π av en ändlig mängd element delar mängden i en eller flera cykliska partitioner. Cykelindexmonomet till π är ett monom av variablerna x1, x2, … som beskriver partitionens typ (π:s cykeltyp), där koefficienten anger cykelns längd. Exponenten j i  anger antalet cykler i π av längden k: exempelvis beskrivs permutationen (1)(28)(37)(46)(5) av monomet  , d.v.s. att permutationen består av två fixpunkter (partitioner om ett element, vilket avbildas på sig själv) och tre cykliska partitioner om två element. Cykelindexpolynomet för en permutationsgrupp är lika med det aritmetiska medelvärdet av cykelindexmonomen för dess element (d.v.s. för de permutationer som ingår i gruppen). 

Om man känner cykelindexpolynomet för en permutationsgrupp kan man räkna upp (enumerera) ekvivalensklasserna som följer av gruppens verkan på mängden. Detta är huvudinnebörden av Pólyas enumerationssats.

Definition
En permutation σ:s cykelindexmonom är monomet

där jk(σ) är hur många cykler av längd k det finns i den fullständiga faktoriseringen av σ.

En permutationsgrupp G:s cykelindexpolynom Z(G) är medelvärdet av cykelindexmonomen av permutationerna i gruppen:

Följder
Om X är en mängd och permutationsgruppen G är en delgrupp till den symmetriska gruppen över X och p(x1, ..., xn) är G:s cykelindexpolynom så kan X färgläggas med q färger, med hänsyn till symmetrierna i G, på p(q, q, ..., q) sätt. Detta är en följd av Burnsides lemma.

En generalisering av detta är Pólyas enumerationssats.

Exempel

En cyklisk grupp med tre element
Ta gruppen C3 = { e, (1 2 3), (1 3 2)}, som består av identitetsavbildning och två tre-cykler. Cykelindexpolynomet för C3 är:

Gruppen C3 kan tolkas som rotationssymmetrierna på en triangel där sidorna är numrerade 1, 2, 3. Om man vill färga triangelns sidor med två färger finns det då

sätt att göra det på. Dessa är att alla sidor har färg 1, alla sidor har färg 2, en sida har färg 1 och de andra färg 2 samt en sida har färg 2 och de andra färg 1.

En dihedral grupp med sex element

En dihedral grupp med sex element, D6, motsvarar en regelbunden sexhörnings permutationer under rotation och spegling. Denna har en identitetsavbildning:

fem rotationssymmetrier (vridning 60°, 120°, 180°, 240° respektive 300°):

 
d.v.s. sammanlagt   

tre speglingar i linjer genom motstående hörn:

d.v.s. sammanlagt   

och tre speglingar i linjer genom motstående sidors mittpunkter:

d.v.s. sammanlagt   

Det aritmetiska medelvärdet av dessa 12 permutationer ger oss:

Om vi tänker oss att sexhörningens hörn motsvarar de sex pärlorna på ett fritt halsband och att vi kan välja mellan tre olika sorters pärlor till detta, ger oss Burnsides lemma att det finns

olika sätt att tillverka ett sådant halsband på.

Cykelindex för permutationer av ytorna på en kub

Betrakta en vanlig tredimensionell kub och dess symmetriska grupp (automorfismer) och kalla den C. Sym(C) permuterar de sex ytorna på kuben (vi skulle också kunna studera permutationerna av kanter eller hörn). Det finns tjugofyra automorfismer (alla symmetriaxlar går genom kubens centrum):

 En identitet:
Denna permutations bidrag är 
 Sex 90°-rotationer kring axlar genom motstående sidors mittpunkter:
 Tre axlar, en mot- och en medsols rotation per axel. Bidraget är 
 Tre 180°-rotationer kring axlar genom motstående sidors mittpunkter:
 Samma tre axlar men bara en rotation per axel. Bidraget är 
 Åtta 120°-rotationer kring axlar genom diagonalt motstående hörn (och genom kubens mittpunkt - se figur till höger):
 Fyra tretaliga axlar. Två rotationer per axel (det tredje läget är ju identiteten) Bidraget är 
 Sex 180°-rotationer kring axlar genom diagonalt motstående kanters mittpunkter (och kubens mittpunkt - se figur till höger):
 Bidrag 

Cykelindex för C blir sålunda:

Har vi k färger till hands kan vi alltså färga kubens sidor på 
 
olika sätt. För k=2 blir antalet sätt 10, för k=3 blir det 57 och har vi exempelvis tio färger blir det 43450. 

De tio sätten för två färger (t.ex. svart och vit) är: (1) alla sidor vita, (2) en sida svart (resten är såklart vita), (3) två intilliggande sidor svarta, (4) två motstående sidor svarta, (5) tre svarta sidor som möts i samma hörn, (6) tre svarta sidor varav två är motstående, (7) två vita intilliggande sidor, (8) två motstående vita sidor, (9) en vit sida och (10) alla sidor svarta.

Vid tre färger får man tre enfärgade kuber (trivialt), 3×8=24 kuber med två färger (analogt med de åtta tvåfärgade vid k=2, men nu kan vi bilda tre par) och övriga 30 är trefärgade: De tre respektive färgerna kan fördelas på 1+1+4 (tre olika färger kan användas för de fyra sidorna och de två övriga sidorna kan antingen vara motstående eller intilliggande, d.v.s. 3×2=6 möjligheter), 1+2+3 (3!×3=18 möjligheter: sex möjligheter att fördela färgerna gånger de tre sidorna av samma färg möts i ett hörn + de två sidorna av samma färg är motstående + ingetdera fallet) eller 2+2+2 sidor (alla färger motstående, en färg motstående och inga färger motstående ger 1+3+2=6 möjligheter; den sista tvåan beror på chiralitet). Fallet med tio färger lämnas åt läsaren.

Cykelindex för olika grupper

Trivialgruppen En
Trivialgruppen innehåller endast identitetsavbildningen, sålunda har vi:

Den cykliska gruppen Cn
Den cykliska gruppen Cn utgörs av gruppen av rotationer i planet av en regelbunden polygon med n kanter (eller hörn), eller av n objekt jämnt utbredda längs en cirkels omkrets. Den har φ(d) element av ordningen d som delar n. φ(d) är Eulers fi-funktion och ger antalet naturliga tal mindre än d som är relativt prima till d. En permutation av ordningen d har n/d cykler av längden d, sålunda:

Den dihedrala gruppen Dn
Den dihedrala gruppen Dn är en cyklisk grupp med n element som också tillåter spegling:

Den alternerande gruppen An
Den alternerande gruppen An utgörs av de jämna permutationerna av på en mängd bestående av n element. Om antalet transpositioner (parvisa byten) av objekten för att åstadkomma en permutation är jämnt är permutationen jämn, annars udda. Exempelvis kan man genom att byta plats på a och b i abcd åstadkomma den udda permutationen bacd och genom att sedan byta plats på a och c får man den jämna bcad. Permutationerna (1)(2)(3)(4), (12)(34), (13)(24), (14)(23), (1)(234), (1)(243), (2)(134), (2)(143), (3)(124), (3)(142), (4)(123) och (4)(132) av fyra objekt är jämna, övriga tolv är udda. An består således av n!/2 element och dess cykelindex ges av:

Referenser
 

 

 

Perneby, Susanne (2010), En Introduktion till Pólyas Enumerationssats, Självständiga arbeten i matematik 2010 - No 9, Matematiska Institutionen, Stockholms Universitet, Läst: 2014-10-14.

Noter

Gruppteori
Kombinatorik