Catalan 数

Catalan数:

$h(1)=1,h(0)=1$

$h(n)=\begin{cases} \sum_{i=0}^{n-1} h(i) \times h(n-i-1) & \text{if }(n>=2) \\\\ \frac{C(2n,n)}{n+1} & \text{if }(n=1,2,3,\mathellipsis) \end{cases}$

相关结论： n边形能分解成三角形的分法数为 h(n – 2) n个节点能组成的二叉树个数为 h(n) 一个栈(无穷大)的进栈序列为1，2，3，…，n，出栈序列种数为 h(n)

参考（转载）： http://zh.wikipedia.org/wiki/卡特兰数 http://baike.baidu.com/view/4076365.htm