Wskaźnik cyklu

W kombinatoryki , wykorzystując wskaźnik cyklu jest wielomian w kilku zmiennych , które niesie pewne informacje na temat działań z grupy permutacji . Ten algebraiczny i skondensowany sposób przechowywania informacji jest często używany w problemach z liczeniem .

Każda permutacja π skończonego zbioru dzieli ten zbiór na cykle ; Jednomian wskaźnik cykli Õ jest iloczynem sił zmiennych 1 , 2 , ..., który opisuje „typ” tej partycji, albo typu „cykli” na Õ: wykładnik I jest liczba cykli o długości π i . Cykl wskazujący wielomian grupy permutacji jest średnią z cyklu wskazującego jednomiany elementów tej grupy.

Ten wielomian umożliwia zliczenie orbit działania grupy. Jest to główny składnik twierdzenia Pólya o wyliczaniu . Wykonywanie tych wielomianów, formalne operacje algebraiczne i operacje różniczkowania oraz interpretacja kombinatoryczna, jest sercem kombinatorycznej teorii struktur gatunkowych (in) .

Grupy permutacji i akcje grupowe

Grupa permutacji jest podgrupa o symetrycznym grupa S X z bijections z zestawu X w sobie.

Niech G grupę, a cp jest morfizm grup o G w S X . Φ obrazu ( G ) oznacza grupę o permutacje i danych cp jest równoważny o działaniu G na X , zwany „przedstawia G przez permutacje”.

W zastosowaniach kombinatorycznych bardziej interesuje nas zbiór X niż działająca na niego grupa G ; na przykład chcemy wyliczyć niezmienne struktury na X za pomocą tej akcji. W tym kontekście, tracimy mało koncentrując się bardziej na działaniu grupy permutacji cp ( G ), niż na tym grupy G sama. ( Wręcz przeciwnie, algebraistów bardziej interesują same grupy, a więc jądro φ, które mierzy to, co traci się przechodząc od działania G do działania φ ( G ).)

Definicja

Indeks cyklu grupy permutacji G działających na zbiorze X z n elementami jest wielomianem zmiennych $a 1 , a 2 , ... a n$ :

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

gdzie dla dowolnego elementu g z G i dla każdego $k$ od 1 do n , $j k$ ( g ) jest liczbą $k-$ cykli permutacji X związanej z g . ( Dlatego te liczby naturalne się sprawdzają ). ${\ displaystyle \ scriptstyle \ sum _ {k = 1} ^ {n} kj_ {k} (g) = n}$

Przykład

Stałą obecność grupy cyklicznej C 4 z obrotów na placu jest działanie na zbiorze X = {1, 2, 3, 4} wierzchołków (ponumerowane w trygonometrycznych kierunku ). Dokładniej, obroty kątów 0 °, 90 °, 180 ° i 270 ° działają odpowiednio przez (1) (2) (3) (4), (1 2 3 4), (1 3) (2 4) i (1 4 3 2) i wskaźnik stopnia jednomianów czterech permutacji są $1$ $4$ $,$ $4$ $,$ $2$ $2$ i $4$ . Dlatego wskaźnikiem cyklu dla tej grupy permutacji jest

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

Grupa C 4 działa również naturalnie na zbiorze 6 par wierzchołków, A = {1, 2}, B = {2,3}, C = {3,4}, D = {4, 1}, E = {1,3} i F = {2,4}, które odpowiadają czterem bokom i dwóm przekątnym kwadratu lub, w zupełnie innych ramach, krawędziom całego wykresu K 4 . W tym nowym zestawie cztery elementy grupy działają odpowiednio przez ( A ) ( B ) ( C ) ( D ) ( E ) ( F ), ( ABCD ) ( EF ), ( AC ) ( BD ) ( E ) ( F ) i ( ADCB ) ( E F ), dlatego wskaźnikiem cyklu tego działania jest

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

Można również wykonać C 4 z 16 par wierzchołków (które odpowiadają łukom wykresu skierowanego pełnego D 4 , z pętlą na każdym wierzchołku). Następnie znajdujemy jako wskaźnik

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

Rodzaje działań

Jak pokazuje powyższy przykład, wskaźnik zależy nie tylko od grupy, ale także od jej działania. Ponieważ grupa ma wiele reprezentacji permutacji, przy ich rozróżnieniu pomocna jest niewielka terminologia.

