4001: [TJOI2015]概率论
Time Limit: 10
Sec Memory Limit: 128 MB
Description
为了提高智商，ZJY开始学习概率论。有一天，她想到了这样一个问题：对于一颗随机生成的$n$个节点的有根二叉树（所以互相不同构的形态等概率出现），它的叶子节点数的期望是多少呢？
判断两棵树是否同构的伪代码如下：
判断两棵树是否同构的伪代码如下：
算法1：bool Check(T1, T2)
Require：两棵树的节点T1, T2
if T1==null || T2==null then
return T1==null && T2==null
else
return Check(T1->leftson, T2->leftson) && Check(T1->rightson, T2->rightson)
end if
Require：两棵树的节点T1, T2
if T1==null || T2==null then
return T1==null && T2==null
else
return Check(T1->leftson, T2->leftson) && Check(T1->rightson, T2->rightson)
end if
Input
输入一个正整数$N$，代表有根树的结点数
Output
输出这棵树期望的叶子节点数。要求误差小于$1\times10^{-9}$
Sample Input
1
Sample Output
1.000000000
HINT
$1\leqslant
N\leqslant10^9$
Solution
设$ \mathrm P(x)$表示$x$个节点的二叉树叶子节点数的期望，$ f_x$为$x$个节点可构成的不同二叉树的数量，$s_x$为$x$个节点构成的所有不同二叉树的叶子节点的和。由期望的定义可得，$ \mathrm P(x)=\frac{s_x}{f_x}$。
$f_x$的求法是一个经典的卡塔兰数问题：固定某个点为根节点，设其左子树有$a$个节点，右子树有$b$个节点，在此条件下，不同的二叉树的数量等于$f_af_b$。而对于$f_x$，$a+b=x-1$且$ 0\leqslant a\leqslant x-1$。即：$$ f_x=\sum_{i=0}^{x-1}f_i\cdot f_{x-1-i}$$
显然$f_x$是第$x$个卡塔兰数（参见https://en.wikipedia.org/wiki/Catalan_number）。于是，$f_x=\frac1{x+1}\begin{pmatrix}2x\\x\end{pmatrix}$。
我们用相似的方式推导$s_x$的递推式：
固定某个点为根节点，设其左子树有$a$个节点，右子树有$b$个节点，我们首先这考虑左子树对$s_x$的贡献，所有不同的左子树的叶子节点的数量和为$s_a$，每种方案都可以和一个右子树结合得到一棵不同形态的二叉树，结合的方案数为$f_b$，所以左子树对$s_x$的贡献为$s_af_b$。类似地，左右子树的总贡献为$s_af_b+f_as_b$。又因为$a+b=x$，所以：$$ s_x=\sum_{i=0}^{x-1}(s_i\cdot f_{x-1-i}+f_i\cdot
s_{x-1-i})=2\sum_{i=0}^{x-1}s_i\cdot f_{x-1-i}$$
参考卡塔兰数通项公式的推导，我们采用母函数计算$s_x$的通项公式。
我们首先确定$s_0$的值，由于$s_1=2f_0s_0=1$，$s_2=2s_0f_1+2s_1f_0=2$，我们发现$s_0$无论取和值都无法满足条件。于是我们大胆猜测，$s_x$的递推式不适用于第一项。这样，$s_0=0$。
根据普通母函数的定义，设：$$ g(x)=\sum_{n=0}^\infty s_nx^n$$ $$ h(x)=\sum_{n=0}^\infty f_nx^n$$
展开，有$$g(x)=s_0+s_1x+s_2x^2+s_3x^3+...$$ $$h(x)=f_0+f_1x+f_2x^2+f_3x^3+...$$
考虑母函数与递推式的联系：$$ g(x)h(x)=s_0f_0+(s_0f_1+s_1f_0)x+(s_2f_0+s_1f_1+s_0f_2)x^2+...$$
整理，得：$$ g(x)h(x)=\sum_{i=0}^0s_if_{0-i}+(\sum_{i=0}^1s_if_{1-i})x+(\sum_{i=0}^2s_if_{2-i})x^2+...$$
根据$s_x$的递推式：$$ xg(x)h(x)=\sum_{i=0}^0s_if_{0-i}x+(\sum_{i=0}^1s_if_{1-i})x^2+(\sum_{i=0}^2s_if_{2-i})x^3+...$$
$$2xg(x)h(x)=0+s_2x^2+s_3x^3+...$$
即：$$ 2xg(x)h(x)=g\left(x\right)-s_1x$$
结合卡塔兰数的推导：$$\left\{\begin{array}{l}2xg(x)h(x)=g\left(x\right)-x\\xh(x)^2=h(x)-1\end{array}\right.$$
解得：$$\left\{\begin{array}{l}g(x)=\frac
x{\sqrt{1-4x}}\\h(x)=\frac{1-\sqrt{1-4x}}{2x}\end{array}\right.,\left\{\begin{array}{l}g(x)=-\frac
x{\sqrt{1-4x}}\\h(x)=\frac{1+\sqrt{1-4x}}{2x}\end{array}\right.$$
不妨令$g(x)=\frac x{\sqrt{1-4x}} =x(1-4x)^{-\frac12}$，根据二项式定理：$$g(x)=x\sum_{n=0}^\infty\begin{pmatrix}-\frac12\\n\end{pmatrix}\left(-4x\right)^n$$
$$g(x)=x\sum_{n=0}^\infty\frac{(-{\displaystyle\frac12})\times(-{\displaystyle\frac32})\times...\times(-{\displaystyle\frac12}-i+1)}{n!}\left(-4x\right)^n$$
$$g(x)=x\sum_{n=0}^\infty\frac{1\times3\times...\times(2n-1)}{n!}2^nx^n$$
$$g(x)=x\sum_{n=0}^\infty\frac{(2n)!}{n!\cdot
n!} x^n$$
$$ g(x)=x\sum_{n=0}^\infty\begin{pmatrix}2n\\n\end{pmatrix}x^n$$
$$g(x)=\sum_{n=1}^\infty\begin{pmatrix}2n-2\\n-1\end{pmatrix}x^n$$
所以$$s_x=\begin{pmatrix}2x+2\\x+1\end{pmatrix}$$
得到了$s_x$的通项公式。我们可以一眼看出$ \mathrm P(x)=\frac{x^2+x}{4x-2}$。
代码一分钟，公式一下午！
:(