Lemma o generujících řadách pro cyklové indexy permutačních gru
Buď {an}^0 libovolná posloupnost polynomů s reálnými koeficienty v proměnných £1, £2,.... Generující řadou této posloupnosti polynomů rozumíme mocninnou řadu a(x) = Yl^Lo a"x" s Prom^nnou x. Pro tuto generující řadu a(x), pokud je v ní splněno ao = 0, definujeme mocninnou řadu exp(a(x)) předpisem
exp(a(x)) = ^-(a(x))".
L—' A7!
A7=0
Podmínka ao = 0 zde zaručuje, že v poslední sumě bude u každé mocniny xn jen konečný počet nenulových koeficientů.
Buď M konečná množina mající m prvků. Můžeme si například představit, že M = {1, 2,..., m}. Tím je hodnotou m určena i množina M. Platí následující lemma pro generující řadu cyklových indexů Z(Sm\ £i3 £2? • • • 3 rm) grup Sm všech permutací takto pojatých množin M.
Uvažujme mocninnou řadu ^2m=0 Z(Sm\ £i, fc? • • • 3 tm)xm, to jest generující řadu pro polynomy Z(Sm\ £i, fc,..., tm). Pro tuto mocninnou řadu platí rovnost
oo
oo
z(sm; tu ..., tm)xm = exp (-
m=0 /'=1
—x
klademe-li Z^Sq) = 1
Důkaz.
Pro každé nezáporné celé číslo m určíme koeficient u x777 v řadě exp(^^1 yx7). Tento koeficient by se ovšem měl rovnat cyklovému indexu Z(Sm\ ti, fc? • • • 3 rm) Pro ni = 0 je tento koeficient roven 1, což souhlasí s tím, že Z(S$) = 1. Předpokládejme tedy dále, že m > 0.
Máme tedy určit koeficient u x777 v řadě
oo
i=l k=0 i=l
oo    ^ oo
ti i
x
Koeficient u x777 v řadě {YľZi ^x')k Je ovšem roven
Přeformulujeme tuto sumu následovně. Nechť mezi hodnotami /'i, /2,..., i\
v jednotlivém sčítanci v této šuměje j\ hodnot rovných 1, dále 72 hodnot
rovných 2, . .. , až jm hodnot rovných m. Pak ovšem ji+J2 + mmm+ jm = k
a l/i + 2/2 + ■ ■ ■ + rnjm = m. Počet uspořádaných /c-tic (/'i, /2,..., ik), které takto
dají vzniknout týmž parametrům (71,72, • • • Jm), je roven počtu permutací
s opakováním a je dán polynomickým koeficientem
k       \ /c!
,71,72, • • • JmJ      j\\J2\ • • -Jm!
To znamená, že předchozí suma udávající koeficient u x171 v řadě (YľZi ^x')k Je rovna sumě
k\        t£t£ ...ti
E
m
m
jl+J2 + -+Jm = k      JlJZ Jm
lji+2j2-\-----\-mjm=m
Odtud plyne, že koeficient u x171 v řadě exp(J^1 4x') je roven sumě
E
_ K! rlr2 • • • ľm
k=0         ji+J2+---+jm=k    JlJZ Jm lji+2j2-\-----\-mjm=m
_l_f/i fh tJ
ji\j2\..Jm\l*2h...min>1* " n
lji+2j2 + ---+mjm=mJÍ JZ Jm
Podle našich dřívějších poznatků tato poslední suma aleje právě rovna cyklovému
indexu Z(Sm\ ŕi, fc,..., tm) grupy Sm všech permutací množiny M. □
m
m