Kiedy grupa jest zdefiniowana jako podgrupa grupy symetrycznej, jest to grupa permutacji, a jej „naturalnym działaniem” jest kanoniczny morfizm włączenia podgrupy do grupy. Na przykład naturalne działanie symetrycznej grupy o wskaźniku 3 ${\ Displaystyle S_ {3} = \ {{\ tekst {id}}, (23), (12), (123), (132), (13) \}}$ posiada wskaźnik cykli ${\ Displaystyle Z (S_ {3}) = {\ Frac {1} {6}} \ lewo (a_ {1} ^ {3} + 3a_ {1} a_ {2} + 2a_ {3} \ prawej). }$
Działanie grupy na samą siebie poprzez tłumaczenia (por . Twierdzenie Cayleya ), po prostu przechodnie , będzie w kontekście tego artykułu nazwane jej „reprezentacją regularną”.
Widzieliśmy już przykład regularnej reprezentacji cyklicznej grupy C 4 . Ta z cyklicznej grupy C 6 zawiera 6 permutacji(1) (2) (3) (4) (5) (6), (1 2 3 4 5 6), (1 3 5) (2 4 6), (1 4) (2 5) (3 6) ), (1 5 3) (2 6 4) oraz (1 6 5 4 3 2)dlatego jego wskaźnik cyklu to ${\ Displaystyle Z (C_ {6}) = {\ Frac {1} {6}} \ lewo (a_ {1} ^ {6} + a_ {2} ^ {3} + 2a_ {3} ^ {2} + 2a_ {6} \ right).}$
W przypadku innych działań wybierz nazwę, która je wywołuje, jak w trzech przykładach poniżej.

Grupa permutacji krawędzi całego wykresu na 3 wierzchołkach

Zakończeniu wykres K 3 jest izomorficzny jego wspomagającej wykresu , a zatem działanie S 3 o 3 krawędzi, wywołanych przez jego naturalne działanie na 3 wierzchołkach jest izomorficzny z tą ostatnią i w związku z tym ten sam wskaźnik cyklu.

Ten przypadek jest wyjątkowy: jeśli n > 3, cały graf K n ma ściśle więcej krawędzi niż wierzchołków.

Grupa permutacji krawędzi całego wykresu na 4 wierzchołkach

Naturalne działanie S 4 na 4 wierzchołki całego grafu K 4 wywołuje akcję na jego 6 krawędziach. Aby wymienić jednomiany wskazujące cykle tego działania na krawędziach, należy postępować dokładnie tak, jak w powyższym przykładzie obliczenia działania C 4 na pary wierzchołków. Nawiasem mówiąc, możemy zidentyfikować K 4 z regularnym czworościanem i zinterpretować te 24 permutacje (wierzchołki i krawędzie) jako izometrie tego czworościanu .

Na tożsamość ustala wszystkie punkty i dlatego wszystkie krawędzie, więc jego Jednomian jest 1 6 .
8 trzecich obrotu osi łączących wierzchołek ze środkiem przeciwległej powierzchni, permutuje kołowo trzy z czterech wierzchołków, a zatem kołowo permutuje trzy krawędzie ich wspólnej powierzchni, jak również trzy pozostałe krawędzie, a więc ich 8 jednomianów są równe a 3 2 .
Trzy półobroty osi łączących środki dwóch przeciwległych krawędzi zamieniają 2 na 2 cztery wierzchołki, dlatego ustalają dwie krawędzie łączące każdą parę odwróconych wierzchołków i zamieniają 2 na 2 dwie pozostałe krawędzie, a zatem ich 3 jednomiany są równe a 1 2 a 2 2 .
Sześć odbić , w odniesieniu do pośredniczących płaszczyzn 6 krawędzi, zamienia dwa wierzchołki, dlatego ustal krawędź, która je łączy z przeciwną krawędzią i zamień 2 na 2 cztery pozostałe krawędzie, więc ich 6 jednomianów nadal jest 1 2 a 2 2 .
Sześć kołowych permutacji czterech wierzchołków (które odpowiadają antyirotacjom ćwierć obrotu) kołowo permutuje cztery z krawędzi i zamienia pozostałe dwa, więc ich 6 jednomianów ma wartość od 2 do 4 .

W związku z tym wskaźnikiem cyklu dla tego działania jest

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

Grupa permutacji ścian sześcianu

Grupa 24 obrotów sześcianu ( izomorficznej na S 4 ) permutacji 8 wierzchołki te krawędzie 12 i 6 powierzchniami tej kostki . Permutacje na twarzach to:

