zcmimi's blog

arrow_back卡特兰数共2篇文章

avatar
zcmimi
2020-10-01 16:21:19

定义

H_n = \begin{cases} \sum_{i=1}^n H_{i-1} H_{n-i} & n \ge 2 \\ 1 & n = 0, 1 \end{cases}

avatar
zc
2020-01-22 22:57:00
查看原题

点击跳转

f_n表示n个节点可以构成的二叉树的个数,g_n表示n个节点可以构成的二叉树的叶子节点的总数

打表: 可以发现g_n=nf_{n-1}

证明: 对于每棵有n个节点的二叉树,若它有k个叶子节点,删去后可以得到kn-1个节点的二叉树,而这kn-1个节点的二叉树每棵都有n个位置可以放置新的叶子节点

f_1=1\\ f_n=\sum_{i=1}^{n-1}f_if_{n-i-1}

f其实就是卡特兰数

代入ans=\frac{g_n}{f_n}得到\frac{n(n+1)}{2(2n-1)}

1/1
Search
search