Matematické Fórum

check_drummer · 20. 09. 2010 21:47

Nechť je funkce t(n,k) dána vztahem (n,k přirozená čísla, n>=k):
$t(n,k)=t(n-1,k)\cdot n + t(n-1,k-1) \cdot (n-k) \cdot \frac{n}{k}$ ,
počáteční podmínky jsou dány:
$t(2,2)=1$
$t(k,k)=0, k \neq 2$
$t(n,1)=0$

(Význam t(n,k): jedná se o počet stromů (koster) na n vrcholech majících právě k vrcholů stupně 1)

Počet stromů na n vrcholech je tedy dán hodnotou b(n), kde:
$b(n)=\sum_{i=2}^{n-1}{t(n,i)}$

Odvoďte explicitní vzorec pro b(n) jakožto funkci proměnné n. (Jak známo, je $b(n)=n^{n-2}$ .)

Úlohu jsem zařadil do této kategorie, protože řešení této rovnice je zejména problém algebraický - grafový pohled by však také mohl pomoci...

Pozn: Hint nemám, zde jsem se zasekl. :-)

Matematické Fórum

#1 20. 09. 2010 21:47

Rekurentní rovnice, počet koster

Zápatí