tożsamość, wskaźnik jednomianowy a 1 6
6 ćwierć obrotu osi łączących środki dwóch przeciwległych ścian, które ustalają te dwie ściany i kołowo permutują pozostałe cztery, od jednomianów do 1 2 do 4
3 półobroty tych samych osi, które również ustalają te dwie ściany, ale zamieniają 2 na 2 cztery pozostałe, jednomianów a 1 2 a 2 2
8 trzecich osi obraca się łącząc dwa przeciwległe wierzchołki, które kołowo permutują sześć ścian 3 na 3, od jednomianów do 3 2
6 półobrotów osi łączących punkty środkowe dwóch przeciwległych krawędzi, które zamieniają sześć ścian 2 na 2, z jednomianów na 2 3

Wskaźnikiem cyklu tej grupy permutacji C jest zatem

{\ 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} \ right).}

Wskaźniki cykli niektórych grup permutacji

Oznaczmy przez n „stopień” grupy permutacji G , to znaczy moc zbioru X, na który działa. Dlatego wielomian Z ( G ) ma dla zmiennych $a 1 , a 2 ,\dots a n$ .

Grupa trywialna E n

Grupa trywialna zawiera pojedynczą permutację, która naprawia wszystkie elementy.

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

Grupa cykliczna C n

Cykliczną grupę C n jest grupa obrotów o regularnego wieloboku o n wierzchołków. Ma φ ( d ) elementy rzędu d dla każdego dzielnika d o n , gdzie φ ( d ) jest indicatrix Eulera na D , to znaczy liczby ściśle dodatnie liczby całkowite mniejsze niż lub równe do D , a pierwsza z d . W regularnym przedstawieniu C n permutacja rzędu d ma n / d cykli o długości d , więc

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

Grupa dwuścienna D n

Grupa dwuścienna zawiera grupę cykliczną, ale obejmuje również odbicia. Ze względu na swoje naturalne działanie

{\ Displaystyle Z (D_ {n}) = {\ Frac {1} {2}} Z (C_ {n}) + {\ rozpocząć {przypadków} {\ Frac {1} {2}} a_ {1} a_ {2} ^ {(n-1) / 2} & n {\ mbox {if odd,}} \\ {\ frac {1} {4}} \ left (a_ {1} ^ {2} a_ {2 } ^ {(n-2) / 2} + a_ {2} ^ {n / 2} \ right) & n {\ mbox {if even.}} \ end {cases}}}

Grupa naprzemienna A n

Grupa alternatywna zawiera n ! / 2 parzystych permutacji na n elementach. Ze względu na swoje naturalne działanie

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

Grupa symetryczna S n

Wskaźnikiem cyklu symetrycznej grupy S n dla jej naturalnego działania jest

{\ Displaystyle Z (S_ {n}) = \ suma _ {j_ {1} + 2j_ {2} + 3j_ {3} + \ ldots + kj_ {k} = n} {\ frac {1} {\ prod _ {k = 1} ^ {n} k ^ {j_ {k}} j_ {k}!}} \ prod _ {k = 1} ^ {n} a_ {k} ^ {j_ {k}}.}

Formułę tę uzyskuje się przez zliczenie liczby permutacji każdego typu ( j 1 , ..., j k ) w trzech krokach: liczba przegród tego typu, a następnie dla każdej części o rozmiarze k takiej przegrody liczba k ! / k od okrągłych zleceń (en) na tej części, a następnie uwzględnienie faktu, że jeden nie odróżnia od siebie cykle tej samej długości j k , które są przesuwane przez S j k . To daje dobrze

{\ 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}!}}.}

Ten wskaźnik cykli S n można przepisać w kategoriach pełnych wielomianów Bella :

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

Można go również obliczyć przez indukcję , od Z ( S 0 ) = 1, stosując następujące rozumowanie. Dla n > 0, jeśli p (między 1 a n ) jest rozmiarem cyklu, który zawiera n , istnieją sposoby na wybranie p - 1 pozostałych elementów tego cyklu, a następnie p ! / P rzędów kołowych w tym cyklu, d ' lub ${\ displaystyle \ scriptstyle {n-1 \ wybierz p-1}}$

{\ Displaystyle Z (S_ {n}) = {\ Frac {1} {n!}} \ suma _ {p = 1} ^ {n} {n-1 \ wybierz p-1} ~ {\ Frac {p !} {p}} ~ a_ {p} ~ (np)! ~ Z (S_ {np}) = {\ frac {1} {n}} \ sum _ {p = 1} ^ {n} a_ {p } ~ Z (S_ {np}).}

