Pólyova věta pro injektivní zobrazení
Jiným speciálním případem Pólyovy-de Bruijnovy věty je výsledek, který dostaneme, když za množinu zobrazení T vezmeme množinu všech injektivních zobrazení M —>* Y. Označme symbolem YM tuto množinu všech injektivních zobrazení. Tato podmnožina YM je očividně uzavřená vzhledem ke každé podgrupě H grupy Sm- Můžeme tak uvažovat příslušnou permutační grupu EH indukovanou podgrupou H na množině YM. Abychom tuto poslední permutační grupu notačně odlišili od permutační grupy indukované podgrupou H na množině všech zobrazení YM, zavedeme pro ni označení EH.
Připomeňme, že jsme již zavedli následující značení pro sumy mocnin proměnných. Pro každé kladné celé číslo k jsme položili
Pak s použitím cyklového indexu Z(Sm) grupy Sm všech permutací na množině M můžeme zformulovat a dokázat následující Pólyovu větu pro injektivní zobrazení:
Enumerator 7(YM, H) je dán formulí
m'
7( VM, H) = ^- Z(SM; si, -s2, s3, -s4,..., (-l)"7"^)
Dokážeme tuto větu nejprve v případě, kdy H = Sm- Pak se jedná o tvrzení, že enumerator ^y(YM, Sm) je dán formulí
7( VM, SM) = Z(SM; si, -s2, s3, -s4,..., (-l)m_1sm).
Protože podmnožina YM množiny YM je uzavřená vzhledem ke grupě Sm, každá orbita prvků z YM v grupě E5/w je tvořena buď pouze injektivními zobrazeními, anebo pouze neinjektivními zobrazeními. Orbitami prvků z YM v grupě ESm jsou potom právě ty z orbit v grupě ESm, které jsou tvořeny injektivními zobrazeními.
Nyní se věnujme vztahu mezi orbitami prvků z YM v grupě ESm a orbitami prvků z VM v grupě E^M, kde Am je podgrupa všech sudých permutací množiny M. Nechť nejprve Oje orbita v ESm tvořená injektivními zobrazeními. Pak O = {f o a : a £ Sm} pro nějaké pevně zvolené injektivní zobrazení f : M ^ Y.
Položme Oi = {f o a : a E S/v? je sudá permutace}
b O2 = {f ° cr : a E S m je lichá permutace}. Pak ovšem O = č?i U 02- Ukážeme dále, že 0i H O2 = 0- Kdyby existovalo injektivní zobrazení g E 0\ fl 02, bylo by toto zobrazení tvaru /" o <j pro nějakou sudou permutaci g a zároveň tvaru f o r pro nějakou lichou permutaci r. Takže bychom měli rovnost f o a = for, odkud by vzhledem k tomu, že /"je injektivní zobrazení, vyplynula rovnost a = r, což není možné. Takže skutečně 0i n O2 = 0- Dále očividně 0\ je orbitou prvku f v grupě E^M. Přesvědčíme se, že také O2 je orbitou nějakého prvku v grupě EAm. Zvolíme-li pevně nějakou lichou permutaci r, pak množina permutací tvaru {r o a : a E Am} je právě množinou všech lichých permutací množiny M. Takže pak O2 = {f o r o a : a E Am}, čili O2 je orbitou prvku fóry grupě E^M. Celkem tedy vidíme, že každá orbita O v ESm, která je tvořena injektivními zobrazeními, je disjunktním sjednocením dvou orbit v EAm.
Nechť dále Oje orbita v ESm tvořená neinjektivními zobrazeními. Pak O = {f o a : a E Sm} pro nějaké pevně zvolené neinjektivní zobrazení f : M ^ Y. Ukážeme, že pak ve skutečnosti O = {f o r : r E Am} pro toto neinjektivní zobrazení f : M —>► Y, takže O je orbitou prvku f v grupě EÄM. K tomu je třeba ukázat, že každé zobrazení tvaru f o a, kde a G Sm, lze vyjádřit také ve tvaru for pro nějaké r E Am- Je-li a G Am, není už co ukazovat. Nechť tedy a ^ /4m.
Pak, poněvadž zobrazení f není injektivní, existují vzájemně různé prvky a, ů E M takové, že f (a) = f(b). Označíme-li symbolem ů transpozici (sb), pak ovšem platí, že f o ů =    takže f o a = f o ů o a, přičemž ale ů o a G /A/v/.
Zjistili jsme tak, že každá orbita v grupě ESm tvořená injektivními zobrazeními se rozpadá na dvě orbity v grupě EAm a že každá orbita v grupě ESm tvořená neinjektivními zobrazeními je sama orbitou v grupě EAm. Pokud jde tedy o orbity tvořené neinjektivními zobrazeními, nezáleží na tom, zda je uvažujeme v grupě ESm nebo EAm .
Označili jsme symbolem WXymam množinu všech orbit libovolných zobrazení f : M —>* Y v grupě EÄM, symbolem OJIttm a   nnnožinu všech orbit injektivních
zobrazení f : M —>* Y v grupě EÄM, symbolem 9JlyM5M množinu všech orbit libovolných zobrazení f : /W —>* Y v grupě E5/w a symbolem 9ftyM5M množinu
všech orbit injektivních zobrazení f : M ^ Y v grupě ESm . Označme ještě symbolem       množinu všech orbit neinjektivních zobrazení f : M —>* V, ať už v grupě       nebo v grupě ES/W. Pak 9JtyM^M = My^Am U 9DT-
a 9JtyM5M = 9?íyM5M U       Jsou disjunktní sjednocení množin. Pro enumerátory ~{{YM, Am) a 7(Vm,Sm) pak podle předchozího zjištění platí
7
(YM,AM)= <0) = 2 v(0) = 27(YM,SM)
Odtud pro enumerátory ^{YM, Am) a j(Y , Sm) vychází
7(ym,am)=  y, <°)=  E v(°)+ J2v(°)
= 2  £  v(0) +
YM,SM
°emW,su °emW,sM
=  E v(°) + E
7(Vm,Sm) + 7(VM,Sm)
Takže dostáváme
7(yM,SM) = 7(VM,Aw) - 7(VM,SM).
Podle Pólyovy věty pro libovolná zobrazení platí, že
j(YM1AM) = Z(/AM;si,s2,... ,sm) a
j(Ym,Sm) = Z(Sm\5i, s2, ..., sm). Dále z dřívějška víme, že
Z(Am) = Z(Sm\ ŕi, t, • • • 5 rm) + Z(Sm\ ti, — £2, í35 — í4, • • •, (—l)m_1rm), takže dostáváme
Z(^m;5i, s2, ... , sm)
= Z(Sm\ si, ^2,..., sm) + Z(Sm\ si, — s2, s3, —s4,..., (—l)m 1sAT7).
To je ale hodnota enumerátoru 7( vm,/4m). Dosazením takto nalezených hodnot enumerátorů ~f(YM, Am) a j(Ym,Sm) do výše uvedeného vyjádření enumerátoru 7(yM,S/vf) nakonec po odečtení obdržíme
7(VM,SM) = Z(sm;si,-s2,s3,-s4,...,(-l)A77~1sm), což bylo tředa dokázat.
Konečně určíme enumerátor j(YM, H) pro libovolnou podgrupu H grupy Sm-K tomu účelu předešleme následující pozorování. Uvažujme libovolnou orbitu O nějakého injektivního zobrazení f : M —>► y v grupě E5/w. Pak /"(M) je m-prvková podmnožina množiny Y. Je-li g : M —>* Y nějaké jiné zobrazení v orbitě O, pak máme g = f o a pro nějakou permutaci a množiny M. Odtud pak plyne, že g(M) = f(a(M)) = f(M). Je-li naopak h : M —>► V jakékoliv injektivní zobrazení takové, že /?(/W) = f(M), pak f^^M)) = M, kde f"1 : f(/W)     M je inverzní zobrazení k zobrazení f. Takže f~x o h je permutace množiny M b h = f o f~ľ o /?, odkud plyne, že i zobrazení /? náleží do orbity O. Je tedy orbita O množinou všech těch injektivních zobrazení g" : M —>► Y, která splňují g"( M) = f (M). Označme symbolem Yq dotyčnou m-prvkovou podmnožinu f (M) množiny Y. Je tedy orbita
O množinou všech injektivních zobrazení f : M —>* Yq. Orbity v grupě E5/w tak vzájemně jednoznačně odpovídají m-prvkovým podmnožinám množiny Y.
Je-li nyní H podgrupa grupy Sm, je grupa EH podgrupou grupy ESm. Každá orbita O v grupě ESm je proto disjunktním sjednocením nějakých orbit v grupě EH. Chystáme se určit počet těchto sjednocovaných orbit. Všimněme si, že orbita Oje
uzavřenou podmnožinou množiny YM vzhledem k podgrupě H. Proto grupa H
~o
indukuje permutační grupu, označme ji symbolem EH  , na orbitě O. Orbity v této
~o ^ _
grupě EH   jsou pak právě těmi orbitami v grupě EH, z nichž se skládá orbita O.
Podle důsledku Pólyovy-de Bruijnovy věty je počet těchto orbit roven číslu
±fl'z\{feO:fo* = f}}\.
mo,h
Je-li však permutace a G H různá od identity, pak žádné injektivní zobrazení f : M —>* Yq podmínku f o a = f nesplňuje, takže příslušný sčítanec je roven nule. Je-li permutace a identitou, pak podmínku f o a = f splňují všechna injektivní
zobrazení f : M —)► Yq, a těchto zobrazení je celkem m\. Počet orbit v grupě EH
o
je tedy roven číslu \TXq,h
h
Zjistili jsme tak, že každou orbitu O v grupě
ESm tvoří |^ř| orbit v grupě EH. Z tohoto důvodu platí pro příslušné enumerátory
rovnost
oestrt-
77
at7! 77
7(VM,SM)
Odtud a z předchozí části tohoto důkazu tak plyne, že
7(VM,W)
A77!
771
Z(Sm\ si, — s2, s3, — s4,..., (—l)m 1sm)
což jsme měli ukázat.
□
Vraťme se nyní k váhové funkci w na množině Y všech obrazců, kterou jsme zavedli v paragrafu věnovaném Pólyově větě pro libovolná zobrazení. Pro každé nezáporné celé číslo a? jsme symbolem dn označili počet obrazců p £ Y váhy n a dále jsme označili
oo
d(x) = ^2 dnX"
n=0
generující řadu pro obrazce dané váhy.
Oproti onomu dřívějšímu paragrafu se nyní věnujme pouze injektivním zobrazením f : M —>* Y. Stejným způsobem jako v tom již zmíněném paragrafu definujme váhu w(f) takového zobrazení f. Je-li H libovolná podgrupa grupy Sm, můžeme
spolu s ní uvažovat orbity injektivních zobrazení f : M —>* Y v grupě EH, to jest v grupě indukované podgrupou H na množině YM všech injektivních zobrazení. Tyto orbity zase nazýváme konfiguracemi. Stejně jako dříve můžeme pro každou orbitu O v grupě EH korektně definovat její váhu w(0) jako váhu w(f) pro některý (kterýkoliv) prvek f orbity O.
Úvahy uvedené ve zmíněném dřívějším paragrafu dále ukazují, že pro každé nezáporné celé číslo a? je počet orbit injektivních zobrazení f : M —>* Y v grupě EH dané váhy n zase konečný. Tedy počet konfigurací dané váhy a? je konečný. Označme symbolem Dn počet nynějších konfigurací O váhy n, to jest počet orbit O váhy n v grupě EH.
Označme dále
oo
Ď(x) = ^Ď„x"
A7=0
generující řadu pro nynější konfigurace dané váhy.
Nakonec, stejně jako v již zmíněném dřívějším paragrafu, pro každý obrazec p £ Y dosaďme mocninu xw^ za proměnnou xp do členu v(0) pro každou
konfiguraci O. Tímto dosazením do enumerátoru 7( YM, H) tentokrát dostaneme řadu D(x). Stejným způsobem dosaďme do sum mocnin proměnných Si,s2,.... Tím dostaneme řady c/(x), c/(x2),.... To ale tentokrát znamená, že tímto dosazením dostaneme z předchozí věty následující speciální podobu Pólyovy věty pro injektivní zobrazení:
Platí rovnost mocninných řad
_ rrj |
D(x) = —{ Z(SM; d(x),-d(x2), d(x3), -d(xA),(-l)m-1c/(xm)). □