Description

求 \(n \le 10^9\) 个节点的二叉树的叶子节点数期望。

Solution

设 \(f_i\) 表示 \(i\) 阶二叉树本质不同个数，\(g_i\) 表示所有本质不同 \(i\) 阶二叉树的树叶个数的和，则有

\[f_i = \sum_{j=0}^{i-1} f_jf_{i-j-1}, \quad g_i=2\sum_{j=0}^{i-1} f_j g_{i-j-1} \]

显然 \(f_i\) 是卡特兰数数列，有

\[f_n=\frac {C_{2n}^n} {n+1} =\frac {4n-2} {n+1} f_{n-1} \]

然而 \(g_i\) 不好处理，下面我们证明 \(g_n=nf_{n-1}\)。

对于 \(n\) 阶二叉树，设有 \(k\) 个叶子，分别删去得到 \(k\) 棵 \(n-1\) 阶二叉树。而每个 \(n-1\) 阶二叉树有 \(n\) 个位置可以悬挂新的叶子，这种添加方式唯一对应了一种删除操作，而删除操作的总数就是所有叶子的个数总和。因此，叶子个数的总和为 \(nf_{n-1}\)。

于是有

\[\frac {g_n} {f_n} = \frac {nf_{n-1}} {f_n} =\frac {n(n+1)}{4n-2} \]

#include <bits/stdc++.h>
using namespace std;

signed main()
{
    double n;
    cin>>n;
    printf("%.10lf",n*(n+1)/(4*n-2));
}