Indeks cyklu

W matematyce kombinatorycznej indeks cyklu jest wielomianem kilku zmiennych, który jest skonstruowany w taki sposób, że informacje o tym, jak grupa permutacji działa na zbiór , można po prostu odczytać ze współczynników i wykładników. Ten zwarty sposób przechowywania informacji w postaci algebraicznej jest często używany w wyliczeniach kombinatorycznych .

Każda permutacja π skończonego zbioru obiektów , które dzielą się na cykle ; jednomian indeksu cyklu π jest jednomianem w zmiennych a ₁ , a ₂ , … który opisuje typ cyklu tego podziału: wykładnik a _i jest liczbą cykli π o rozmiarze i . Wielomian indeksu cyklu grupy permutacji jest średnią jednomianów indeksu cyklu jego elementów. Wskaźnik cyklu frazy jest również czasami używany zamiast wskaźnika cyklu .

Znając wielomian indeksu cyklu grupy permutacji, można wyliczyć klasy równoważności ze względu na działanie grupy. Jest to główny składnik twierdzenia Pólyi o wyliczaniu . Wykonywanie formalnych operacji algebraicznych i różniczkowych na tych wielomianach, a następnie kombinatoryczna interpretacja wyników, leży u podstaw teorii gatunków .

Grupy permutacji i akcje grupowe

Bijektywna mapa ze zbioru X na siebie nazywana jest permutacją X , a zbiór wszystkich permutacji X tworzy grupę pod złożeniem odwzorowań, zwaną grupą symetryczną X i oznaczoną Sym ( X ). Każda podgrupa Sym( X ) nazywana jest grupą permutacyjną stopnia | X |. Niech G będzie grupą abstrakcyjną o homomorfizmie grupowym φ z G do Sym( X ). Obraz φ ( G ) jest grupą permutacji. Homomorfizm grupowy można traktować jako sposób na umożliwienie grupie G „działania” na zbiorze X (przy użyciu permutacji związanych z elementami G ). Taki homomorfizm grupowy jest formalnie nazywany działaniem grupowym , a obrazem homomorfizmu jest permutacyjna reprezentacja G . Dana grupa może mieć wiele różnych reprezentacji permutacji, odpowiadających różnym akcjom.

Załóżmy, że grupa G działa na zbiorze X (czyli istnieje działanie grupowe). W zastosowaniach kombinatorycznych interesuje nas zbiór X ; na przykład liczenie rzeczy w X i wiedza, jakie struktury mogą pozostać niezmienne przez G . Niewiele traci się pracując z grupami permutacji w takim ustawieniu, więc w tych zastosowaniach, gdy rozważana jest grupa, jest to reprezentacja permutacji grupy, z którą będzie się pracować, a zatem należy określić działanie grupowe. Z drugiej strony algebraiści są bardziej zainteresowani samymi grupami i bardziej interesowaliby się jądrami działań grupowych, które mierzą, ile traci się przy przejściu od grupy do jej reprezentacji permutacyjnej.

Rozłączna reprezentacja cykliczna permutacji

Skończone permutacje są najczęściej reprezentowane jako działania grupowe na zbiorze X = {1,2, ..., n}. Permutacja w tym ustawieniu może być reprezentowana przez notację dwuwierszową. Zatem,

${\ Displaystyle \ lewo ({\ rozpocząć {macierz} 1 i 2 i 3 i 4 i 5 \\ 2 i 3 i 4 i 5 i 1 \ koniec {macierz}} \ w prawo)}$

odpowiada bijekcji na X = {1, 2, 3, 4, 5}, która wysyła 1 → 2, 2 → 3, 3 → 4, 4 → 5 i 5 → 1. Można to odczytać z kolumn notacja. Gdy górny wiersz jest rozumiany jako elementy X w odpowiedniej kolejności, wystarczy napisać drugi wiersz. W tej jednolinijkowej notacji nasz przykład to [2 3 4 5 1]. Ten przykład jest znany jako permutacja cykliczna , ponieważ „przetacza” liczby wokół, a trzecia notacja dla niego to (1 2 3 4 5). Ten zapis cykliczny należy odczytywać jako: każdy element jest wysyłany do elementu po jego prawej stronie, ale ostatni element jest wysyłany do pierwszego ("cykluje" do początku). W notacji cyklicznej nie ma znaczenia, gdzie zaczyna się cykl, więc (1 2 3 4 5) i (3 4 5 1 2) i (5 1 2 3 4) reprezentują tę samą permutację. Długość cyklu to liczba elementów w cyklu.

