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}\).