传送门

提前一个月退役啦,为什么快乐的时光总是那么短暂啊

众所周知$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("这么简单的代码还有什么展示的必要吗");