P3978 [TJOI2015] 概率论

题目描述

为了提高智商，ZJY 开始学习概率论。有一天，她想到了这样一个问题：对于一棵随机生成的 $n(n\le {10}^9)$ 个结点的有根二叉树（所有互相不同构的形态等概率出现），它的叶子节点数的期望是多少呢？

判断两棵树是否同构的伪代码如下：

$$\overline{)\begin{array}{ll}\mathbf{\text{算法 1}}& \text{Check}(T1,T2)\\ 1& \mathbf{\text{Require: }}\text{ 两棵树的节点}T1,T2\\ 2& \mathbf{\text{if}}T1=\text{null}\mathbf{\text{ or }}T2=\text{null}\mathbf{\text{ then }}\\ 3& \mathbf{\text{return}}T1=\text{null}\mathbf{\text{ and }}T2=\text{null}\\ 4& \mathbf{\text{else}}\\ 5& \mathbf{\text{return}}\text{Check}(T1\to \mathit{leftson},T2\to \mathit{leftson})\\ \mathbf{\text{ and }}\text{Check}(T1\to \mathit{rightson},T2\to \mathit{rightson})\\ 6& \mathbf{\text{endif}}\end{array}}$$

输入格式

输入一个正整数 $n$，表示有根树的结点数。

输出格式

输出这棵树期望的叶子节点数，要求误差小于 ${10}^{-9}$。

输入输出样例 #1

输入 #1

1

输出 #1

1.000000000

输入输出样例 #2

输入 #2

3

输出 #2

1.200000000

说明/提示

数据范围

对于 $30\mathrm{\%}$ 的数据，$1\le n\le 10$。

对于 $70\mathrm{\%}$ 的数据，$1\le n\le 100$。

对于 $100\mathrm{\%}$ 的数据，$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)=nf(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{nf(n-1)}{f(n)}$$

代入卡特兰数的通项公式 $f_n=\frac{C_{2n}^n}{n+1}$ 很容易就得到上式等于 $\frac{n(n+1)}{2(2n-1)}$。