题解 P3978 【[TJOI2015]概率论】

· · 题解

rqy写的太简单啦Orz

生成函数+求导

设g(n)表示有n个节点的二叉树的个数,g(0) = 1

设f(x)表示n个节点的二叉树叶子节点的个数，f_0 = 0,f_1 = 1

那么ans = \frac{f_i}{g_i}

对于g_i

考虑有一颗n个点的二叉树,由于左右字数都是二叉树,枚举左右子树的点数

g_n = \sum_{i = 0}^{n - 1}g_ig_{n - i - 1}

这就是卡特兰数，通项为\frac{C_{2n}^{n}}{n + 1}

对于f_i

枚举左右子树的大小，我们可以有g函数推出,由于左右对称，最后*2

f_n = 2\sum_{i = 0}^{n - 1}f_i*g_{n - i - 1}

我们要找到f与h的关系

另G(x)为g的生成函数，F(x)为f的生成函数

G(x) = x G^2(x) + 1,F(x) = 2xF(x)G(x) + x

对于G(x)他的封闭形式为\frac{1-\sqrt{1-4x}}{2x},(对于另外一根不收敛,舍去)

对F(x)得到F(x) = x * (1 - 4x)^{-\frac{1}{2}}

(xG(x))'=\frac 1{\sqrt{1-4x}}=\frac{F(x)}x xG(x)$的每一项$xg_nx^n = g_nx^{n +1}$求导后变为$(n + 1)g_nx^n$,也就等于等式右边的$\frac{f_{n + 1}x^{n + 1}}{x} = f_{n + 1}x^n$ 也就是说$f_{n + 1} = (n+1)g_n$即$f_n=g_{n-1}

带入g_n =\frac{C_{2n}^{n}}{n + 1} 化简得到

ans =\frac{n(n + 1)}{2(2n + 1)}