Nie wszystkie permutacje są permutacjami cyklicznymi, ale każdą permutację można zapisać jako iloczyn rozłącznych (nie mających wspólnego elementu) cykli zasadniczo w jeden sposób. Ponieważ permutacja może mieć stałe punkty (elementy niezmienione przez permutację), będą one reprezentowane przez cykle o długości jeden. Na przykład:

${\ Displaystyle \ lewo ({\ początek {macierz} 1 i 2 i 3 i 4 i 5 i 6 \\ 2 i 1 i 3 i 5 i 6 i 4 \ koniec {macierz}} \ po prawej) = (12) (3) (456).}$

Ta permutacja jest iloczynem trzech cykli, jednego o długości 2, jednego o długości 3 i punktu stałego. Elementy w tych cyklach są rozłącznymi podzbiorami X i tworzą partycję X .

Struktura cykli permutacji może być zakodowana jako algebraiczny jednomian w kilku ( fikcyjnych ) zmiennych w następujący sposób: zmienna jest potrzebna dla każdej odrębnej długości cyklu cykli, które pojawiają się w dekompozycji cyklu permutacji. W poprzednim przykładzie były trzy różne długości cykli, więc użyjemy trzech zmiennych, a ₁ , a ₂ i a ₃ (ogólnie używamy zmiennej a _{k ,} aby odpowiadała długości k cykli). Zmienna a _i zostanie podniesiona do potęgi j _i ( g ) , gdzie j _i ( g ) jest liczbą cykli o długości i w dekompozycji cykli permutacji g . Możemy wtedy powiązać jednomian indeksu cyklu

${\ Displaystyle \ prod _ {k = 1} ^ {n} a_ {k} ^ {j_ {k} (g)}}$

do permutacji g . Jednomian indeksu cyklu w naszym przykładzie to a ₁ a ₂ a ₃ , podczas gdy jednomian indeksu cyklu permutacji (1 2)(3 4)(5)(6 7 8 9)(10 11 12 13) to a ₁ za ₂ ² za ₄ ² .

Definicja

Indeks cyklu grupy permutacji G jest średnią jednomianów indeksu cyklu wszystkich permutacji g w G .

Bardziej formalnie, niech G będzie grupą permutacji rzędu m i stopnia n . Każda permutacja g w G ma unikalny rozkład na rozłączne cykle, powiedzmy c ₁ c ₂ c ₃ ... . Niech długość cyklu c będzie oznaczona przez | c |.

Niech teraz j _k (g) będzie liczbą cykli g o długości k , gdzie

${\ Displaystyle 0 \ równoważnik j_ {k} (g) \ równoważnik \ lfloor n/k \ rfloor {\ mbox {i}} \ suma _ {k = 1} ^ {n} k \, j_ {k} (g )\;=n.}$

Łączymy się z jednomianem g

${\ Displaystyle \ prod _ {c \ w g} a_ {| c |} = \ prod _ {k = 1} ^ {n} a_ {k} ^ { j_{k}(g)}}$

w zmiennych a ₁ , a ₂ , ..., a _n .

Wtedy indeks cyklu Z ( G ) G jest dany przez

${\ Displaystyle Z (G) = {\ Frac {1} {| G |}} \ suma _ {g \ w G} \ prod _ {k = 1} ^ {n} a_ {k} ^ {j_ {k }(G)}.}$

Przykład

