Kombinatorik, Partitioner Og Repræsentationsteori Kompendium

Kombinatorik, Partitioner og Repræsentationsteori Kompendium Jørn B. Olsson med tak til Henning Røigaard-Petersen for stor hjælp med første version 1 Dette kompendium, som er udarbejdet i forbindelse med et tidligere kursus, og som nu er ved at blive udbygget, supplerer bogen af Andrews og Eriksson, samt forelæserens Lecture Notes. Henvisninger til bogen af Andrews og Eriksson gives som [AE], fx. “Se et bevis i [AE], Kapitel 2.2” 2 1 Konjugationsklasser i Sn og partitioner Teorien for partitioner spiller en væsentlig rolle for de symmetriske grupper, især for studiet af deres repræsentationer. Men partitioner dukker allerede op i beskrivelsen af konjugationsklasser af elementer i Sn . Definition 1.1. For n ∈ N defineres den symmetriske gruppe af grad n, betegnet Sn , som mængden af slle permutationer af tallene 1,. . . ,n. Elementerne i Sn er alts˚ a de bijektive afbildninger s : {1, . . . , n} → {1, . . . , n} og udgør en gruppe med kompositionen ”sammensætning af afbildninger”. Et typisk element s ∈ Sn kan angives eksplicit p˚ a 3 m˚ ader: Tabelfremstillingen er, som navnet antyder, en tabel, hvor det nemt aflæses hvad et givet tal afbildes i:
 1 2 ... n s= s(1) s(2) . . . s(n) Den direkte fremstilling er essentielt tabelfremstillingen, men den øverste række er fjernet: s = [s(1) s(2) . . . s(n)] Denne fremstilling ikke hensigtsmæssigt til at beregne produktet (sammensætning) af to elementer. Cykelfremstillingen : Elementet skrives som et produkt af disjunkte cykler, s = (i1 , i2 , . . . , il )(j1 , j2 , . . . , js ) . . . (k1 , k2 , . . . , kt ). Her skal (i1 , i2 , . . . , il ) læses som i1 → i2 , i2 → i3 , . . . , il−1 → il og slutteligt il → i1 og delmængderne af i’er, j’er etc er disjunkte. Er der punkter i {1, . . . , n} der er fikspunkter for permutationen, vil disse udgøre en cykel med kun ´et element i fremstillingen og udelades gerne. S˚ aledes defineres ved s = (1, 2, 3)(4, 5) en permutation i S6 givet ved s(1) = 2, s(2) = 3, s(3) = 1, s(4) = 5, s(5) = 4, s(6) = 6. En cykelfremstilling er entydig op til ombytning af cyklerne samt ”rotation”i en cykel, f.eks. er (i1 , i2 , i3 ) = (i3 , i1 , i2 ). Definition 1.2. (Cykellængde/Cykeltype) En cykel med m elementer kaldes en m-cykel. For en permutation s ∈ Sn defineres cykeltypen som et tupel ct(s) = (1m1 , 2m2 , . . . , nmn ) hvor mi angiver antallet af i-cykler i fremstillingen 3 For en cykeltype gælder klart følgende relation:  imi = n i≥1 . Definition 1.3. (Konjugation) Lad G være en gruppe og lad x, y ∈ G. x og y siges da at være konjugerede, og vi skriver x ∼ y, dersom ∃g ∈ G : x = gyg −1 Vi ved fra Mat2AL at denne relation er en ækvivalensrelation hvis ækvivalensklasser kaldes G’s konjugationsklasser. Ved at udnytte cykelfremstillingen af elementerne i Sn kan man beskrive gruppens konjugationsklasser. Lemma 1.4. Lad g, s ∈ Sn med s = (i1 , i2 , . . . , il )(j1 , j2 , . . . , js ) . . . (k1 , k2 , . . . , kt ). Da har gsg −1 cykelfremstillingen (g(i1), g(i2 ), . . . , g(il )) (g(j1 ), g(j2), . . . , g(js )) . . . (g(k1), g(k2), . . . , g(kt)) Eksempel 1.5. Lad s, g ∈ S8 s˚ a s = (1, 3, 4, 8)(2, 7, 6) og g = (1, 2)(3, 4)(5, 6, 7). Da er gsg −1 = (2, 4, 3, 8)(1, 5, 7) Af lemmaet f˚ as umiddelbart Sætning 1.6. Lad s1 , s2 ∈ Sn . Da gælder s1 ∼ s2 ⇔ ct(s1 ) = ct(s2 ) Definition 1.7. (Partition) Lad n ∈ N. En partition af n er en sekvens af naturlige tal λ = (l1 , l2 , . . . , lm ) s˚ aledes at l1 ≥ l2 ≥ . . . ≥ lm og l1 + l2 + . . . + lm = n Tallene li kaldes λ’s dele og m er dens længde. At λ er en partition af n skrives λ  n. Nogle steder i litteraturen, fx. i [AE], benyttes notationen l1 + l2 + · · · + lm for en partition. At der er tale om en partition af n skrives s˚ a n = l1 + l2 + · · · + lm . Hvis vi tager en sekvens (1m1 , 2m2 , . . . , k mk ), kort skrevet (imi ), der opfylder  imi = n mi ≥ 0 (idet indgange med mi