Obarvení rulety podruhé Mějme kolo rulety rozdělené do n sektorů. Každý z těchto sektorů obarvíme jednou barvou z celkového počtu k barev tak, aby byly splněny následující podmínky. Předem jsou dána nezáporná celá čísla r?i, A72,..., n/c taková, že ni + a?2 + • • • + rik = n. Potom za přípustná považujeme taková obarvení sektorů rulety, kdy a?i sektorů je obarveno první barvou, a?2 sektorů je obarveno druhou barvou, ... , až sektorů je obarveno poslední barvou. V této situaci pak klademe otázku, kolik obarvených kol takto můžeme dostat, považujeme-li za stejná taková dvě obarvení, z nichž jedno vznikne z druhého nějakým pootočením rulety. Směřujeme k aplikaci Pólyovy-de Bruijnovy věty. Množinou M zde bude množina všech sektorů rulety. Množinou Y bude množina všech použitých barev. Podmnožinou T množiny YM všech zobrazení f : M —>* Y bude množina všech těch zobrazení f, která zobrazí ni sektorů na první barvu, a?2 sektorů na druhou barvu, . .., až sektorů na poslední barvu. Tato podmnožina T je očividně uzavřená vzhledem ke každé podgrupě grupy Sm všech permutací množiny M. V našem případě podgrupou H grupy Sm bude grupa všech otočení rulety. Pak H bude cyklická grupa, která bude generovaná jedním cyklem 9 délky n zobrazujícím první sektor na druhý sektor, druhý sektor na třetí sektor, .. . , až předposlední sektor na poslední sektor a poslední sektor zase na první sektor. Takže podgrupa H bude pozůstávat ze všech permutací tvaru 9' pro všechna / = 1, 2,..., a?, přičemž 9n bude identita id/v? na množině M. K této podgrupě H vezměme jí odpovídající podgrupu EH grupy Sjr všech permutací podmnožiny T. Pak orbity grupy EH budou odpovídat vzájemně odlišitelným obarvením sektorů rulety. Věnujme se nyní chvíli obecné permutaci 9' grupy H pro nějaké zvolené / = 1, 2,..., a?. Buď r největší společný dělitel čísel / a n a buď s = Pak se permutace 9' skládá z r vzájemně nezávislých cyklů délky s. Skutečně podle Bezoutovy věty máme r = ia — nb pro jistá kladná celá čísla a a b, odkud plyne (9i)a = 9r+nb = 9r. Položíme-li ještě t = Lr pak máme také (<9r)ř = 0'". Z těchto vztahů vyplývá, že permutace 9' a 9r jsou téhož typu (jejich rozklady na součiny nezávislých cyklů mají stejné počty cyklů jednotlivých délek). Poněvadž 9 je cyklus délky n a číslo r dělí číslo n, permutace 9r se zřejmě skládá z r vzájemně nezávislých cyklů délky s. Totéž pak platí také pro permutaci 9'. Navíc pak ŕ ^ s a čísla s a ŕ jsou vzájemně nesoudělná. Počet takových čísel ŕ udává Eulerova funkce ip, je totiž (f(s) rovno počtu těch kladných celých čísel ŕ, která nepřevyšují číslo s a jsou s číslem s nesoudělná. Tolik je také těch permutací tvaru 91, které jsou téhož typu jako permutace 9r pro dané kladné celé číslo r dělící číslo n. Označili jsme symbolem 9JIjt;h množinu všech orbit grupy EH jakožto podgrupy grupy permutací Sjr. Naším úkolem je určit počet prvků množiny 9JIjt;h- Podle důsledku Pólyovy-de Bruijnovy věty je tento počet roven číslu \^H\ = ^^2\{feT:foS = f}\. ' ô e h Zde řád |A7| grupy H je roven číslu n. Prvky ô grupy H jsou všechny permutace tvaru 9' pro všechna / = 1, 2,..., n. Je vidět, že zobrazení f G j7 jakožto zobrazení f : /W —>* Y splňuje podmínku f o ô = f právě tehdy, když f je konstantní na všech třídách rozkladu množiny M na prvky nezávislých cyklů, na něž se rozpadá permutace ô. Ale permutace ô je tvaru 9' pro některé / = 1, 2,..., a?, a tato permutace se rozpadá na r nezávislých cyklů stejné délky s, kde r je největší společný dělitel čísel / a n a s = -r. Rozklad množiny /W na prvky těchto r nezávislých cyklů pak určuje typ dotyčné permutace 9'. Viděli jsme v předchozím odstavci, že daná permutace 9' je téhož typu jako permutace 9r a že počet těch exponentů /, pro něž permutace 9' je téhož typu jako permutace 9r při daném děliteli r čísla n, je roven číslu (f(s). Konečně je patrno, že pro libovolné dvě permutace 9' a 9J grupy H téhož typu platí rovnost \{f G T : f o B1 = f}\ = \{f G T : f o 9j = f}\. Počet těch zobrazení f G j7, která jsou konstantní na všech třídách rozkladu množiny M na prvky nezávislých cyklů permutace 9' totiž závisí pouze na typu permutace 9', nikoliv na permutaci 9' samotné. Ještě poznamenejme, že probíhá-li číslo r všechny dělitele čísla a?, pak také číslo s = -r probíhá všechny dělitele čísla a?. Shrneme-li tyto poznatky, můžeme přepsat shora uvedenou sumu do tvaru |^h| = ^5>(s)|{ŕ* Y, která zobrazí ni prvků na první barvu z Y, ri2 prvků na druhou barvu z Y, .. . , až prvků na poslední barvu z V. Není-li nyní některé z čísel r?i, 172,...,^ dělitelné číslem s, není možné podmínku f o 0r = f splnit, takže příslušný sčítanec ve výše uvedené sumě je roven nule. Stačí tedy sčítat pouze přes ta čísla s, která dělí všechna čísla a?i, a?2, ..., n^. Předchozí suma tak přejde do tvaru \m^.H\ = l Yl rts)\{feT:fo$r = f}\, s\gcó{n1,n2,...,nk} kde rs = n a gcd značí největšího společného dělitele uvedených čísel. Zbývá tak už jen určit počet \{f E T : f o 9r = f}\, to jest počet těch zobrazení f : M —>► Y, která jsou konstantní na všech r třídách rozkladu množiny M na prvky nezávislých cyklů permutace 9r. Tyto třídy jsou všechny velikosti s. Současně tato zobrazení f : M —>* Y mají zobrazit ni prvků na první barvu, a?2 prvků na druhou barvu, .. . , až prvků na poslední barvu. Taková zobrazení f : M ^ Y indukují zobrazení tříd uvedeného rozkladu množiny M do množiny Y, těchto tříd je celkem r = ^, přičemž y tříd se má zobrazit na první barvu, y tříd se má zobrazit na druhou barvu, ... , až y tříd se má zobrazit na poslední barvu. Jedná se tedy o permutace s opakováním, jejichž počet je dán polynomickým koeficientem \{fe T \ fo9r = f} Celkem je tedy počet prvků množiny 9JIjt;h roven \m^\ = -n E ^(s) n L—' s\gcá{n1,n2,...,nk} Tolik je tedy také všech přípustných vzájemně rozlišitelných obarvení sektorů naší rulety.