Cyklový index permutační grupy
Zápis některých výsledků, k nimž se později dostaneme, se zjednoduší, zavedeme-li pomocný pojem cyklového indexu permutační grupy.
Nechť M je nějaká neprázdná konečná množina mající m prvků. Pišme
M = {<3i, «32, • • •, 3m}. Každou permutaci a množiny M lze zapsat jako součin
několika nezávislých cyklů ve tvaru
k\ + l<2 + • • • + kq = m. Čísla /ci, /c2,..., kq jsou délky cyklů. Připouštíme i cykly délky jedna, které se objeví, když permutace a zobrazí některý prvek na něj samotný. Cykly délky jedna tak jednoznačně odpovídají pevným bodům permutace a. Výše uvedený zápis permutace a je jednoznačný až na pořadí cyklů a způsob, jakým jsou zapsány jednotlivé cykly — cyklus délky k lze zapsat k způsoby podle toho, který prvek je postaven na začátek.
Množiny prvků {cl,...,    }, {cl,..., cj;2},..., {c^,..., cqk } vystupujících ve výše uvedeném rozkladu permutace g na součin nezávislých cyklů tvoří rozklad množiny M. Označme tento rozklad symbolem r(a). Označme dále pro každé / = 1, 2,..., m symbolem j i (a) počet cyklů permutace a délky /.
Přitom {cl,...,    , Ci,..., cj~2,..., c^,...
a =
am} a k tomu
Pak rozklad r(a) množiny M indukovaný permutácia obsahuje pro každé / = 1, 2,..., m právě ji(cr) /-prvkových podmnožin. V této situaci řekneme, že rozklad r(a) je rozkladem typu V1^^2^ ... mJm(a\ O samotné permutaci a pak rovněž řekneme, že je permutací typu V1^^2^ ... mJm(a\ Pak ovšem platí
E™ i Ui(v) = m-
Každé permutaci a množiny M přiřadíme člen, to jest součin proměnných, v proměnných ŕi, Í2,..., tm následovně:
Z (a) = t[l{a) ti2{a) ... tiz{a).
Pak pro dvě permutace a a r množiny M zřejmě platí Z(a) = Z(r) právě tehdy, když a i r indukují rozklad množiny M téhož typu.
Buď nyní H podgrupa v grupě Sm všech permutací množiny M. Pak říkáme, že H je permutační grupa. Cyklovým indexem této permutační grupy H pak nazýváme polynom Z(H) v proměnných ti, £2,..., rm definovaný rovností
Přejeme-li si zvýraznit proměnné, píšeme někdy místo pouhého Z(H) obšírněji Z(H\ ri, t2,..., tm).
Určíme cyklové indexy některých význačných permutačních grup.
Cyklovým indexem celé grupy Sm všech permutací množiny M je polynom
1
Z{SM) =
E
Ol J2,--- Jm)
lji+2j2-\-----\-mjm=m
j1\j2\..Jm\V^...nV™
ují uj2 řJm
L*2    *   *  *     iJ~} *
Poznamenejme, že v této sumě se sčítá, de facto, přes všechny možné typy rozkladů množiny M. Sčítanci příslušnému m-tici (71,72, ••• Jm) odpovídají rozklady množiny M obsahující pro každé / = 1, 2,..., m právě j; /-prvkových podmnožin. V souladu s předchozím označením pak mluvíme o rozkladech typu Vl2h ...mJ™.
Podle definice cyklového indexu Z(Sm) máme rovnost
Z(SM) = ]T Z(a).
S
m
M
Zde \Sm\ — m- Přitom člen Z(a) nezávisí na permutaci a samotné, závisí pouze na typu permutace a. Sloučíme tedy do jednoho sčítance všechny členy odpovídající permutacím stejného typu. Budeme tak sčítat už nikoliv přes všechny permutace a množiny M, ale přes všechny možné typy rozkladů množiny M. Máme-li rozklady typu Vl2^2 ... atV"7, pak v uvedené sumě bude člen t^tí? ... V™ vystupovat s koeficientem, jímž bude počet permutácia množiny M indukujících rozklad množiny M tvpu l7l272 ... nim.
Zbývá si ujasnit, že tento koeficient je roven číslu
j1\j2\..Jm\ 1*2*... mi™
Představme si tedy libovolnou permutaci a množiny M typu Vx2n ... ni171 zapsanou ve tvaru součinu nezávislých cyklů tak, že nejprve jsou uvedeny cykly délky jedna, potom cykly délky dva, atd. V tomto zápisu se objeví prvky 3i, 32,..., am uvedené v nějakém určitém pořadí, tedy tvořící nějakou permutaci množiny M. Takových permutací prvků 3i, 32,..., 3m je celkem m\. Ne všechny tyto permutace ale zadávají zápisy různých permutací a množiny M jako součinů nazávislých cyklů. Při takovém zápisu permutace a totiž nezáleží na pořadí cyklů stejných délek, takže musíme číslo m\ vydělit součinem čísel 71 L/2! .. .jm\, a nezáleží ani na způsobu zápisu jednotlivých cyklů, jakými prvky tyto cykly začínají, takže musíme číslo m\ dále vydělit součinem čísel V1^2 ... atV"7. Takto dospějeme ke shora uvedenému koeficientu.
Cyklovým indexem grupy Am všech sudých permutací množiny M je polynom Z(Am) = Z(Sm\ ri, fc,..., tm) + Z(Sm\ ri, —fc,    ~U,..., { l)m~1tm).
Připomeňme, že cyklus liché délky je sudá permutace a cyklus sudé délky je lichá permutace. Pro paritu permutace a zapsané jako součin nezávislých cyklů jsou tedv určující počtv cvklů sudvch délek.
Takže permutace a je sudá, respektive lichá, je-li 72(0") +        + ••• sudé, respektive liché číslo. Poněvadž pro každou permutaci a je
Z(a; ři, r2,..., řm) + Z(a; ŕi, -ŕ2, í3, —í4, • • •, (—l)m tm)
= Z(a; ti, r2,..., rm) + (-I)7'2"Z(a; ti, r2,..., rm), plyne z předchozí úvahy, že tento polynom je roven 0 pro lichou permutaci a a je roven 2Z(cr) pro sudou permutaci a. Poněvadž dále \AM\ = L^ii, z definice cyklového indexu Z(/4m) vychází
Z(AM)
E z(^) = 4i E 2Z(^)
Odtud a z předchozího pozorování pak vyplývá
JrZ{a\ ti, — ŕ2, í3, — U
cr€S
(-i)m-1fm))
, . . . ,
tm)
1 _^
= Z(5m; ti, t2,..., tm) + Z(Sm; ti, — fc,    — fch • • •, (—l)m ^m)
což bylo potřeba ukázat.
Nechť Cm značí cyklickou podgrupu v grupě Sm řádu m generovanou cyklem
P = (^1 32 ... 3m).
Cyklovým indexem cyklické grupy Cm řádu rn je polynom
m
d\m
m d
d
Zde (f(n) je Eulerova funkce udávající pro každé kladné celé číslo n počet kladných celých čísel, která nepřevyšují n a jsou s n nesoudělná.
Prvky grupy Cm jsou kladné mocniny pk cyklu p = (ai a2 ... am). Každá taková mocnina pk je zřejmě součinem několika nezávislých cyklů stejné délky. Označme symbolem d tuto délku. Pak d\m a permutace pk je součinem ^ nezávislých cyklů délky d. Přispívá tedy tato permutace pk do cyklového indexu Z(Cm) sčítancem
tvaru t£ . Zbývá tak jen určit, s jakým koeficientem se tento sčítanec v cyklovém indexu Z(Cm) objeví. Tento koeficient je roven počtu těch exponentů /c E {1,2,..., m}, pro něž permutace pk je součinem nezávislých cyklů stanovené délky c/, po vydělení řádem m grupy Cm-
K dané délce d nezávislých cyklů, na něž se rozpadá mocnina p cyklu p délky m, uvažme ještě největšího společného dělitele c čísel kam. Při řešení poslední úlohy o obarvení rulety jsme si ujasnili, že pak mocnina pk je permutací téhož typu jako mocnina pc cyklu p. Takže i mocnina pc je součinem nezávislých cyklů délky d, a poněvadž c dělí m, je počet těchto nezávislých cyklů roven číslu c, takže máme rovnost cd = m, a tedy dostáváme c = ^. Dále jsme si ujasnili, že pak počet těch exponentů /c E {1,2,..., m}, pro něž mocnina pk je permutací téhož typu jako mocnina pc, je roven hodnotě Eulerovy funkce (f(d). To ukazuje, že koeficient,
s nímž se sčítanec t j v cyklovém indexu Z(Cm) objeví, je roven číslu (f(d) vydělenému řádem m grupy Cm-
Nechť Dm značí dihedrální grupu stupně m, to jest grupu všech symetrií pravidelného m-úhelníka, jehož vrcholy jsou prvky ai, 32,..., 3m. Tato grupa Dm je složena z m otočení (to jsou prvky cyklické podgrupy Cm) a dále z m osových souměrností. Je-li m liché, pak jde o souměrnosti podle os procházejících středem některé strany m-úhelníka a protilehlým vrcholem. Je-li m sudé, pak jde o y souměrností podle os procházejících protilehlými vrcholy a y souměrností podle os procházejících středy protilehlých stran m-úhelníka. Grupa Dm nná tedy celkem 2m prvků.
Cyklovým indexem dihedrální grupy Dm je polynom
Z{DM) = ^Z{CM) + ^t1t^1
pro m liché a
1 1       HZ m-2
Z(DM) =-Z(Cm) +-{t22 +í?Í22 )
pro A77 sudé.
Skutečně v obou případech symetrie pravidelného m-úhelníka, které jsou otočeními, tedy symetrie z cyklické podgrupy Cm, přispívají do cyklového indexu Z (Dm) příspěvkem
Je-li ni liché, pak každá osová souměrnost m-úhelníka ponechá jeden vrchol na místě a zbývající vrcholy ve dvojicích, které si odpovídají podle dotyčné osy souměrnosti, si navzájem vymění místa. Jsou zde tedy jeden pevný vrchol a
transpozic vrcholů. Člen Z(a) příslušný takové symetrii a je tedy tvaru
m — l
Z (a) = t\t2 2 ■ Tyto osové souměrnosti tedy celkem přispívají do cyklového indexu Z (Dm) příspěvkem
1 m-1 ]_ m-1
— A77ŕiŕ22   = - ŕi ŕ2 2 . 2/7? 2
Je-li ni sudé, pak v osových souměrnostech m-úhelníka podle os procházejících středy protilehlých stran si všechny vrcholy po dvojicích navzájem vymění místa. Je zde tedy y transpozic vrcholů. Clen Z(a) příslušný takové symetrii a je tedy
tvaru Z(cr) = r22 ■ Tyto osové souměrnosti tedy celkem přispívají do cyklového indexu Z(Dm) příspěvkem
1 m  m     1 m
V osových souměrnostech m-úhelníka podle os procházejících dvěma protilehlými vrcholy zůstanou tyto dva vrcholy na místě a zbývající vrcholy si po dvojicích navzájem vymění místa. Jsou zde tedy dva pevné vrcholy a m^L transpozic
m-2
vrcholů. Clen Z(a) příslušný takové symetrii a je pak tvaru Z(a) = ŕ^ŕ2 2 ■ Tyto osové souměrnosti tedy celkem přispívají do cyklového indexu Z(Dm) příspěvkem
1     rn m — 2 1 m — 2
2/77 2
r"L r2    — ^2
Sečtením příslušných příspěvků pak dostaneme očekávaný tvar cyklového indexu Z(DM).