Rozważmy grupę G symetrii obrotowych kwadratu na płaszczyźnie euklidesowej . Takie symetrie są całkowicie określone przez obrazy tylko rogów kwadratu. Oznaczając te rogi 1, 2, 3 i 4 (kolejno idąc zgodnie z ruchem wskazówek zegara) możemy przedstawić elementy G jako permutacje zbioru X = {1,2,3,4}. Reprezentacja permutacyjna G składa się z czterech permutacji (1 4 3 2), (1 3)(2 4), (1 2 3 4) i e = (1)(2)(3)(4), które reprezentują obroty w kierunku przeciwnym do ruchu wskazówek zegara odpowiednio o 90°, 180°, 270° i 360°. Zauważ, że permutacja tożsamościowa e jest jedyną permutacją ze stałymi punktami w tej reprezentacji G . Jako grupa abstrakcyjna, G jest _znana jako grupa cykliczna C4 , a jej permutacyjna reprezentacja jest jej regularną reprezentacją . Jednomiany indeksu cyklu to odpowiednio a ₄ , a ₂ ² , a ₄ i a ₁ ^{4 .} Zatem indeks cyklu tej grupy permutacji wynosi:

${\ Displaystyle Z (C_ {4}) = {\ Frac {1} {4}} \ lewo (a_ {1} ^ {4} + a_ {2} ^ {2} + 2a_ {4} \ prawo). }$

Grupa C ₄ działa również na nieuporządkowane pary elementów X w naturalny sposób. Dowolna permutacja g wysłałaby { x , y } → { x ^g , y ^g } (gdzie x ^g jest obrazem elementu x pod permutacją g ). Zbiór X to teraz { A , B , C , D , E , F } gdzie A = {1,2}, B = {2,3}, C = {3,4}, D = {1,4} , E = {1,3} i F = {2,4}. Elementy te można traktować jako boki i przekątne kwadratu lub, w zupełnie innym układzie, jako krawędzie pełnego wykresu K ₄ . Działając na tym nowym zbiorze, cztery elementy grupowe są teraz reprezentowane przez ( A D C B )( E F ), ( AC )( BD )( E )( F ), ( ABCD )( EF ) i e = ( A ) ( B )( C )( D )( E )( F ) a indeks cyklu tej akcji to:

${\ Displaystyle Z (C_ {4}) = {\ Frac {1} {4}} \ lewo (a_ {1} ^ {6} + a_ {1} ^ {2} a_ {2} ^ {2} + 2a_{2}a_{4}\prawo).}$

Grupa C ₄ może również działać na uporządkowane pary elementów X w ten sam naturalny sposób. Dowolna permutacja g wysłałaby ( x , y ) → ( x ^g , y ^g ) (w tym przypadku mielibyśmy również uporządkowane pary postaci ( x , x )). Elementy X można traktować jako łuki pełnego digrafu D4 (z pętlami w każdym wierzchołku) _. Indeks cyklu w tym przypadku byłby następujący:

${\ Displaystyle Z (C_ {4}) = {\ Frac {1} {4}} \ lewo (a_ {1} ^ {16} + a_ {2} ^ {8} + 2a_ {4} ^ {4} \Prawidłowy).}$

Rodzaje akcji

Jak pokazuje powyższy przykład, indeks cyklu zależy od akcji grupowej, a nie od grupy abstrakcyjnej. Ponieważ istnieje wiele reprezentacji permutacyjnych grupy abstrakcyjnej, warto mieć pewną terminologię, aby je rozróżnić.

Kiedy grupa abstrakcyjna jest zdefiniowana w kategoriach permutacji, jest to grupa permutacji, a działaniem grupowym jest homomorfizm tożsamościowy. Nazywa się to naturalnym działaniem .

Grupa symetryczna S ₃ w swoim naturalnym działaniu ma pierwiastki

${\ Displaystyle S_ {3} = \ {e, (23), (12), (123), (132),(13)\}}$

więc jego indeks cyklu to:

${\ Displaystyle Z (S_ {3}) = {\ Frac {1} {6}} \ lewo (a_ {1} ^ {3} + 3a_ {1} a_ {2} + 2a_ {3} \ prawo). }$

Grupa permutacji G na zbiorze X jest przechodnia , jeśli dla każdej pary elementów x i y w X istnieje co najmniej jedno g w G takie, że y = x ^g . Grupa permutacji przechodnich jest regularna (lub czasami określana jako ostro przechodnia ), jeśli jedyną permutacją w grupie, która ma stałe punkty, jest permutacja tożsamościowa.

