题目描述
为了提高智商，ZJY 开始学习概率论。有一天，她想到了这样一个问题：对于一棵随机生成的 $n (n \le 10^9)$ 个结点的有根二叉树（所有互相不同构的形态等概率出现），它的叶子节点数的期望是多少呢？
判断两棵树是否同构的伪代码如下：
$$ \def\arraystretch{1.2} \begin{array}{ll} \hline \textbf{算法 1}&\text{Check}(T1,T2) \ \hline 1&\textbf{Require: }\text{ 两棵树的节点}T1,T2\ 2&\qquad\textbf{if}\ \ T1=\text{null}\textbf{ or }T2=\text{null}\textbf{ then }\ 3&\qquad\qquad\textbf{return}\ \ T1=\text{null}\textbf{ and }T2=\text{null}\ 4&\qquad\textbf{else}\ 5&\qquad\qquad\textbf{return}\ \text{Check}(T1\to\mathit{leftson},T2\to\mathit{leftson}) \ & \qquad\qquad\qquad \textbf{ and }\text{Check}(T1\to\mathit{rightson},T2\to\mathit{rightson})\ 6&\qquad\textbf{endif}\ \hline \end{array} $$
输入格式
输入一个正整数 $n$，表示有根树的结点数。
输出格式
输出这棵树期望的叶子节点数，要求误差小于 $10^{-9}$。
输入输出样例 #1
输入 #1
1 | |
输出 #1
1 | |
输入输出样例 #2
输入 #2
1 | |
输出 #2
1 | |
说明/提示
数据范围
对于 $30%$ 的数据，$1 \le n \le 10$。
对于 $70%$ 的数据，$1 \le n \le 100$。
对于 $100%$ 的数据，$1 \le n \le 10^9$。
题解
令 $f(n)$ 表示 $n$ 个点的二叉树个数；$g(n)$ 表示 $n$ 个点的所有 $f(n)$ 棵二叉树的叶节点总数。
打表如下：
| n | 1 | 2 | 3 | 4 | 5 | ... |
|---|---|---|---|---|---|---|
| $f_n$ | 1 | 2 | 5 | 14 | 42 | ... |
| $g_n$ | 1 | 2 | 6 | 20 | 70 | ... |
发现规律：$g(n) = n f(n-1)$。证明很简单：
- 对于每棵 $n$ 个点的二叉树，如果里面有 $k$ 个叶节点，那么我们分别把这 $k$ 个叶子删去会得到 $k$ 棵 $n-1$ 个点的二叉树；
- 而每棵 $n-1$ 个点的二叉树恰好有 $n$ 个位置可以悬挂一个新的叶子，所以每棵 $n-1$ 个点的二叉树被得到了 $n$ 次；
- 综上，我们即可得出结论：所有 $n$ 个点的二叉树的叶子个数和等于 $n-1$ 个点的二叉树个数 $\times n$。
那么我们只需要求出 $f$ 即可。而 $f$ 的递推式可以通过枚举左子树结点个数得到：
$$ f(n) = \sum_{i=1}^{n-1} f(i) f(n-i-1) $$
边界是 $f(1) = 1$。
该递推式显然是 Catalan 数列（其实一看那个 $[1, 2, 5, 14, 42]$ 就应该知道，滑稽）。于是答案即为 $$ \frac{g(n)}{f(n)} = \frac{n f(n-1)}{f(n)} $$
代入卡特兰数的通项公式 $f_n = \frac{C_{2n}^{n}}{n+1}$ 很容易就得到上式等于 $\frac{n(n+1)}{2(2n-1)}$。
