Počet neizomorfních kořenových stromů
Uvidíme později, že počet navzájem neizomorfních stromů s daným počtem vrcholů je možné určit, známe-li počty navzájem neizomorfních tzv. kořenových stromů s danými počty vrcholů. Věnujme se tedy nyní navzájem neizomorfním kořenovým stromům.
Buď nejprve G = (V(G), E(G)) obyčejný graf, u kterého je označen jeden
z vrcholů z V(G). Takový graf G nazýváme kořenovým grafem, označený vrchol
a G V(G) nazýváme kořenem grafu G. Dva kořenové grafy G a G s kořeny
a G V(G) a b G V(G) se nazývají izomorfní, existuje-li izomorfismus tp : G —>* G
takový, že (f(a) = b. Kořenovým stromem rozumíme kořenový graf G s kořenem
a G V(G) takový, že sám graf G je stromem.
Chystáme se aplikovat Pólyovu větu k určení počtu navzájem neizomorfních kořenových stromů s daným počtem vrcholů. Množinou obrazců Y bude množina, která z každé třídy navzájem izomorfních kořenových stromů obsahuje právě jeden exemplář. Váhovou funkci w definujeme jako funkci udávající pro každý kořenový strom T E Y počet vrcholů tohoto stromu, to jest w(T) = |\/(7")|. Pro každé kladné celé číslo n označme un počet navzájem neizomorfních kořenových stromů majících n vrcholů. Pak řada u(x) = Yl^Li       Je řadou d(x) z Pólyovy věty.
Vezměme nezáporné celé číslo m a vezměme za M množinu čísel {1,2,..., m}. Uvažujme libovolná zobrazení f : M —>* Y. Každému takovému zobrazení f přiřaďme dále kořenový strom následujícím způsobem. Můžeme předpokládat, že množiny vrcholů kořenových stromů        ^(2)3 • • • 3 f{m) Jsou navzájem disjunktní. Nyní ke všem těmto vrcholům přidáme ještě jeden nový vrchol, spojíme jej hranami s kořeny stromů        f(2),..., f {ni), čímž vznikne nový strom, a prohlásíme tento nově přidaný vrchol za kořen tohoto nově vzniklého stromu. Tento kořen tohoto nového stromu bude mít stupeň m. Přitom tento nový strom bude mít o jeden vrchol více, než je úhrnný počet všech vrcholů stromů
r(2),..., f {ni). Takže počet vrcholů tohoto nového stromu bude o jedničku vyšší než součet vah stromů        f(2),..., f {ni), to jest než váha zobrazení f. Konečně si všimněme orbit zobrazení f : M     Y v grupě ESm. Těmto orbitám odpovídají množiny kořenových stromů, jejichž kořen má stupeň m a které se od sebe navzájem liší, porovnáváme-li je izomorfismem, pouze navíc tím, že také sledujeme, v jakém pořadí bereme hrany vycházející z kořene. Takže těmto orbitám fakticky odpovídají navzájem neizomorfní kořenové stromy, jejichž kořen má stupeň m. Označme tedy u™ počet navzájem neizomorfních kořenových stromů majících n vrcholů, jejichž kořen má stupeň m. Při tomto označení se řada um(x) = Yl^Li u^xn liší od řady D(x) z Pólyovy věty pouze tím, že je oproti ní ještě vynásobena činitelem x — to odpovídá výše popsanému přidání nového vrcholu. Podle Pólyovy věty tedy máme rovnost
Dm(x) = xZ(SM; ď(x), D(x2), ..., u{xm)).
Dále zřejmě pro každé n platí un = X^m=o ^íľ- Tato suma je ve skutečnosti konečná, poněvadž pro m ^ n je Zv™ = 0. Odtud plyne, že
oo
u(x) = ]T um(x).
m=0
Dosazením za um(x) z předchozí rovnosti odtud vyplyne, že
oo
U(x) = ^ xZ(SM\ U{x), U(x2), . . . , Ll(xm)).
m=0
Po rozepsání řady u(x) ve tvaru u(x) = Yl^Lo *Wix"+1 a po vydělení činitelem x přejde poslední rovnost do tvaru
oo oo
^ un+ixn = ^2 z(5m; u(x), u(x2),..., u(xm)).
n=0 m=0
Podle lemmatu o generujících řadách pro cyklové indexy permutačních grup platí
rovnost ^ ^
z(sm; tu ..., tm)xm = exp (-
m=0 i=l
ti i
—x
Dosazením hodnoty 1 za x a řad u(x') za proměnné ŕ; pro všechna kladná celá čísla / do této rovnosti obdržíme vztah
OO OO    _/ j\
Z(SM-u(x), u(x2),u(xm)) = exp(£ ^i).
AT7=0 1 = 1
Spojením této poslední rovnosti s předminulou rovností dostaneme vztah
OO OO    _ /    / \
v- _    n      fsr uixJ
n=0 i=l
Odtud logaritmováním vyjde
" D(x')
OO OO
n=0 i=l
Dále derivováním dostaneme
Eoo    - n      — /   . IX
Konečně vynásobením činitelem x a odstraněním zlomku obdržíme
OO OO OO
A7=l A7=0 1 = 1
Poněvadž u(x) = YľkĹi Uk*k, můžeme v tomto vztahu ještě dále rozepsat
u\x') = Y^kLi kúkxlk~'■ Tímto způsobem po přeznačení indexu n na pravé straně
posléze odvodíme
oo oo oo     oo oo oo oo
E nun+ix" =      -»J+ixJ E (E kukxik-') x'' = J2 -uj+ixJ E E k~u^k-
n=l j=0 i=l   k=l j=0 i=l k=l
Porovnáme koeficienty u xn na obou stranách této rovnosti. Na levé straně máme ovšem koeficient nun+i. Na pravé straně potom máme koeficient Yljlo Uj+i YlHi J2T=i kuk, kde navíc žádáme, aby platilo j + ik = n. Takže j < n. Položme h = n — j. Pak 1 ^ h ^ n a j = n — h. Koeficient u xn na pravé straně potom nabude tvaru J2h=i ^n-h+i YlHi J2T=i ^Uk, přičemž žádáme, aby platilo ik = h. To ale znamená, že k\h. Lze tedy výraz pro koeficient u xn na pravé straně ještě přepsat do tvaru Ylh=i Un-h+i(J2k\h kuk)- Porovnáním koeficientů tak dostáváme rovnost
n
nun+1 = ^2 un-h+i (^2 kuk)
h=l k\h
z níž plyne rovnost
1 n
Un+l = ~ ^ Un-h+1 kUk
n
h=l k\h
která platí pro všechna kladná celá čísla n.
Poněvadž na pravé straně této rovnosti vystupují koeficienty uq s indexy q rovnými nejvýše n, dává tato rovnost spolu s očividným faktem, že ui = 1, rekurentní formuli pro výpočet všech hodnot un.