Skończona przechodnia grupa permutacji G na zbiorze X jest regularna wtedy i tylko wtedy, gdy | G | = | X |. Twierdzenie Cayleya stwierdza, że ​​każda grupa abstrakcyjna ma reprezentację permutacji regularnej, którą daje grupa działająca na siebie (jako zbiór) przez (prawo) mnożenie. Nazywa się to regularną reprezentacją grupy.

Grupa cykliczna C ₆ w swojej regularnej reprezentacji zawiera sześć permutacji (najpierw podawana jest jednokreskowa postać permutacji):

[1 2 3 4 5 6] = (1)(2)(3)(4)(5)(6) [2 3 4 5 6 1] = (1 2 3 4 5

6)

[3 4 5 6 1 2] = (1 3 5)(2 4 6)

[4 5 6 1 2 3] = (1 4)(2 5)(3 6) [5 6

1 2 3 4] = (1 5 3)(2 6 4)

[6 1 2 3 4 5] = (1 6 5 4 3 2).

Zatem jego indeks cyklu wynosi:

${\ Displaystyle Z (C_ {6}) = {\ Frac {1} {6}} \ lewo (a_ {1} ^ {6} + a_ {2} ^ {3} + 2a_ {3} ^ {2} +2a_{6}\prawo).}$

Często, gdy autor nie chce używać terminologii działań grupowych, grupie permutacji, której to dotyczy, nadaje się nazwę, która sugeruje, czym jest działanie. Poniższe trzy przykłady ilustrują tę kwestię.

Indeks cyklu grupy permutacji krawędzi pełnego wykresu na trzech wierzchołkach

Cały graf K ₃ utożsamimy z trójkątem równobocznym na płaszczyźnie euklidesowej . To pozwala nam używać języka geometrycznego do opisywania permutacji jako symetrii trójkąta równobocznego. Każda permutacja w grupie S ₃ permutacji wierzchołkowych ( S 3 _w swoim naturalnym działaniu, podanym powyżej) indukuje permutację krawędziową. Są to permutacje:

• Tożsamość: żadne wierzchołki nie są permutowane ani krawędzie; wkład ${\ displaystyle a_ {1} ^ {3}.}$
• Trzy odbicia w osi przechodzącej przez wierzchołek i środek przeciwległej krawędzi: ustalają jedną krawędź (tę, która nie pada na wierzchołek) i wymieniają pozostałe dwa; wkład wynosi ${\ Displaystyle 3a_ {1} a_ {2}.}$
• Dwa obroty, jeden zgodnie z ruchem wskazówek zegara, drugi przeciwnie do ruchu wskazówek zegara: tworzą cykl trzech krawędzi; wkład wynosi ${\ displaystyle 2a_ {3}.}$

Indeks cyklu grupy G permutacji krawędzi indukowanych przez permutacje wierzchołków z S ₃ wynosi

${\ Displaystyle Z (G) = {\ Frac {1} {6}} \ lewo (a_ {1} ^ {3} + 3a_ {1} a_ {2} + 2a_ {3} \ prawo).}$

Zdarza się, że pełny graf K ₃ jest izomorficzny z własnym grafem liniowym (podwójny wierzchołek-krawędź), a zatem grupa permutacji krawędzi indukowana przez grupę permutacji wierzchołków jest taka sama jak grupa permutacji wierzchołków, a mianowicie S _{3 ,} a indeks cyklu wynosi Z ( S ₃ ). Nie dotyczy to kompletnych wykresów na więcej niż trzech wierzchołkach, ponieważ mają one dokładnie więcej krawędzi ( ${\ Displaystyle {\ binom {n} {2}}}$ ) niż wierzchołków ( n ).

Indeks cyklu grupy permutacji krawędzi pełnego wykresu na czterech wierzchołkach

Jest to całkowicie analogiczne do przypadku trzech wierzchołków. Są to permutacje wierzchołków ( S ₄ w swoim naturalnym działaniu) i permutacje krawędzi ( S ₄ działające na nieuporządkowanych parach), które indukują:

