概率论

题意

求 $n$个节点随机二叉树的叶子个数期望。

分析

设所有的 $n$个节点的二叉树的叶子个数之和为 $G$，$n$个节点二叉树的总数为 $C$。

则可以枚举根节点的两个儿子的大小来统计：
$$
G[n]=\sum_{i=0}^{n-1}2G[i]C[n-1-i]\\
G[0]=0\\
G[1]=1
$$
求和符号中的数字 2 是根据对称性计算左右子树相互的贡献。

接下来，我们可以将 $G$和 $C$写成卷积的形式：
$$
G=2GCx+1
$$
解得：
$$
G=\frac{x}{1-2Cx}
$$
我们知道，$C$是卡特兰数，而卡特兰数的生成函数恰好是 $\frac{1-\sqrt{1-4x}}{2x}$，因此，我们得到 $G$的生成函数：
$$
G=\frac{x}{\sqrt{1-4x}}
$$
那么，为了求 $[x^n]G(x)$，我们需要将 $G$进行二项式展开，根据广义二项式定理：
$$
\begin{aligned}
G&=\frac{x}{\sqrt{1-4x}}\\
&=x(1-4x)^{-\frac{1}{2}}\\
&=x\sum_{i=0}^{\infty}\binom{-\frac{1}{2}}{i}(-4x)^i\\
&=x\sum_{i=0}^{\infty}\frac{(-\frac{1}{2})^{i\downarrow}}{i!}(-1)^i4^ix^i\\
&=x\sum_{i=0}^{\infty}\frac{(\frac{1}{2})^{i\uparrow}}{i!}4^ix^i\\
&=x\sum_{i=0}^{\infty}\frac{(2i-1)!!}{i!}2^ix^i
\end{aligned}
$$
接下来不好继续分解，我们将我们需要求的期望的表达式写出：
$$
\begin{aligned}
E&=\frac{G[n]}{C[n]}\\
&=\frac{[x^{n-1}]G(x)}{C[n]}\\
&=\frac{2^{n-1}(2n-3)!!n!n!(n+1)}{(n-1)!(2n)!}\\
&=\frac{(n+1)n!(2n)!!(2n-3)!!}{2(2n)!(n-1)!}\\
&=\frac{n(n+1)}{2(2n-1)}
\end{aligned}
$$