题目大意：对于一棵随机生成的$n$个结点的有根二叉树，所有不同构的形态等概率出现（这里同构当且仅当两棵二叉树根相同，并且相同节点的左儿子和右儿子都相同），求叶子节点个数的期望是多少？

题解：令$f_n$表示$n$个节点的二叉树的个数，$g_n$表示这$f_n$棵二叉树的叶子节点个数和。

打(ti)表(jie)发现：$g_n=n f_{n-1}$

证明：而每棵$n-1$个点的二叉树恰好有$n$个位置可以悬挂一个新的叶子，所以每棵$n-1$个点的二叉树被扩展了$n$次。发现会算重复，但是对于一个有$k$个叶子节点的二叉树，就会被重算$k+1$次，刚好就是叶子节点的个数，所以$g_n=n f_{n-1}$

$$

\dfrac{g_n}{f_n}=\dfrac{nf_{n-1}}{f_n}\\

\begin{align*}

f_n&=\sum\limits_{i=0}^{n-1}f_if_{n-i-1}\\

&=\dfrac{\binom{2n}n}{n+1}\\

&（即卡特兰数）\\

\end{align*}\\

g_n=\dfrac{n(n+1)}{2(2n-1)}

$$

更正常的生成函数证明

卡点：未开$long\;long$

 

C++ Code：

#include 
     
      long long n;int main(){    scanf("%lld", &n);    printf("%.10lf\n", n * (n + 1) / 2.0 / (2.0 * n - 1.0));    return 0;}