• Tożsamość: ta permutacja odwzorowuje wszystkie wierzchołki (a więc i krawędzie) na siebie, a wkład ${\ displaystyle a_ {1} ^ {6}.}$
• Sześć permutacji, które wymieniają dwa wierzchołki: te permutacje zachowują krawędź łączącą dwa wierzchołki, a także krawędź łączącą dwa wierzchołki, które nie zostały zamienione. Pozostałe krawędzie tworzą dwa dwucykle i wkład wynosi ${\ Displaystyle 6a_ {1} ^ {2} a_ {2} ^ {2}.}$
• Osiem permutacji, które ustalają jeden wierzchołek i tworzą trzy cykle dla trzech nieustalonych wierzchołków: Te permutacje tworzą dwa trzy cykle krawędzi, jeden zawierający te, które nie występują na wierzchołku, a drugi zawiera te, które występują na wierzchołku; wkład wynosi ${\ Displaystyle 8a_ {3} ^ {2}.}$
• Trzy permutacje, które wymieniają jednocześnie dwie pary wierzchołków: te permutacje zachowują dwie krawędzie łączące dwie pary. Pozostałe krawędzie tworzą dwa dwucykle, a udział wynosi ${\ Displaystyle 3a_ {1} ^ {2} a_ {2} ^ {2}.}$
• Sześć permutacji, które obracają wierzchołki w czterocyklu: Te permutacje tworzą czterocykl krawędzi (tych, które leżą w cyklu) i wymieniają pozostałe dwie krawędzie; wkład wynosi ${\ Displaystyle 6a_ {2} a_ {4}.}$

Możemy wizualizować typy permutacji geometrycznie jako symetrie czworościanu foremnego . Daje to następujący opis typów permutacji.

• Tożsamość.
• Odbicie w płaszczyźnie zawierającej jedną krawędź i środek przeciwległej krawędzi.
• Obrót o 120 stopni wokół osi przechodzącej przez wierzchołek i środek przeciwległej ściany.
• Obrót o 180 stopni wokół osi łączącej środki dwóch przeciwległych krawędzi.
• Sześć odbić obrotowych o 90 stopni.

Indeks cyklu grupy permutacji krawędzi G z K ₄ wynosi:

${\ Displaystyle Z (G) = {\ Frac {1} {24}} \ lewo (a_ {1} ^ {6} + 9a_ {1} ^ {2} a_ {2} ^ {2} + 8a_ {3 }^{2}+6a_{2}a_{4}\prawo).}$

Indeks cyklu permutacji twarzy sześcianu

Sześcian z kolorowymi twarzami

Rozważmy zwykły sześcian w trójprzestrzeni i jego grupę symetrii (automorfizmów), nazwijmy go C . Permutuje sześć ścian sześcianu. (Możemy również rozważyć permutacje krawędzi lub permutacje wierzchołków). Istnieją dwadzieścia cztery automorfizmy.

• Tożsamość:

Istnieje jedna taka permutacja, a jej wkład ${\ displaystyle a_ {1} ^ {6}.}$

• Sześć 90-stopniowych obrotów twarzy:

obracamy się wokół osi przechodzącej przez środki twarzy i twarz przeciwną. Spowoduje to utrwalenie ściany i ściany przeciwnej oraz utworzenie czterech cykli ścian równoległych do osi obrotu. Wkład wynosi ${\ Displaystyle 6a_ {1} ^ {2} a_ {4}.}$

• Trzy obroty twarzy o 180 stopni:

obracamy się wokół tej samej osi, co w poprzednim przypadku, ale teraz nie ma czterech cykli ścian równoległych do osi , a raczej dwa dwucykle. Wkład wynosi ${\ Displaystyle 3a_ {1} ^ {2} a_ {2} ^ {2}.}$

• Osiem 120-stopniowych obrotów wierzchołków:

tym razem obracamy się wokół osi przechodzącej przez dwa przeciwległe wierzchołki (punkty końcowe głównej przekątnej). Tworzy to dwa trzycykle ścian (ściany padające na ten sam wierzchołek tworzą cykl). Wkład wynosi ${\ Displaystyle 8a_ {3} ^ {2}.}$

• Sześć 180-stopniowych obrotów krawędzi:

