Počet neizomorfních stromů

Úloha číslo: 4131

Dokažte, že na \(n\) vrcholech je nejvýše \(4^n\) neizomorfních stromů. Vylepšete odhad až na \(\frac{1}{n+1}\binom{2n}{n}\).

  • Nápověda

    Použijte algoritmus izomorfismu stromů.

  • Řešení

    Neizomorfní stromy na \(n\) vrcholech kódujeme posloupnostmi nul a jedniček délky \(2n\). Takových je \(2^{2n}=4^n\).

    Nul a jedniček je však stejně, čili odhad lze zlepšit na \(\binom{2n}{n}\).

    Navíc, nuly a jednicky v těchto posoupnostech lze ovšem zpárovat jako závorky v dobrých uzávorkováních. Takových je \(\frac{1}{n+1}\binom{2n}{n}\).

Obtížnost: Snadná úloha (řešená úvahou nebo přímo z definic)
Úloha na dokazování, ověřování
En translation
	Zaslat komentář k úloze