提前一个月退役啦，为什么快乐的时光总是那么短暂啊
众所周知$n$个点的二叉树数量是卡特兰数$c(n)$。
令$G(x)$为其生成函数，其封闭形式为$\dfrac{1-\sqrt{1-4x}}{2x}$。怎么得到的可以看我的生成函数笔记。
设$f(n)$为$n$个节点二叉树的叶子总数。枚举根的左子树大小转移：$f(0)=0,f(1)=1,f(n)=\sum\limits_{i=0}^{n-1}f(i)c(n-1-i)+f(n-1-i)c(i)$
令$F(x)$为$\{f(n)\}$的生成函数。
$F=\sum\limits_{n=1}^\infty f(n)x^n$
$=\sum\limits_{n=1}^\infty x^n\left([n=1]+\sum\limits_{i=0}^{n-1}f(i)c(n-1-i)+f(n-1-i)c(i)\right)$
$=x+2xF\times G$
解出来$F=\dfrac{x}{1-2xG}=\dfrac{x}{\sqrt{1-4x}}$。
之后的操作就有点仙了，不知道谁想到的对$xG(x)$求导：
$(xG(x))’=\dfrac{1}{\sqrt{1-4x}}=\dfrac{F(x)}{x}$
另一方面：
$(xG(x))’=\left(\sum\limits_{n=1}^\infty c(n-1)x^n\right)’=\sum\limits_{n=0}^\infty (n+1)c(n)x^n$
$\dfrac{F(x)}{x}=\sum\limits_{n=0}^\infty f(n+1)x^n$
于是$f(n+1)=(n+1)c(n)$。
答案为$\dfrac{f(n)}{c(n)}$，代入上式和卡特兰数通项公式，化简得到$\dfrac{n(n+1)}{2(2n-1)}$。
代码：
puts("这么简单的代码还有什么展示的必要吗");
