Pólyova enumerační teorie Nechť M je neprázdná konečná množina mající m prvků a nechť Y je nějaká neprázdná konečná nebo spočetně nekonečná množina. Prvky množiny Y budeme nazývat obrazci. Nechť dále /-/je podgrupa v grupě Sm všech permutací množiny M. Uvažujme množinu YM, to jest množinu všech zobrazení M —>* Y. Mějme dále nějakou podmnožinu T množiny YM s následující vlastností: Pro každou permutaci a z H b pro každé zobrazení ŕ z J také zobrazení f o a náleží do T. O takové podmnožině T množiny YM budeme říkat, že je uzavřená vzhledem k podgrupě H. Každému obrazci p G Y přiřaďme proměnnou xp a každému zobrazení f G T přiřaďme člen, to jest součin proměnných, označený v(f) a definovaný následovně v(f) = II xn*> Ke každé permutaci a G H uvažme zobrazení ä \ T ^ T definované tímto předpisem: pro každé f G T klademe (ř(f) = f o a. Tato definice je korektní, poněvadž podmnožina T je uzavřená vzhledem k podgrupě H. Ukážeme dále, že zobrazení ä je permutací podmnožiny T. Je-li g G T libovolné zobrazení, pak poněvadž a-1 G H, také zobrazení g o a-1 náleží do T a máme cř(g o a-1) = g o a-1 o a = g\ To ukazuje, že zobrazení čř je surjektivní. Jsou-li dále f, g G T libovolná dvě zobrazení taková, že = <ř(g"), to jest f o a = g o a, pak jistě f o a o a~ľ = g o a o a-1, takže f = g. To ale ukazuje, že zobrazení ä je injektivní. Celkem je tedy ä permutací podmnožiny T. Uvažme množinu permutací EH = {ä : a G H}. Ukážeme, že EH je podgrupa grupy Sjf všech permutací podmnožiny T. Ukážeme totiž, že pro libovolné dvě permutace a, r G H platí ~ä o T = r o a. Skutečně pro libovolné zobrazení f E J7 vychází (ä o T)(f) = <ť(ť(/")) = ľr(f or) = foroa = T~ô~ä(f). Je tedy zobrazení přiřazující každé permutaci a z podgrupy H permutaci ä podmnožiny T antihomomorfismem podgrupy H do grupy Sjr. Obrazem podgrupy H při tomto antihomomorfismu je pak právě množina permutací EH. Je tedy EH antihomomorfním obrazem podgrupy H, takže EH je skutečně podgrupa grupy Sjr. Je tedy EH jistou podgrupou grupy permutací Sjr. Můžeme tedy zkoumat orbity prvků množiny J7, to jest zobrazení z J7, v této podgrupě EH. Tyto orbity budeme nazývat konfiguracemi. Všimněme si, že jsou-li f,g dvě zobrazení z téže konfigurace, to jest, jsou-li f,g dva prvky náležející do téže orbity podgrupy EH, takže platí g" = cř(f) pro nějakou permutaci a z H, pak pro členy v(f) a v(g) příslušné těmto zobrazením f,g vychází: v(g) = V(W)) = v(foa)= Yl Xf(a(a)) = JI Xf(a) = V(f), poněvadž a je permutací množiny M. Můžeme tedy pro každou orbitu O v podgrupě E korektně definovat jí odpovídající člen v(0) jako člen v(f), kde /"je některý (kterýkoliv) prvek orbity O. Označme 9?Ijf,h množinu všech konfigurací, to jest množinu všech orbit prvků množiny T v podgrupě EH. Dále definujme takzvaný enumerátor: *y{F,H) = ]T v{0). Všimněme si, že je-li množina Y nekonečná, pak i množina T může být nekonečná. Poněvadž ale podgrupa /-/je konečná, a tedy také podgrupa EH je konečná, všechny orbity prvků množiny T v podgrupě EH, to jest všechny konfigurace budou konečné. V takovém případě pak množina 97tjr h všech konfigurací bude nekonečná, takže potom i výše uvedená suma bude obsahovat nekonečný počet sčítanců. V této sumě se ale každý myslitelný člen vyskytuje jenom konečně mnohokrát. To je patrné z toho, že ke každé konečné podmnožině Yq množiny Y existuje jenom konečný počet zobrazení M —>* Yq. Lze tedy na výše uvedenou sumu pohlížet jako na sumu navzájem různých členů s koeficienty, jimiž budou nějaká nezáporná celá čísla. My budeme dále vedeni snahou enumerátor 7(jr,/-/) určit. Poznamenejme už jen, že je-li naopak množina Y konečná, potom je konečná i množina 97tjr h všech konfigurací, takže má smysl ptát se na počet těchto konfigurací. Tento počet pak dostaneme dosazením hodnoty 1 za všechny proměnné do enumerátoru. Na tomto místě bude užitečné si rozmyslet, jakým způsobem se právě zavedené pojmy a konstrukce promítnou do situace zkoumané v příkladě o obarvení stěn pravidelného osmistěnu z předchozího paragrafu. Naše nynější množina M bude množinou všech stěn pravidelného osmistěnu. Množina Y bude množinou všech n barev. Naše nynější grupa H bude grupou všech těch permutací množiny M všech stěn osmistěnu, které jsou indukovány symetriemi z grupy K všech přímých symetrií pravidelného osmistěnu. Dřívější množina M zavedená v předchozím příkladě bude v našem nynějším pojetí množinou YM všech zobrazení M —>* Y, což je ovšem množina všech obarvení stěn nehybného osmistěnu. Podmnožinou T množiny YM bude v tomto příkladě celá množina YM. Dřívější grupa H uvažovaná v předchozím příkladě bude v našem nynějším pojetí odpovídat grupě EH. To je teď totiž podgrupa grupy všech permutací množiny YM všech obarvení stěn nehybného osmistěnu, která pozůstává z těch permutací, které jsou vytvořeny permutacemi stěn osmistěnu pocházejícími z naší nynější grupy H. Řešení příkladu z předchozího paragrafu pak vede na nalezení počtu všech orbit prvků množiny YM v podgrupě EH, to jest na nalezení počtu všech konfigurací. Označme U(H) svaz všech podgrup grupy H a V(M) svaz všech rozkladů množiny M. Definujme zobrazení í/j : V(M) —>► U(H) tak, že pro každý rozklad tt množiny M bude ^(tt) podgrupou grupy H pozůstávající ze všech těch permutací množiny M obsažených v H, které nechávají třídy rozkladu tv nehnuty. To znamená, že ^(tt) bude podgrupou grupy H složenou ze všech těch permutací a G H, které splňují podmínku, že cr(N) = N pro každou třídu N rozkladu tt. Připomeňme ještě, že jádrem zobrazení f : M —>* Y rozumíme rozklad množiny M, jehož třídami jsou všechny podmnožiny tvaru f~ľ(p) pro všechny obrazce p ležící v podmnožině f(M) množiny Y. Jádro zobrazení f značíme symbolem kerf. V tomto kontextu máme následující pozorování: Lemma. Pro libovolné zobrazení f : M —>► Y platí: ^(kerf) = {a e H : f o a = f}. Důkaz Permutace a G H náleží podle definice zobrazení ^ do podgrupy i/j(kerf) právě tehdy, když a ponechává nehnuty všechny třídy rozkadu kerf. To nastane právě tehdy, když pro každý prvek a G M platí, že oba prvky a i a (a) patří do téže třídy rozkladu i/j(kerf). To je ale ekvivalentní tomu, že pro každý prvek a G M platí, že f (a) = f (a (a)). To ale právě znamená, že f = f o a. □ Pro každé zobrazení f G T označme fH orbitu prvku f v podgrupě EH. Připomeňme, že fH = {f o a : a G H}. Určíme počet prvků orbity fH: Lemma. Pro libovolné zobrazení f £ J7 je počet prvků orbity fH roven fH Důkaz. Pro libovolné dvě permutace a a r z podgrupy H rovnost f o a = f o r platí právě tehdy, když platí f o a o r-1 = f. Podle předchozího lemmatu je poslední rovnost ekvivalentní tomu, že cror-1 G i/j(kerf). To ale nastává právě tehdy, když permutace a a r leží v téže pravé třídě grupy H podle její podgrupy ^(ker f). Tato úvaha ukazuje, že prvky orbity fH vzájemně jednoznačně odpovídají pravým třídám grupy H podle podgrupy i/;(kerf). Je tedy počet prvků orbity fH roven počtu tříd pravého rozkladu grupy H podle podgrupy i/;(kerf). Na základě formule pro počet tříd pravého rozkladu takto dostáváme, že fH\ = |H/^(kerf) H\ ^(ker f) □ Nyní jsme připraveni dokázat následující Pólyovu-de Bruijnovu větu, která je stěžejním výsledkem tohoto paragrafu: Věta Enumerator 7(j-*, H) je dán formulí H) s|E( £ «o 1 cr =-si £ ( £ -o) 1 crGH feT,foa=f což jsme měli ukázat. □ 8/9 Vraťme se nyní k situaci, kdy množina obrazců Y je konečná. Viděli jsme, že pak také množina všech konfigurací 97tjr h je konečná, takže má smysl ptát se na počet těchto konfigurací. Jak již bylo řečeno, tento počet dostaneme dosazením hodnoty 1 za všechny proměnné do enumerátoru 7(j-*, H). Z předchozí Pólyovy-de Bruijnovy věty takto bezprostředně plyne tento její důsledek: Důsledek. Počet všech konfigurací, to jest počet všech orbit prvků množiny T v podgrupě EH je roven ^-]T \{f G r:fo* = f}}\. □ Na závěr se vraťme ještě jednou k příkladu o obarvení stěn pravidelného osmistěnu z předchozího paragrafu. Tam jsme úlohu najít počet orbit v příslušné permutační grupě řešili s použitím Burnsideova lemmatu. Mělo by být nyní zřejmé, že takřka totožný postup řešení obdržíme, použijeme-li místo toho výše uvedený důsledek Pólyovy-de Bruijnovy věty.