Burnsideovo lemma
Buď M konečná neprázdná množina. Buď Sm grupa všech permutací množiny M. Buď H nějaká podgrupa grupy Sm- Označme ~h binární relaci na množině M definovanou pro libovolná a, ů E M předpisem
a ~H b <^> existuje permutace a g H taková, že b = cr(a).
Snadno se ověří, že ~h je relace ekvivalence na množině M. Vzniká tak příslušný rozklad M/^h- Třídy tohoto rozkladu se nazývají orbity v grupě H. Pro libovolný prvek a g M je třída rozkladu M/~H obsahující tento prvek a rovna množině
0H(a) = {a(a) : a g H}
a nazývá se orbita prvku a v grupě H. Uvažujme dále pro libovolný prvek a g M podmnožinu
H(a) = {ae H : a(a) = a}
grupy H. Pak H(a) je očividně podgrupa grupy H a nazývá se stabilizátor prvku a v grupě H. Uvažujme konečně pro libovolný prvek a g M zobrazení
^a-H^ 0H(a)
dané pro libovolnou permutaci a g H předpisem
Pak ipa je surjektivní zobrazení. Zkoumejme jádro tohoto zobrazení. Pro libovolné dvě permutace a, r g H máme
r-1 o (j g a o H(a) = r o
Poslední rovnost je ovšem rovností tříd levého rozkladu grupy H podle její podgrupy H(a). Dvě permutace a, r g H se tedy zobrazením ^a zobrazí na tentýž prvek cr(a) = r(a) orbity On(a) právě tehdy, když tyto permutace a, r leží v téže třídě levého rozkladu H/H(a). Indukuje tedy zobrazení^ bijekci
^a : H/H(a) -+ 0„(a)
danou pro libovolnou permutaci a <E H předpisem
^a(aoH(a)) = a(a).
Je tedy počet prvků orbity On(a) roven počtu tříd levého rozkladu H/H(a) grupy H podle stabilizátoru H(a). Z kurzu algebry víme, že pro počet prvků podgrupy H(a) a pro počet tříd levého rozkladu H / H (a) platí rovnost
\H/H(a)\ • \H(a)\ = \H .
To ale znamená, že máme rovnost
\0H(a)\ ■ \H(a)\ = \H\.
Z této rovnosti mimo jiné plyne, že pro dva prvky a, b G M ležící v téže orbitě grupy H, což znamená, že Oh(^) = On(b), platí též rovnost \H(a)\ = \H(b)\, čili stabilizátory H(a) a H(b) takových prvků jsou podgrupami v H majícími týž počet prvků.
Naší snahou bude určit počet všech orbit v grupě /-/, to jest počet tříd rozkladu M/~h- Pro libovolnou permutaci a množiny M označíme symbolem ji(cr) počet všech cyklů délky 1 v rozkladu permutace a na součin nezávislých cyklů. Jinými slovy, j\(cr) bude počet všech pevných bodů permutace a, to jest počet prvků množiny Pa = {a E M : a(a) = a}.
Nyní jsme již připraveni formulovat a dokázat následující Burnsideovo lemma, někdy nazývané též Cauchyovo-Frobeniovo lemma:
Věta
Buď H podgrupa v grupě Sm- Psk pro počet orbit v této grupě H, to jest pro počet tříd rozkladu M/~Hf platí vztah
M/
h
Řečeno slovy, počet orbit v grupě H je roven průměrnému počtu pevných bodů permutací z grupy H.
Důkaz
Uvedená rovnost je ekvivalentní rovnosti
M/
h
kterou tedy máme dokázat. K tomu účelu uvažme množinu
W = {(a, a) :a EH, aGM, a(a) = a}.
Nyní použijeme následující obrat: budeme počítat velikost množiny 1/1/ dvěma způsoby. Poprvé bereme jednotlivé permutace a £ H a ke každé z nich zjistíme, kolik je možno vzít prvků a £ M tak, aby vznikla dvojice (a, a) z l/l/, to jest tak, aby platilo a(a) = a. Tímto způsobem dospějeme k zjištění, že
w\ = y,\p-\ = T,j^-
Podruhé bereme jednotlivé prvky a G M a ke každému z nich zjistíme, kolik je možno vzít permutací a E H tak, aby vznikla dvojice (a, a) z l/l/, to jest zase tak, aby platilo a(a) = a. Tímto způsobem dojdeme k zjištění, že
1/1/
Ovšem víme již, že stabilizátory prvků z téže orbity grupy H mají týž počet prvků Roztřídíme-li tedy prvky a £ M podle toho, do kterých orbit O grupy H náležejí, můžeme poslední vyjádření velikosti množiny W přepsat ve tvaru
W
y    \°h(u0)\ • \H{u0)
oeM/~H
kde uq je některý (kterýkoliv) prvek orbity O. Pak ovšem Oh(uo) je O. Podle poslední rovnosti odvozené bezprostředně před touto větou jsou ovšem součiny \®h(uo)\ • \ H{uq)\ rovny hodnotě |A7|. Dospíváme tak ke zjištění, že
W\=   y   \h\ = \m/
oeM/~H
Celkem odtud a z předchozího odvození vyplývá, že
h
H
M/
h
H
což bylo třeba dokázat.
□