Invariance konfigurací vzhledem k permutacím obrazců
Buď M neprázdná konečná množina mající m prvků a buď Y neprázdná konečná množina mající r\ prvků. Prvky množiny Y nazýváme obrazci. Buď H nějaká podgrupa grupy Sm všech permutací množiny M. Mějme množinu YM všech zobrazení M —>* Y. Buď dále T nějaká podmnožina množiny YM uzavřená vzhledem k podgrupě H. Viděli jsme, že podgrupa H grupy Sm indukuje podgrupu EH grupy Sjf- Připomeňme, že pro každé zobrazení f g T značíme fH orbitu prvku f v podgrupě EH a že platí fH = {foa:a<E H}. Orbity tvaru fH jsme nazývali konfiguracemi. Konečně buď r nějaká permutace množiny obrazců Y. Taková permutace r indukuje permutaci množiny YM danou předpisem g^rog pro každé zobrazení g : M —>* Y. Označme dále pro každé zobrazení f g T symbolem r(fH) množinu zobrazení {r o f o a : a g H}. Za této situace klademe
TT = {f g T : r{fH) = fH}.
Takže TT je množina všech těch zobrazení f g j7, pro něž orbita fH je invariantní vzhledem k permutaci r. Tvrdíme, že podmnožina TT je uzavřená vzhledem k podgrupě H. Skutečně nechť f g j>, takže r(fH) = fH, a nechť p g H. Chceme ukázat, že pak f o p g j>, což znamená, že orbita (f o p)/-/ má být invariantní vzhledem k permutaci r. Ale máme
(f o p)H = {f o p o a : a g H} = {f o a : a g H} = fH,
poněvadž /-/je podgrupa grupy Sm a p E H. Takže dostáváme rovnost orbit (f o p)H = fH. Ovšem orbita fH je podle předpokladu invariantní vzhledem k permutaci r. To dokazuje naše tvrzení.
Můžeme se tedy dále starat o enumerátor 7(Jv3 H). Bude ale vhodné poněkud modifikovat definici tohoto enumerátoru. Buď tv nějaký rozklad množiny obrazců Y. Řekneme, že tento tozklad tv je kompatibilní s permutací r množiny obrazců Y, jestliže pro každý obrazec p G Y platí, že prvky p a r(p) leží ve stejné třídě rozkladu tv. To znamená, že třídy rozkladu tv jsou invariantní vzhledem k permutaci r. Připomeňme, že permutace r se rozpadá na součin několika nezávislých cyklů (včetně cyklů délky 1) a že prostřednictvím těchto cyklů permutace r indukuje rozklad množiny Y, který jsme označili r(r). Třídami rozkladu r(r) jsou množiny prvků jednotlivých nezávislých cyklů, na něž se rozpadá permutace r. Potom rozklad tv množiny Y je kompatibilní s permutací r množiny Y, jestliže každá třída rozkladu tv je sjednocením několika tříd rozkladu r(r), to jest jestliže rozklad r(r) je zjemněním rozkladu tv. Nyní každé třídě C rozkladu tv přiřaďme proměnnou xc a každému zobrazení f G J~T (siřeji každému zobrazení f G J7) přiřaďme člen, to jest součin proměnných, označený v7r(f) a definovaný následovně. Označme ještě pro každý obrazec p G Y symbolem [p\tt třídu rozkladu tv obsahující prvek p. Pak klademe:
váf)= II xin*)]*-
Obdobným argumentem jako dříve se ukáže, že jsou-li f,g dvě zobrazení z podmnožiny T náležející téže orbitě grupy EH, pak členy v7ľ(f) a v7ľ(g) příslušné těmto zobrazením jsou si rovny, to jest platí v7ľ(f) = v7ľ(g). Můžeme tedy pro každou orbitu O v podgrupě EH korektně definovat jí odpovídající člen vn(0) jako člen v^^f), kde /"je některý (kterýkoliv) prvek orbity O. Označme navíc symbolem 9?Ijft,h množinu všech orbit prvků podmnožiny TT v podgrupě EH. V tomto kontextu definujeme enumerátor 77r(J>, H) následovně:
77r(Jv,H)= v«í°y
Podotkněme už jen, že nyní jsou obě množiny M i Y konečné, takže je konečná i množina 9JIjtt,h, a tedy výše uvedená suma bude obsahovat jenom konečný počet sčítanců. Má tedy smysl ptát se na počet konfigurací v množině 9JIjtt,h- Tento počet dostaneme dosazením hodnoty 1 za všechny proměnné do enumerátoru.
Pozastavme se ještě na malý okamžik u porovnání dřívějšího enumerátoru 7(J>, H) a nynějšího enumerátoru t^Jv, H) definovaného prostřednictvím rozkladu tv množiny obrazců Y. Nyní jsme přiřazovali jednotlivé proměnné nikoliv jednotlivým obrazcům z Y, ale celým třídám rozkladu tv množiny Y všech obrazců. Mohli jsme také přiřazovat jednotlivé proměnné přímo obrazcům z Y s tou výhradou, že obrazcům z téže třídy rozkladu tv se přiřadí tatáž proměnná.
Z toho je patrno, že náš nynější enumerator t^Jy, H) vznikne z původního enumerátoru 7(Jv3 H) nějakým ztotožněním některých proměnných. To také znamená, že i v nynějším kontextu platí odpovídající varianta dřívější Pólyovy-de Bruijnovy věty. Nyní jsme připraveni dokázat následující výsledek:
Věta.
Enumerator 77r(J>, H) je dán formulí
' crGH   feT, rof=foa
Poznámka
Požadavek ŕ G J, roŕ = ŕoave vnitřní sumě znamená, žerof = fo<j£ fH, takže r(fH) C /H, a tedy nutně r(fH) = /H. To ale říká, že ve skutečnosti f E Fn
Důkaz
Podle Pólyovy-de Bruijnovy věty máme
^(0
crGH feJrT,foa=f
Přehozením pořadí sčítaní přejde toto vyjádření do tvaru
feTT aeH,foa=f
Pro každé zobrazení f £ TT je počet sčítanců tvaru v7r(f) ve vnitřní sumě poslední formule roven počtu těch permutácia £ H, pro něž f oa = f. Označme symbolem H(f) množinu permutací {a E H : f o a = f}. Pak H(f) je podgrupa grupy H. Fakt, ze f E TT, znamená, že r(fH) = fH, a tedy r o f £ //-/. Je tedy zobrazení r o f tvaru /"op pro nějakou permutaci p £ A7. Nyní podmínka r o f = f o a, to jest podmínka f o p = f o a, platí právě tehdy, když platí podmínka f o a o p~ľ =    to jest právě tehdy, když je splněno a o p~ľ e H (f). Poslední podmínka je ale ekvivalentní tomu, že permutace a leží v pravé třídě grupy H podle její podgrupy H (f) určené permutací p. Poněvadž H (f) je podgrupa grupy H, každá pravá třída grupy H podle podgrupy H (f) má týž počet prvků, jako má podgrupa H (f) sama. Je tedy počet permutácia splňujících podmínku f o a = f roven počtu permutací a splňujících podmínku r o f = f o a. Je tedy možno první z těchto dvou podmínek vyskytující se ve vnitřní sumě v poslední výše uvedené formuli nahradit druhou z těchto dvou podmínek. Dostáváme tak vyjádření
f^TT <tGH', rof=foa
— s
5/13
Zbývá přehodit zpět pořadí sčítání, abychom odtud dostali formuli
K úplnému dokončení důkazu pak už zbývá jen se odvolat na shora uvedenou poznámku.
□
Věnujme se nyní speciálnímu případu, kdy podmnožina T množiny YM je rovna celé množině YM. Pak pro danou permutaci r množiny Y je podmnožina TT rovna množině (VM)^_. Pišme jednodušeji VrM místo (VM)^_. V takovém případě pak máme následující výsledek formulovaný s použitím cyklového indexu Z(H) permutační grupy H:
Enumerátor 77ľ(V7íw, H) je dán formulí
ln(YTM,H) = Z(H; Ai,A2.
kde pro každé í = 1, 2,..., m je
X
t
E<E
Xi
[p]tt
iU
přičemž druhá suma je přes všechny cykly permutace r délky i a pro každý takový cyklus je p některý (kterýkoliv) prvek v tomto cyklu.
Důkaz
Podle předchozí věty je enumerator 7^ VrM, H) dán formulí
iáytm, ") = 4£(   E "»(0
' cr<EH feYM,rof=foa
Podle definice je cyklový index Z(H) permutační grupy H dán formulí
kde Z(cr) je člen v proměnných ti, £2,..., rm definovaný následovně: Připomeňme, že zde pracujeme s typem l^í0"^2^... m*™^ permutace a.
Budeme tedy hotovi, když ukážeme, že pro každou permutaci a G H platí rovnost
^ = Z (a; Ai, A2,..., Am),
feYM,Tof=foa
kde Ai, A2,..., Xm jsou výše definované polynomy. Pokusme se tedy určit posledně jmenovanou sumu. Uvažme k tomu libovolné zobrazení f G YM splňující podmínku r o f = f o a. Vezměme dále libovolný cyklus permutace a délky £ a některý prvek a G M ležící v tomto cyklu. Pak f (a) = p pro některý prvek p G Y. Celý vybraný cyklus permutace a lze pak vypsat ve tvaru
(a<r(a) a2(a) ... ^(a)).
Poněvadž /"(a) = p a platí r o f = f o a, prvky tohoto cyklu se zobrazením /" zobrazí na ^-tici prvků
(pr(p) r2(p) ... T^_1(p)).
Nakonec odtud vyplyne, že f(a£(a)) = r^(/"(a)). Ovšem cr^(a) = a, poněvadž prvek a náležel cyklu permutace a délky £, a dále /"(a) = p. Takže z předchozího poznatku posléze vyplyne, že r£(p) = p. To ale znamená, že délka / cyklu permutace r obsahujícího prvek p dělí délku £ předtím vybraného cyklu permutace a. Dosavadní úvahy lze navíc obrátit.
K vybranému cyklu permutace a délky í lze vzít kterýkoliv cyklus permutace r, jehož délka / dělí^. Pro zvolený prvek a G M ležící ve vybraném cyklu permutace g a pro kterýkoliv prvek p obsažený v cyklu permutace r, který jsme právě vzali, lze uvažovat všechna zobrazení f £ YM taková, že f (a) = p, a navíc taková, že tato f se budou na prvcích vybraného cyklu permutace a chovat ve shodě s tím, jak to bylo popsáno výše. Provedeme-li takovou volbu pro každý cyklus permutace a, bude tím plně určeno jedno pevné zobrazení f £ YM, které bude navíc splňovat podmínku r o f = f o a. Připomeňme ještě znovu, že námi uvažované přiřazení proměnných jednotlivým obrazcům z množiny Y je konstantní na jednotlivých třídách rozkladu 7r, a je proto konstantní i na třídách rozkladu r(r) indukovaného permutací r. Vezmeme-li toto v úvahu, pak z definice členů vn(f) a z právě provedených úvah teď už vyplývá, že
kde Ai, A2,..., Xm jsou polynomy definované výše. Polynom na pravé straně poslední formule je ale vzhledem k definici člene Z(a) právě roven polynomu Z(a; Ai, A2,..., Am). To již dokládá výše uvedené tvrzení, které bylo třeba
E
f€YM,TOf=foa
dokázat.
9/13
Z právě dokázané věty bezprostředně plyne její následující důsledek. Poznamenejme jen, že v něm budou vystupovat veličiny pocházející z typu liiW2^W .. tTjJv(r) permutace r. Připomeňme ještě, že počet konfigurací v množině DJtyM H, to jest počet všech orbit prvků podmnožiny Y1M v podgrupě
EH obdržíme, když do enumerátoru 77ľ(V7íw, H) dosadíme hodnotu 1 za všechny proměnné.
Důsledek.
Počet konfigurací v množině WlyMH je dán rovností
ym h\ — Z(H] 111,112, • • • , Mm)
kde pro každé í = 1, 2,..., m je
iU
□
Jako příklad užití tohoto důsledku řešme následující úlohu.
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. Mějme dále cyklus r délky k na množině všech k barev. Klademe otázku, kolika způsoby lze sektory rulety obarvit, nezáleží-li přitom na pootočení rulety, tak aby takové obarvení bylo invariantní vzhledem k cyklické záměně barev určené zadaným cyklem r. To znamená, že popsanou cyklickou záměnou barev v takovém obarvení má vzniknout jiné obarvení, které se ale od původního obarvení bude lišit jen nějakým pootočením rulety.
Podobně jako v dřívější úloze o obarvení sektorů rulety, i zde množinou M 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 bude nyní celá množina YM a podmnožinou TT množiny YM bude tedy množina Y^1. Podgrupou H grupy Sm všech permutací množiny M bude grupa všech otočení rulety. Pak H bude cyklická grupa řádu n na množině /W, kterou jsme dříve značili symbolem Cm- K této podgrupě Cm vezměme jí odpovídající podgrupu ECm grupy SyM všech permutací množiny Y^1.
Pak orbity prvků z Y^1 v podgrupě ECm budou odpovídat obarvením sektorů rulety, kdy nerozlišujeme mezi obarveními, která se vzájemně liší pouze nějakým pootočením rulety, a to sice jen těm obarvením sektorů rulety, která budou invariantní vzhledem k cyklické záměně barev určené zadaným cyklem r na množině Y.
Směřujeme k aplikaci předchozího důsledku. Grupou H tedy nyní bude cyklická grupa Cm řádu n. Permutací r bude cyklus délky k, v němž se zaměňují všechny barvy z množiny Y. To znamená, že jk{j) = 1 a js(r) = 0 pro všechna s = 1, 2,..., s 7^ k. Takže fíg = k pro všechna í = 1, 2,..., n taková, že k\£, kdežto fi£ = 0 pro všechna ostatní^. Podle předchozího důsledku je potom počet orbit prvků z Yj^ v podgrupě EC/W, to jest počet konfigurací v množině DJtyM c dán rovností
-M
TI
yM r
' T    5 ^-í
Z(CM\0,..., 0, /c, 0,..., 0, /c, 0,
)
/c-l
/c-1
Viděli jsme dříve, že cyklový index Z(Cm) grupy Cm je roven
d\n
Do tohoto cyklového indexu nyní dosazujeme výše určené hodnoty fi^ za proměnné td pro všechna d\n. Hodnota Hd je nenulová a je rovna /c právě tehdy, když k\d. Jestliže tedy kj(n, pak Hd = 0 pro všechna c/|a?, takže v tom případě máme
9Jtv/w
t   ' 1
M
0.
Žádné obarvení sektorů rulety barvami z množiny y v tom případě není invariantní vzhledem k cyklické záměně barev určené daným cyklem r.
Předpokládejme tedy dále, že k\n. Pak hodnoty ji^ jsou nenulové a jsou rovny k pro ty dělitele d\n, které splňují k\d. Takový dělitel d je pak tvaru d = ke pro nějaké e|^. V takovém případě pak dostáváme rovnost
ym c
1 t 5
m
Tolik je tedy všech obarvení sektorů otočné rulety, která jsou invariantní vzhledem k dané cyklické záměně barev.