Te obroty krawędzi obracają się wokół osi, która przechodzi przez punkty środkowe przeciwległych krawędzi, które nie leżą na tej samej powierzchni i są równoległe do siebie, i zamieniają dwa ściany incydentne na pierwszej krawędzi, dwie ściany incydentne na drugiej krawędzi i dwie ściany, które mają wspólne dwa wierzchołki, ale nie mają krawędzi z dwiema krawędziami, tj. istnieją trzy dwucykle, a wkład wynosi ${\ Displaystyle 6a_ {2} ^ {3}.}$

Wniosek jest taki, że wskaźnik cyklu grupy C wynosi

${\ Displaystyle Z (C) = {\ Frac {1} {24}} \ lewo (a_ {1} ^ {6} + 6a_ {1} ^ {2} a_ {4} + 3a_ {1} ^ {2} }a_{2}^{2}+8a_{3}^{2}+6a_{2}^{3}\prawo).}$

Indeksy cykli niektórych grup permutacji

Grupa tożsamości E _n

Ta grupa zawiera jedną permutację, która naprawia każdy element (musi to być naturalne działanie).

${\ Displaystyle Z (E_ {n}) = a_ {1} ^ {n}.}$

Grupa cykliczna C _n

Grupa cykliczna Cn to grupa obrotów n -kąta foremnego, czyli n elementów równomiernie _{rozmieszczonych} wokół okręgu. Ta grupa ma elementy φ( d ) rzędu d dla każdego dzielnika d od n , gdzie φ ( d ) jest funkcją φ Eulera , podającą liczbę liczb naturalnych mniejszych od d , które są względnie pierwsze od d . W regularnej reprezentacji Cn permutacja rzędu d ma n / d cykli o długości _d , zatem:

${\ Displaystyle Z (C_ {n}) = {\ Frac {1} {n}} \ suma _ {d | n} \ varphi (d) a_ {d} ^ {n / d}.}$

Grupa dwuścienna D _n

Grupa dwuścienna jest podobna do grupy cyklicznej , ale zawiera również odbicia. W swoim naturalnym działaniu

${\ Displaystyle Z (D_ {n}) = {\ Frac {1} {2}} Z (C_ {n}) + {\ rozpocząć {przypadki} {\ Frac {1} {2}} a_ {1} a_ {2}^{(n-1)/2},&n{\mbox{ nieparzyste, }}\\{\frac {1}{4}}\left(a_{1}^{2}a_{2} ^{(n-2)/2}+a_{2}^{n/2}\right),&n{\mbox{ parzyste.}}\end{przypadki}}}$

Naprzemienna grupa A _n

Indeks cyklu grupy naprzemiennej w jej naturalnym działaniu jako grupa permutacji wynosi

${\ Displaystyle Z (A_ {n}) = \ suma _ {j_ {1} + 2j_ {2} + 3j_ {3} + \ cdots + nj_ {n} = n} {\ Frac {1 + (-1) ^{j_{2}+j_{4}+\cdots}}{\prod _{k=1}^{n}k^{j_{k}}j_{k}!}}\prod _{k= 1}^{n}a_{k}^{j_{k}}.}$

Licznik wynosi 2 dla permutacji parzystych i 0 dla permutacji nieparzystych. 2 jest potrzebne, ponieważ ${\ Displaystyle {\ Frac {1} {| A_ {n} |}} = {\ Frac {2} {n!}}$ }

Grupa symetryczna S _n

Indeks cyklu grupy symetrycznej S _n w jej naturalnym działaniu jest określony wzorem:

${\ Displaystyle Z (S_ {n}) = \ suma _ {j_ {1} + 2j_ {2} + 3j_ {3} + \ cdots + nj_ {n} = n} \frac {1}{\prod _{k=1}^{n}k^{j_{k}}j_{k}!}}\prod _{k=1}^{n}a_{k}^ {j_{k}}}$

co można również wyrazić za pomocą pełnych wielomianów Bella :

${\ Displaystyle Z (S_ {n}) = {\ Frac {B_ {n} (0! \, a_ {1}, 1! \, a_ {2}, \ kropki, (n-1)! \, a_ {n})}{n!}}.}$

