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×10−9
Sample Input
1
Sample Output
1.000000000
HINT
1⩽
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}。
代码一分钟，公式一下午！
:(