Description：

对于一棵随机生成的 $n$ 个结点的有根二叉树求它的叶子节点数的期望。

$1\leqslant n\leqslant 10^9$

Solution：

首先设 $g(i)$ 表示有 $n$ 个节点的二叉树的个数， $f(i)$ 表示有 $n$ 个节点的所有二叉树的叶子节点个数和，显然有： $$ \begin{align} g_i&=\sum_{k=0}^{i-1}g_k\times g_{i-1-k}+[i=1]\\ f_i&=\sum_{k=0}^{i-1}(f_k\times g_{i-1-k}+f_{i-1-k}\times g_k)+[i=1]=2\sum_{k=0}^{i-1}f_k\times g_{i-1-k}+[i=1] \end{align} $$ 即： $$ G(x)=xG(x)^2+x,F(x)=2xF(x)G(x)+x $$ 我们已经知道： $$ G(x)=\frac{1-\sqrt{1-4x}}{2x} $$ 因此： $$ F(x)=x(\sqrt{1-4x})^{-\frac 1 2} $$ 然后我们发现： $$ \begin{align} xG(x)&=\frac{1-\sqrt{1-4x}}2\\ \Rightarrow(xG(x))'&=-\frac12(\sqrt{1-4x})'\\ &=-\frac14(1-4x)^{-\frac12}\times (1-4x)'\\ &=-\frac14(1-4x)^{-\frac12}\times (-4)\\ &=(1-4x)^{-\frac12}\\ &=\frac{F(x)}x \end{align} $$ 即： $$ F(x)=x(xG(x))' $$ 而我们知道 $G$ 第 $i$ 项的值为 $C(i)=\frac{\binom{2i}i}{i+1}$ ，于是可以得到 $F$ 第 $n$ 项的值为 $\frac{n(n+1)}{2(2n-1)}$ 。

Code：

#include<bits/stdc++.h>

using namespace std;

#define MOD 10007

int main()

{

	int n;cin >> n;

	printf("%.12lf\n",1.0 * n * (n + 1) / 2 / (2 * n - 1));

	return 0;

}