Formułę tę uzyskuje się przez zliczenie, ile razy może wystąpić dany kształt permutacji. Istnieją trzy $k$ podziel zbiór n etykiet na podzbiory, w których znajdują się podzbiory o rozmiarze . Każdy taki podzbiór generuje ${\ Displaystyle k!/k}$ cykli o długości k . Ale nie rozróżniamy cykli o tej samej wielkości, tj. są one permutowane przez ${\ displaystyle S_ {j_ {k}}}$ . To daje

${\ Displaystyle {\ Frac {n!} {\ prod _ {k = 1} ^ {n} (k!) ^ {j_ {k}}}} \ prod _ {k = 1} ^ {n} \ lewo ({\frac {k!}{k}}\right)^{j_{k}}\prod _{k=1}^{n}{\frac {1}{j_{k}!}}={ \frac {n!}{\prod _{k=1}^{n}k^{j_{k}}j_{k}!}}.}$

Formułę można jeszcze bardziej uprościć, jeśli zsumujemy wskaźniki cykli dla każdego $}$ używając dodatkowej zmiennej, ${\ displaystyle n$ śledzić całkowity rozmiar cykli: n

${\ Displaystyle \ suma \ ograniczenia _ {n \ geq 1} y ^ {n} Z (S_ {n}) = \ suma \ ograniczenia _ {n \ geq 1}\suma _{j_{1}+2j_{2}+3j_{3}+\cdots +nj_{n}=n}\prod _{k=1}^{n}{\frac {a_{ k}^{j_{k}}y^{kj_{k}}}{k^{j_{k}}j_{k}!}}=\prod \limits _{k\geq 1}\sum \limits _{j_{k}\geq 0}{\frac {(a_{k}y^{k})^{j_{k}}}{k^{j_{k}}j_{k}!}}= \prod \limits _{k\geq 1}\exp \left({\frac {a_{k}y^{k}}{k}}\right),}$

dając w ten sposób uproszczoną formę indeksu cyklu ${\ displaystyle S_ {n}}$ :

${\ Displaystyle {\ rozpocząć {wyrównane} Z (S_ {n}) & = [y ^ {n}] \ prod \ ograniczenia _ {k \ geq 1} \ exp \ lewo ({\ Frac {a_ {k} y ^{k}}{k}}\right)\\&=[y^{n}]\exp \left(\sum \limits _{k\geq 1}{\frac {a_{k}y^{ k}}{k}}\prawo).\end{wyrównane}}}$

Istnieje użyteczna rekurencyjna formuła indeksu cyklu grupy symetrycznej. Ustaw ${\ Displaystyle Z (S_ {0}) = 1}$ i rozważ rozmiar l cyklu zawierającego n , gdzie ${\ Displaystyle {\ rozpocząć {macierz} 1 \ równoważnik l \ równoważnik n. \ koniec {macierz}}}$ Istnieją $}}$${\ Displaystyle {\ rozpocząć {macierz}} {n-1 \ wybierz l -1} \ koniec {macierzy$$}$ sposobów wyboru pozostałych cyklu i każdy taki ${\ Displaystyle {\ rozpocząć {macierz} {\ Frac {l!} {l}} = (l-1)! \ koniec {macierz}}}$ różne cykle.

Daje to nawrót

${\ Displaystyle Z (S_ {n}) = {\ Frac {1} {n!}} \ suma _ {g \ w S_ {n}} \ prod _ {k = 1} ^ {n}a_{k}^{j_{k}(g)}={\frac {1}{n!}}\sum _{l=1}^{n}{n-1 \wybierz l-1 }\;(l-1)!\;a_{l}\;(nl)!\;Z(S_{nl})}$

Lub

${\ Displaystyle Z (S_ {n}) = {\ Frac {1} {n}} \ suma _ {l = 1} ^ {n} a_ {l} \; Z (S_ {nl}).}$

Aplikacje

W tej części nieco zmodyfikujemy notację indeksów cykli, wyraźnie włączając nazwy zmiennych. Zatem dla grupy permutacji G napiszemy teraz:

${\ Displaystyle Z (G) = Z (G; a_ {1}, a_ {2}, \ ldots, a_ {n}).}$

₀₀ Niech G będzie grupą działającą na zbiorze X . G indukuje również działanie na k -podzbiorach X i na k -krotkach różnych elementów X (patrz #Przykład dla przypadku k = 2), dla 1 ≤ k ≤ n . Niech f _k i F _k oznaczają odpowiednio liczbę orbit G w tych działaniach. Zgodnie z konwencją ustalamy f = F = 1. Mamy:

a) Zwykła funkcja generująca dla f _k jest dana wzorem:

${\ Displaystyle \ suma _ {k = 0} ^ {n} f_ {k} t ^{k}=Z(G;1+t,1+t^{2},\ldots ,1+t^{n}),}$ i

b) Wykładnicza funkcja generująca dla F _k jest dana wzorem:

