Pólyova věta pro libovolná zobrazení
Poté co jsme dokázali Pólyovu-de Bruijnovu větu v plné obecnosti, věnujme se jejím speciálním případům, které vyvstanou, když za množinu zobrazení T vezmeme některé speciální podmnožiny množiny YM uzavřené vzhledem ke každé podgrupě H grupy Sm- Znění Pólyovy-de Bruijnovy věty se v některých těchto případech zjednoduší. Jako první se v tomto ohledu nabízí sama celá množina YM.
Zaveďme následující značení pro sumy mocnin proměnných. Pro každé kladné celé číslo k položme
per
Pak s použitím cyklového indexu Z(H) permutační grupy H můžeme zformulovat a dokázat následující Pólyovu větu:
Podle Pólyovy-de Bruijnovy věty platí
' aeH feYM,foa=f
Buď nyní a £ H libovolná, pevně zvolená permutace. Předpokládejme, že a je permutace typu V1^^2^ ... mJm^a\ Nechť rozklad r(a) množiny M indukovaný permutací a pozůstává z podmnožin Q, C2,..., Cq. Připomeňme, že tyto podmnožiny jsou složeny z prvků nezávislých cyklů, na něž se rozpadá permutace a. Pak ovšem platí q = ji(cr) + 72(0") + ■ ■ ■ + jm(o').
Uvědomme si, že požadavek f o a = f znamená, že zobrazení f je konstantní na všech podmnožinách Q, C2,..., Cq. Má tedy smysl v této situaci mluvit o hodnotách f(Ci), f (C2),..., f(Cq). Zobrazení f splňující f o a = f je pak plně určeno touto q-ticí hodnot a pro člen v(f) platí
/ r\ _ I Cl I       I C21 I Cg I
nrJ - xf(Q)xf(c2)' "xf{cqy
Protože pracujeme s množinou YM všech zobrazení f : M —>* Y, mohou být hodnotami f(Ci), f (C2),..., f(Cq) libovolné prvky z Y, odkud plyne, že
£ "(o= E
feYM,foa=f (p1,p2,...,pq)
y\Q\        |C2|    .   .   . \Cq\
Pl    *P2 *Pq '
kde (pi, p25 • • • 5 Pq) probíhá přes všechny uspořádané q-tice prvků z V. Nyní si všimněme, že tuto poslední sumu zřejmě dostaneme roznásobením výrazu
per pGV pGV
To je ale právě součin sum mocnin proměnných
Ji(<r) Ma) m m m jm(a) ^1      ^2 •>
což je výraz, který dostaneme dosazením sum si, S2,..., sm za proměnné ti, t2,..., tm do členu Z(a). Dostáváme tak rovnost
^     v(0 = Z(a; Si, s2,..., sm).
Dosazením tohoto poznatku do vyjádření enumerátoru ^{YM/-/) uvedeného na začátku tohoto důkazu konečně dostáváme
7(yM,H) = — ^2 Z(a;si,s2,... ,sm) = Z(H\s1,s2
•S/77)
což jsme měli ukázat.
□
Uvažme zobrazení w přiřazující každému obrazci p G Y nějaké nezáporné celé číslo w(p) takovým způsobem, že pro každé nezáporné celé číslo n existuje jenom konečný počet obrazců p G Y takových, že w(p) = n. Takové zobrazení w nazveme váhovou funkcí, číslo w(p) nazveme vahou obrazce p.
Za této situace je možno ke každému nezápornému celému číslu n uvažovat nezáporné celé číslo | w—1(r?)|, to jest počet obrazců p G Y dané váhy n. Označme symbolem dn toto posledení celé číslo. Označme dále
oo
d(x) = £ dnxn
n=0
generující řadu pro obrazce dané váhy.
Věnujme se nyní libovolným zobrazením f : M     Y. Vahou takového zobrazení f rozumíme číslo w(f) = ^2aeM w(f(a))- Je~'' dále ^ libovolná podgrupa grupy Sm, můžeme spolu s ní uvažovat orbity libovolných zobrazení f : M —>* Y v grupě EH. Tyto orbity jsme nazvali konfiguracemi. Všimněme si, že jsou-li f^g.M^Y dvě zobrazení z téže konfigurace, to jest platí-li g = ä (f) pro nějakou permutaci a z grupy H, pak pro váhy w(f) a w(g) těchto zobrazení vychází
w(g) = w(ä(f)) = w(foa) = Y^ w(f(v(*))) = E w(f (*)) = w^
poněvadž a je permutací množiny M. Můžeme tedy 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.
Přesvědčíme se dále, že pro každé nezáporné celé číslo a? je počet orbit libovolných zobrazení f : M —>* Y v grupě EH dané váhy n konečný. Tedy počet konfigurací dané váhy a? je konečný. Kdyby totiž mělo váhu n nekonečně mnoho konfigurací, mělo by tuto váhu také nekonečně mnoho zobrazení f : M —>* Y. Pak by ovšem musela být nekonečná také množina U{f(M) : f ^ YM, w(f) = n}, neboť v opačném případě bychom měli nekonečně mnoho zobrazení f : M —>* Y konečné množiny M do konečné podmnožiny množiny Y, což není možné. Musela by tedy tato množina U{f(M) : f ^ YM, w(f) = n} být opravdu nekonečná.
Avšak zde ve sjednocovaných množinách f(M) mohou figurovat pouze obrazce p G Y váhy nejvýše n, neboť w(f) = J2aeM w(f(a)) = n- Měli bychom tedy nekonečnou podmnožinu obrazců p G Y nabývajících jenom konečně mnoha vah w(p) ^ n. To je ale ve sporu s požadavkem na váhovou funkci w, podle něhož ke každé možné váze existuje jenom konečný počet obrazců p G Y této váhy.
Viděli jsme tedy, že pro každé nezáporné celé číslo n je počet všech konfigurací O váhy = n zase nějaké nezáporné celé číslo. Označme symbolem Dn toto
poslední celé číslo. Označme dále
oo
D(x) = Y, DnX"
n=0
generující řadu pro konfigurace dané váhy.
Konečně si povšimněme, že když pro každý obrazec p G Y dosadíme mocninu xw(p) za proměnnou xp do členu v(0), dostaneme tak mocninu xw^°\ To však znamená, že tímto dosazením do enumerátoru ^{YMH) dostaneme řadu D(x). Také si všimněme, že když stejným způsobem dosadíme do sum mocnin proměných si, S2,..., dostaneme řady c/(x), c/(x2),.... To ale znamená, že tímto dosazením nakonec dostaneme z předchozí věty následující speciální podobu Pólyovy věty: