题意描述
为了提高智商,ZJY开始学习概率论.有一天,她想到了这样一个问题:对于一棵随机生成的(n)个结点的有根二叉树(所有互相不同构的形态等概率出现),它的叶子节点数的期望是多少呢?
判断两棵树是否同构的伪代码如下:
( ext{CHECK}(T1,T2):)
(// ext{两棵树的节点}T1,T2)
(mathbf{if} T1=mathbf{NULL} mathbf{or} T2=mathbf{NULL}:)
(quad mathbf{return} T1=mathbf{NULL} mathbf{and} T2=mathbf{NULL})
(mathbf{else}:)
(quadmathbf{return} ext{CHECK}(T1.leftson,T2.leftson) mathbf{and} ext{CHECK}(T1.rightson,T2.rightson))
分析
首先,我们令(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)个点的二叉树个数( imes n).
那么我们只需要求出(f)即可.而(f)的递推式可以通过枚举左子树结点个数得到:
[f_n=sum_{i=1}^{n-1}f_if_{n-i-1}
]
边界是(f_1=1).应该可以一眼看出来这是Catalan数列(其实一看那个(1,2,5,14,421)就应该知道)
于是答案即为
[frac{g_n}{f_n}=frac{nf_{n-1}}{f_n}
]
代入卡特兰数的通项公式
[f_n=frac{inom{2n}{n}}{n+1}
]
很容易就得到上式等于
[frac{n(n+1)}{2(2n-1)}.
]
Code
double n;
int main()
{
scanf("%lf",&n);
printf("%.12lf
",n*(n+1)/(2*(2*n-1)));
}