${\ Displaystyle \ suma _ {k = 0} ^ {n} F_ {k} t ^ {k} / k! = Z (G; 1 + t, 1,1, \ ldots, 1).}$

Niech G będzie grupą działającą na zbiorze X , a h funkcją od X do Y. Dla dowolnego g w G , h ( xg ) jest również funkcją ^od X do Y. Zatem G indukuje działanie na zbiorze Y ^X wszystkich funkcji od X do Y . Liczba orbit tego działania wynosi Z( G ; b , b , ..., b ) gdzie b = | Y |.

Wynik ten wynika z lematu o liczeniu orbit (znanego również jako lemat Not Burnside'a, ale tradycyjnie nazywany lematem Burnside'a), a ważoną wersją wyniku jest twierdzenie Pólyi o wyliczaniu .

Indeks cyklu jest wielomianem kilku zmiennych, a powyższe wyniki pokazują, że pewne oceny tego wielomianu dają kombinatorycznie istotne wyniki. Jako wielomiany można je również formalnie dodawać, odejmować, różniczkować i całkować. Dziedzina kombinatoryki symbolicznej dostarcza kombinatorycznych interpretacji wyników tych operacji formalnych.

Pytanie, jak wygląda struktura cykli losowej permutacji, jest ważnym pytaniem w analizie algorytmów . Przegląd najważniejszych wyników można znaleźć w statystykach permutacji losowych .

Notatki

•   Brualdi, Richard A. (2010), „14. Pólya Counting”, Introductory Combinatorics (wyd. 5), Upper Saddle River, NJ: Prentice Hall, s. 541–575, ISBN 978-0-13-602040-0
•   Cameron, Peter J. (1994), „15. Wyliczanie w ramach akcji grupowej”, Kombinatoryka: tematy, techniki, algorytmy , Cambridge: Cambridge University Press, s. 245–256, ISBN 0-521-45761-0
•   Dixon, John D.; Mortimer, Brian (1996), Grupy permutacji , Nowy Jork: Springer, ISBN 0-387-94599-7
•   Roberts, Fred S.; Tesman, Barry (2009), „8.5 The Cycle Index”, Applied Combinatorics (wyd. 2), Boca Raton: CRC Press, s. 472–479, ISBN 978-1-4200-9982-9
•   Tucker, Alan (1995), „9.3 The Cycle Index”, Applied Combinatorics (wyd. 3), Nowy Jork: Wiley, s. 365–371, ISBN 0-471-59504-7
•   van Lint, JH; Wilson, RM (1992), „35.Pólya teoria liczenia”, Kurs kombinatoryki , Cambridge: Cambridge University Press, s. 461–474, ISBN 0-521-42260-4

Linki zewnętrzne

• Marko Riedel, Twierdzenie Pólyi o wyliczaniu i metoda symboliczna
• Marko Riedel, Indeksy cykli operatora zbioru / multizbioru i formuła wykładnicza
• Haralda Fripertingera (1997). „Wskaźniki cykli grup liniowych, afinicznych i rzutowych” . Algebra liniowa i jej zastosowania . 263 : 133–156. doi : 10.1016/S0024-3795(96)00530-7 .
• Haralda Fripertingera (1992). „Wyliczanie w teorii muzyki” . Beiträge zur Elektronischen Musik . 1 .