令h(1)＝1,h(0)=1，catalan数满足递归式：
h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)h(0) (其中n>=2)
该递推关系的解为：
h(n)=C(2n,n)/(n+1) (n=1,2,3,...)
卡特兰数的应用
1. 火车出栈的序列总数问题
2. P=a1×a2×a3×……×an，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方案
3. 有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票，另外n人只有10元钞票，剧院无其它钞票，问有多少种方法使得只要有10元的人买票，售票处就有5元的钞票找零？
4. 一个凸多边形区域分成三角形区域的方法数
5. 给定N个节点，能构成多少种不同的二叉树？