Počet navzájem neizomorfních stromů
Směřujeme k nalezení počtu navzájem neizomorfních stromů s daným počtem vrcholů. Budeme k tomu potřebovat některá speciální tvrzení o stromech.
Tvrzení.
Nechť T = (V(T), E(T)) je strom. Nechť 7~o je podstrom ve stromě T takový, že pro každý automorfismus a stromu T je splněna podmínka:
((x G V(T0) &. a(x) + x)       a(x) $ V( 7b)). (*)
Pak platí následující sdělení. Nechť p E V (T) — V (To), q E V (To) jsou takové vrcholy, že {p, q} E E (T), nechť a je nějaký automorfismus stromu T, nechť a(p) = p', a(q) = q! a nechť je splněno p! E V^To). Potom platí buďto ÍP, q} = {Pf> q'}> anebo q' = q.
Důkaz
Jestliže platí {p, q} = {p/, q'}, pak tvrzení platí. Předpokládejme tedy dále, že {p, q} 7^ {p/, q;}. Ukážeme nejprve, že v tom případě platí {p/, q'} E E(Tq). Postupujeme sporem. Předpokládejme tedy, že {p', q!} ^ E(Tq).
Poněvadž {p, q} G E (T) a a(p) = p7, a(q) = q7, máme {p7, q'} G E (T), protože a je automorfismus stromu T.
Odstraněním hrany {p, q} z množiny E(T) se strom T rozpadne na dva podstromy. Označme Tp ten z těchto podstromů, který obsahuje vrchol p, a označme Tq druhý z těchto podstromů, který obsahuje vrchol q. Podobně odstraněním hrany {p', q'} z množiny E(T) se strom T rozpadne na dva podstromy 7~p/ a Tq/. Z toho, že p ^ ^(7"o) a q G V^To), vyplýva, že {p> ^1 ^ E(Tq) a že tedy podstrom Tq stromu T je celý obsažen v podstromě Tq, takže zejména platí V (To) C \z(7~q).
Protože {p, q} 7^ {p7, q7}, musí pro hranu {p', q7} nastat právě jedna ze dvou možností: buď {p7, q7} G E(TP), nebo {p7, q7} G E(Tq). Poněvadž ale p/ G V^To) a viděli jsme, že V (To) C \z(7~q), máme p/ G V^Tg), a tedy musí nastat druhá možnost, čili {p7, q7} G E(Tq).
Odstraněním hrany {p', q'} z množiny E(Tq) se strom 7~q dále rozpadne na dva podstromy. Označme Tqp> ten z těchto podstromů, který obsahuje vrchol p7, a označme Tqq/ druhý z těchto podstromů, který obsahuje vrchol q7. Pak nastane jedna ze dvou možností: buď q G V(Tqp'), nebo q G \z(7"qc7/). Pokud by ale platilo q G ^/(T'qq/), musela by jediná cesta ve stromě Tq vedoucí z vrcholu p7 do vrcholu q procházet hranou {p', q'}.
Poněvadž ale q G V^To) a p/ G V^To), byla by tato cesta současně jedinou cestou v podstromě 7~o stromu Tq vedoucí z vrcholu p' do vrcholu q. Musela by tedy hrana {p;,q;} ležet v E(To). To ale odporuje našemu současnému předpokladu, že {p', q'} ^ E(To). Musí tedy nastat první z uvedených dvou možností, tedy q G V(Tqp'). To ale znamená, že spojením podstromů Tp a Tqp> hranou {p, q} vznikne podstrom 7"p/, a tedy že podstrom Tqq> je roven podstromu Tq>. Je tedy podstrom Tq> obsažen v podstromě Tq.
Ovšem podstrom Tq> není roven celému podstromu Tq, neboť samozřejmě p/ ^ V(Tqf), zatímco {p', q'} G E(Tq), a tedy p/ G V(Tq). Je tedy množina vrcholů V(Tqf) vlastní podmnožinou množiny V(Tq). Ale zobrazení a je automorfismem stromu T a platí a(p) = p/ a a(q) = q'. Odtud plyne že a zobrazuje bijektivně podstrom Tq na podstrom Tq>. To je však ve sporu s předchozím zjištěním, podle něhož podmnožina vrcholů V(Tq/) není rovna celé množině V(Tq).
Nalezený spor tak potvrzuje naše počáteční tvrzení, že {pf,qf} G E(Tq). Odtud plyne, že q! G V^To), čili a(q) G V^To). Avšak také q G V^To). Vzhledem k tomu, že podstrom Tq splňuje podmínku (*), nutně musí platit a(q) = q, to jest platí rovnost q' = q. □
Řekneme, že hrana {a, b) ve stromě T je symetrická, jestliže existuje automorfismus a stromu T takový, že a(a) = b a cr(fo) = a. Strom T může mít nanejvýš jednu symetrickou hranu. Je-li totiž {a, b} symetrická hrana a je-li a příslušný automorfismus stromu 7", pak odstraněním hrany {a, b} se strom 7" rozpadne na dva podstromy 7~a a 7"^, které musí být navzájem izomorfní, jelikož automorfismus a převádí podstrom 7~a na 7"^ a podstrom 7"^ na 7"a. Musí tedy mít oba podstromy 7"a i 7"^ stejný počet vrcholů. Žádná jiná hrana {a', b'} stromu T pak nemůže analogickou podmínku splnit, neboť taková hrana {a', //} je buď hranou podstromu 7"a nebo podstromu 7"^.
Tvrzení.
Necht T je strom a nechi Tq je maximální podstrom stromu T splňující podmínku (*) z předchozího tvrzení Potom pro každý vrchol c G V (T) existuje automorfismus a stromu T takový, že a(c) G V(Tq). Dále pro každou nesymetrickou hranu {c, d} G E (T) existuje automorfismus a stromu T takový, žea({c,d}) G E(To).
Důkaz.
Jestliže už c G V(Tq), pak za a lze vzít identitu a první část tvrzení platí. Nechť tedy dále c G V (T) — V (To). Předpokládejme nejprve, že tento vrchol c sousedí ve stromě T hranou s některým vrcholem d G V(Tq).
4/12
Pak přidáním vrcholu c a hrany {c, d} k podstromu 7~o vznikne větší podstrom, který označíme 7~q. Protože Tq byl maximální podstrom ve stromě T splňující podmínku (*), podstrom Tq už podmínku (*) nesplňuje. To znamená, že existuje automorfismus a stromu T a vrchol x G V(Tq) takový, že cr(x) / xa přitom a(x) G V(Tq). Jestliže nyní x = c, je a automorfismem, pro nějž a(c) G V(Tq) a zároveň a(c) 7^ c, takže a(c) G V(Tq), a tedy a je hledaným automorfismem. Jestliže však x/c, pak x G V^To) a musí platit a(x) = c, neboť jinak bychom měli a(x) G V^To), takže už podstrom 7"o by nesplňoval podmínku (*). To ale má za následek, že x = a_1(c), takže a-1 je teď hledaným automorfismem.
Předpokládejme tedy dále, že vrchol c nesousedí ve stromě T s žádným vrcholem z V(Tq). Nechť c = xq,xi,...,Xk-i,Xk = d je nějaká cesta ve stromě T z vrcholu c, který ovšem nenáleží do V{Tq), do nějakého vrcholu d G V^To). Postupujeme dále indukcí vzhledem k délce k takové cesty. Vrchol c = xo podle předpokladu nepatří do V{T$) a nesousedí s žádným vrcholem z \/(To), zatímco vrchol Xk-i sousedí s vrcholem Xk = d patřícím do V(Tq). To nutně znamená, že k > 1. Podle předchozího odstavce pak existuje automorfismus a stromu T takový, že a(x/c_i) G V^To). Jestliže a(c) G V^To), pak je a hledaným automorfismem. Nechť tedy dále a(c) ^ V(Tq), to jest <r(xo) ^ ^(7"o). Poněvadž a je automorfismus stromu 7", můžeme dále uvažovat cestu a(xo), cr(xi),..., a(xk-i) ve stromě 7~.
Tato cesta má délku k — l a platí na ní a(xo) ^ V (To), zatímco a(xk-i) G V (To). Můžeme tedy na tuto poslední cestu aplikovat indukční předpoklad, podle něhož existuje automorfismus r stromu T takový, že r(a(xo)) G V (To), to jest r(a(c)) G V (To). V tomto případě je tedy r o a hledaným automorfismem.
Dokažme druhou část našeho tvrzení. Nechť {c, d} je nesymetrickou hranou stromu T. Jestliže {c, d} G E (To), pak za a lze vzít identitu a druhá část tvrzení platí. Nechť tedy dále {c, d} G E(T) — E(To). Podle první části tvrzení existuje automorfismus a stromu T takový, že a(c) G V^To). Jestliže platí též, že <j(d) G V^To), pak a je automorfismem, pro který platí cr({c, d}) G E(To). Předpokládejme tedy dále, že cr(d) ^ V(To). Opět podle první části tvrzení existuje automorfismus r stromu T takový, že r(a(d)) G V^To). Protože hrana {c, d} byla nesymetrickou hranou stromu T a a je automorfismus stromu T, je také hrana {a(c),a(d)} nesymetrickou hranou stromu 7". Z tohoto důvodu nemůže platit rovnost r({a(c), a(d)}) = {a(c),a(d)}, neboť v opačném případě bychom nutně měli r(a(c)) = cr(d) a r(a(d)) = cr(c), protože cr(d) ^ \/(7o), zatímco r(a(c/)) G V^To), takže r(a(c/)) 7^ cr(d). Byla by tedy hrana {a(c), a(d)} symetrickou hranou stromu T, což jsme vyloučili. Nyní můžeme aplikovat předcházející tvrzení z tohoto paragrafu na hranu {a(d),a(c)} stromu T a automorfismus r, neboť cr(d) ^ V(Tq), <j(c) G V(Tq) a r(a(d)) G ^(Tq).
Vzhledem k předchozímu závěru v tomto odstavci důkazu ale může být jmenované předcházející tvrzení z tohoto paragrafu splněno jedině tak, že r(a(c)) = cr(c). Pak ovšem, poněvadž a(c) G V(To), máme r(a(c)) G V(To). Také máme r(a(c/)) G ^(To). Odtud plyne, že r(a({c, c/})) G E(To), takže r o a je nyní hledaný automorfismus. □
Buď nyní T strom. Označme symbolem Aut(7") grupu všech automorfismů stromu 7~. Grupa Aut(7") indukuje grupu permutací na množině V(T) všech vrcholů stromu 7~. Označme vj počet orbit vrcholů z V(T) v této permutační grupě. Grupa Aut(7") rovněž indukuje grupu permutací na množině E(7~) všech hran stromu 7". Označme ej počet orbit hran z E(7") v této permutační grupě. Dále označme Sj počet symetrických hran stromu T (takže s7- = 1 nebo s7- = 0 podle toho, zda strom T má nebo nemá symetrickou hranu). Pro tyto hodnoty platí následující věta.
Věta.
V libovolném stromě T platí rovnost
vT = eT - sT + 1.
Buď opět 7~o maximální podstrom stromu T splňující podmínku (*) z předminulého tvrzení. Podmínka (*) zaručuje, že množina V(Tq) obsahuje z každé orbity vrcholů z V(T) v grupě Aut(7") nejvýše jeden vrchol. Podmínka (*) rovněž zaručuje, že množina E(7~o) obsahuje z každé orbity hran z E(7") v grupě Aut(7") nejvýše jednu hranu. Tato podmínka také zaručuje, že množina E(7"o) neobsahuje symetrickou hranu stromu 7", má-li strom T nějakou. Oproti tomu minulé tvrzení zase zaručuje, že množina V(Tq) z každé orbity vrcholů nějaký vrchol obsahuje a také že množina E(7~o) z každé orbity hran nějakou hranu obsahuje, vyjma orbitu tvořenou symetrickou hranou stromu 7", má-li strom T nějakou. Počet vrcholů podstromu 7~o Je tedy roven právě číslu vj a počet hran podstromu 7~o Je roven právě číslu ej — Sj. Jinak řečeno, máme rovnosti | V(7~o)| = vj a |E(7~o)| = ej — Sj. Ovšem 7~o je strom, takže platí rovnost |\/(7~o)| = |E(7~o)| + 1. Dostáváme tak rovnost vj = čt — st + 1, což je tvrzení naší věty. □
V důkazu následující věty budeme potřebovat ještě pojem hranově kořenového stromu. Tak nazýváme strom 7", v němž je označena jedna nesymetrická hrana jako kořenová. Dva hranově kořenové stromy T b T s kořenovými hranami {a, b} a {c, d} nazveme izomorfní, jestliže existuje izomorfismus (f : T —>* T takový, že V({a,b}) = {c, d}.
Připomeňme, že jsme pro každé kladné celé číslo n označili un počet navzájem neizomorfních kořenových stromů majících n vrcholů a že jsme se zabývali generující řadou u(x) = Yl^Li Un*"- Označme dále un počet navzájem neizomorfních stromů majících n vrcholů a uvažujme generující řadu u(x) = Yl^Li un*n- Vyjádříme nyní řadu u(x) pomocí řady u(x). Platí následující věta.
Věta
Pro generující řady u(x) a u(x) platí rovnost
u(x) = B(x) - -((u(x)f - u(x2))
Důkaz
Vytvoříme-li ze stromu T dva kořenové stromy tím způsobem, že za kořeny zvolíme dva vrcholy p a q stromu 7", budou takto vzniklé kořenové stromy navzájem izomorfní, právě když bude existovat automorfismus a stromu T takový, že a(p) = q, to jest právě když budou oba vrcholy p a q náležet téže orbitě v grupě Aut(7"). To znamená, že ze stromu T lze zvolením jednoho vrcholu za kořen vytvořit právě vj navzájem neizomorfních kořenových stromů.
Vytvoříme-li podobně ze stromu T dva hranově kořenové stromy tím způsobem, že za kořenové hrany zvolíme dvě nesymetrické hrany {a, b} a {c, d} stromu 7", budou takto vzniklé hranově kořenové stromy navzájem izomorfní, právě když bude existovat automorfismus a stromu T takový, že cr({a, b}) = {c, c/}, to jest právě když budou obě hrany {a, b) a {c, d} náležet téže orbitě v grupě Aut(7"). To znamená, že ze stromu T lze zvolením jedné nesymetrické hrany za kořenovou hranu vytvořit právě ej — sj navzájem neizomorfních hranově kořenových stromů.
Označme £n počet navzájem neizomorfních hranově kořenových stromů majících n vrcholů (klademe í\ = 0) a uvažme příslušnou generující řadu í[x) = J2^Li^n><n'■ Označme dále Tn množinu stromů obsahující z každé třídy navzájem izomorfních stromů majících n vrcholů právě jeden strom. Pak podle závěrů učiněných v předchozích dvou odstavcích platí
Sečtením rovností vj — (ej — sj) = 1 pocházejících z předchozí věty přes všechny stromy T G Tn dostaneme
a
TeTn
TeTn
TeTn
TeTn TeTn
a tedy
U n — Un.
Tato rovnost platí pro všechna kladná celá čísla n, takže dostáváme rovnost zahrnující generující řady
D(x) — £(x) = u(x).
Chystáme se použít Pólyovu větu pro injektivní zobrazení, abychom určili řadu £(x). Množinou M bude dvouprvková množina {1,2}. 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 G Y počet vrcholů stromu 7". Takže řada D(x) bude nyní řadou d(x) z Pólyovy věty. Každé injektivní zobrazení f : M —>* Y zadává hranově kořenový strom, který dostaneme, když kořeny stromů f(í) a f(2) spojíme hranou a prohlásíme tuto novou hranu za kořenovou hranu takto vzniklého stromu. Fakt, že zobrazení /"je injektivní, znamená, že tato nová hrana nebude symetrická. Dvě zobrazení f,f.M^Y takto zadávají navzájem izomorfní hranově kořenové stromy právě tehdy, když fa f náležejí do téže orbity grupy ESm . To znamená, že řada £(x) bude nyní řadou D(x) z Pólyovy věty. Připomeňme ještě, že M = {1,2} a že tedy S m je dvouprvková grupa, totiž grupa všech permutací dvouprvkové množiny. Podle Pólyovy věty pro injektivní zobrazení tedy máme rovnost
£(x) = Z(SM;u(x),-u(x2)). Přitom cyklový index grupy S m všech permutací dvouprvkové množiny M je roven
l
Z(SM\t1,t2) = ^ + t2). Dosazením do předchozí rovnosti dostaneme
£(x) = l((u(x))2-u(x2)).
Konečně odtud dosazením za £(x) do rovnosti u(x) — £(x) = u(x), kterou jsme odvodili výše, vyjde
U(x) = D(x)-Í((D(x))2-D(x2)), což je tvrzení věty. □
i