Loading AI tools
Från Wikipedia, den fria encyklopedin
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)[1] 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.
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:
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.
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, D6, motsvarar en regelbunden sexhörnings permutationer under rotation och spegling. Denna har en identitetsavbildning:
fem rotationssymmetrier (vridning 60°, 120°, 180°, 240° respektive 300°):
tre speglingar i linjer genom motstående hörn:
och tre speglingar i linjer genom motstående sidors mittpunkter:
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[2] 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å.
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):
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.
Trivialgruppen innehåller endast identitetsavbildningen, sålunda har vi:
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:[3]
Den dihedrala gruppen Dn är en cyklisk grupp med n element som också tillåter spegling:
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:
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.