Matematické Fórum

milan.w · 23. 06. 2013 11:27

Zdravím, potřeboval bych poradit s příkladem

najděte počet všech stromů na daných n vrcholech (v1,v2,..vn) v nichž každý vrchol má stupeň 1, nebo stupeň 3

JohnPeca18

Pomoci mocninovych rad, pokud Z(x) je rada s koeficientmi, kde $z_n$ je pocet stromu na n vrcholech pak plati $Z(x)=xZ(x)+x(Z(x))^3$
z toho $Z(x)=x(Z(x)+Z(x)^3)$
pak pouzijeme Lagrangovu inverzni formuly(LIF) z ceho dostaneme
$z_n=\frac{1}{n}[x^{n-1}](x+x^3)^n$
$z_n=\frac{1}{n}[x^{n-1}]\sum_{i=0}^{n}\binom{n}{i}x^ix^{3(n-i)}$
$[x^{n-1}]$ znaci koeficient u $x^{n-1}$
takze potrebujeme koeficient binomickeho rozvoje, kde je $x^{n-1}$ .
Mne to vyslo $\binom{n}{\frac{2n+1}{2}}$
Takze $z_n=\frac{1}{n}\binom{n}{\frac{2n+1}{2}}$ pro liche n. Pro sude to je 0.
Podobny priklad i s LIF je tady, str. 26
http://kam.mff.cuni.cz/%7Eklazar/kpoc99.ps