Aplikacje

Naturalne działanie grupy permutacji G , na zbiorze X o liczności n , wywołuje dla każdej naturalnej liczby całkowitej k ≤ n działanie na zbiorze części X o k elementach i na zbiorze k - części elementów o X ( patrz przykład powyżej dla K = 2). Oznaczmy odpowiednio f k i F k liczbę orbit dla tych dwóch działań. Do odpowiednich serii generowania , które są proste wielomiany zmiennej stopnia n , oblicza się przez podstawienie zmiennych $1$ $,$ $2$ $...$ $n$ w wielomian Z ( G )

zwykły szereg generujący f k jest dany przez ${\ Displaystyle \ sum _ {k = 0} ^ {n} f_ {k} t ^ {k} = Z (G) (1 + t, 1 + t ^ {2}, \ ldots, 1 + t ^ { nie})}$
wykładniczy szereg generatorów F k jest dany przez ${\ Displaystyle \ sum _ {k = 0} ^ {n} F_ {k} {\ Frac {t ^ {k}} {k!}} = Z (G) (1 + t, 1,1, \ ldots , 1).}$

Dla dowolnego zbioru Y , działanie G na X indukuje jedno na zbiorze Y X odwzorowań od X do Y , przez ( gf ) ( x ) = f ( g –1 . X ). Jeśli Y jest skończone, od kard. B , liczba orbit tego indukowanego działania wynosi Z ( G ) ( b , b ,…, b ). Wynik ten jest wydedukowany z lematu Burnside'a lub jego uogólnienia, twierdzenia Pólya o wyliczaniu .

Tak więc wskaźnik cyklu jest wielomianem kilku zmiennych, których niektóre oceny zapewniają wyniki zliczania. Te wielomiany można również formalnie dodawać, odejmować, wyprowadzać i całkować. Te symboliczne kombinatoryki (in) zapewnia kombinatoryczne interpretacje wyników tych operacji.

Pytanie o typ rozpadu w cyklach oraz innych danych statystycznych o losowej permutacji jest ważne w analizie algorytmów .

Uwagi i odniesienia

(fr) Ten artykuł jest częściowo lub w całości zaczerpnięty z artykułu Wikipedii w języku angielskim zatytułowanego „ Cycle index ” ( zobacz listę autorów ) .

(en) Peter J. Cameron , Kombinatoryka: tematy, techniki, algorytmy , CUP ,1994, 355 str. ( ISBN 978-0-521-45761-3 , czytaj online ), s. 227-228
Cameron 1994 , str. 231, pkt 14.3
To właśnie wywołuje regularną ( liniową ) reprezentację grupy.
(w) John D. Dixon i Brian Mortimer , Switching Groups , Springer , al. " GTM " ( N O 163)1996, 348 str. ( ISBN 978-0-387-94599-6 , czytaj online ) , rozdz. 1.2 („Grupy symetryczne”) , s. 2
(w) JH van Lint i RM Wilson , A Course in Combinatorics , CUP,1992, 530 pkt. ( ISBN 978-0-521-42260-4 ) , str. 464, przykład 35.1
Cameron 1994 , str. 248, propozycja 15.3.1
van Lint i Wilson 1992 , str. 463, Twierdzenie 35.1

Zobacz też

Linki zewnętrzne

(en) Marko Riedel, twierdzenie Pólya o wyliczeniu i metoda symboliczna ,listopad 2009
(en) Harald Fripertinger , „ Wskaźniki cyklu grup liniowych, afinicznych i rzutowych ” , Algebra liniowa i jej zastosowania , t. 263,1997, s. 133-156 ( czytaj online )

Bibliografia

(en) Richard A. Brualdi , Introduction to Combinatorics , Prentice Hall ,2010, 5 th ed. , 605 str. ( ISBN 978-0-13-602040-0 ) , rozdz. 14 („Liczenie Pólya”) , s. 541-575
(w) Fred S. Roberts (w) and Barry Tesman , Applied Combinatorics , CRC Press ,2009, 2 II wyd. , 848 s. ( ISBN 978-1-4200-9982-9 , czytaj online ) , rozdz. 8.5 („Indeks cyklu”) , s. 472-479
(en) Alan Tucker , Applied Combinatorics , Wiley ,1995, 3 e ed. , 462 str. ( ISBN 0-471-59504-7 ) , rozdz. 9.3 („Indeks cykli”) , s. 365-371