本文使用 Zhihu On VSCode 创作并发布
卡特兰数经常会在算法题中出现，是组合数学中的一个特别重要的数.
\begin{aligned}h(n)&=\sum\limits_{i=0}^{n-1}h(i)\cdot h(n-i-1)\\&=h(0)\cdot h(n-1)+h(1)\cdot h(n-2)+\cdots+h(n-1)\cdot h(0).\end{aligned}\\
则Catalan 数的解为h(n)=\frac{1}{n+1}C_{2n}^n .
令H(x)=h(0)+h(1)x+h(2)x^2+\cdots+h(n)x^n+\cdots ，则递归公式左边就是H(x) 的n 次项系数，右边是H^2(x) 的n-1 次项系数，所以我们有
H(x)=xH^2(x)+h(0)=xH^2(x)+1.
解得H(x)=\frac{1\pm\sqrt{1-4x}}{2x} .
在上一篇文章中，由广义牛顿二项式定理得\sqrt{1-4x}=\sum\limits_{n=0}^{\infty}-\frac{1}{2n-1}C_{2n}^nx^n.
取H(x)=\frac{1-\sqrt{1-4x}}{2x} ，则x^n 系数为\frac{1}{2}\frac{1}{2n+1}C_{2n+2}^{n+1}=\frac{1}{n+1}C_{2n}^n .
这样就得到Catalan 数h(n)=\frac{1}{n+1}C_{2n}^n .
在邓俊辉【C++数据结构】「二叉搜索树」一节中，由一组共n 个互异节点组成的二叉搜索树，总共有\frac{1}{n+1}C_{2n}^n=\frac{(2n)!}{n!(n+1)!} 棵.
