卡特兰数（Catalan）公式、证明、代码、典例
⼤佬博客：
组合数公式：
⼀、关于卡特兰数
卡特兰数是⼀种经典的组合数，经常出现在各种计算中，其前⼏项为 : 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, ...
⼆、卡特兰数的⼀般公式
卡特兰数满⾜以下性质：
令h(0)=1,h(1)=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)-c(2n,n+1)(n=0,1,2,...)。这个公式还可以更简单得化为h(n)=C(2n,n)/(n+1)。后⼀个公式都可以通过前⼀个公式经过⼏步简单的演算得来，⼤家可以拿起笔试试，⼀两分钟就可以搞定。
1. 出栈次序
2. 01序列
3. ‘+1’ ‘-1’序列
4. 括号序列
5. 零问题
6. 矩阵链乘
7. ⼆叉树计数
8. 凸多边形划分
9. 圆上n条线段
10. 单调路径
11. 填充阶梯图形
12. 摞碗问题
13. 汽车胡同加油问题
14. 还书借书问题
15. ⾼矮排队问题
典例：
1. 出栈次序
⼀个栈(⽆穷⼤)的进栈序列为1，2，3，…，n，有多少个不同的出栈序列?
2. 01序列
给出⼀个n，要求⼀个长度为2n的01序列，使得序列的任意前缀中1的个数不少于0的个数，有多少个不同的01序列?
以下为长度为6的序列:
111000 101100 101010 110010 110100
3. ‘+1’ ‘-1’序列
n个+1和n个-1构成的2n项 a1,a2,⋅⋅⋅,a2na1,a2,⋅⋅⋅,a2n，其部分和满⾜⾮负性质，即a1+a2+⋅⋅⋅+ak>=0a1+a2+⋅⋅⋅+ak>=0，(k=1,2,···,2n) ，有多少个不同的此序列?
4. 括号序列
n对括号有多少种匹配⽅式？
5. 零问题
2n个⼈要买票价为五元的电影票，每⼈只买⼀张，但是售票员没有钱零。其中，n个⼈持有五元，另
外n个⼈持有⼗元，问在不发⽣零困难的情况下，有多少种排队⽅法？
6. 矩阵链乘
P=a1×a2×a3×……×an，依据乘法结合律，不改变其顺序，只⽤括号表⽰成对的乘积，试问有⼏种括号化的⽅案？
7. ⼆叉树计数
有n个节点构成的⼆叉树（⾮叶⼦节点都有2个⼉⼦），共有多少种情形？
有n+1个叶⼦的⼆叉树的个数？、
8. 凸多边形划分
在⼀个n边形中，通过不相交于n边形内部的对⾓线，把n边形拆分为若⼲个三⾓形，问有多少种拆分⽅案？
9. 圆上n条线段
在圆上选择2n个点，将这些点成对连接起来使得所得到的n条线段不相交的⽅法数？
10. 单调路径
⼀位⼤城市的律师在他住所以北n个街区和以东n个街区处⼯作，每天他⾛2n个街区去上班。如果他从不穿越（但可以碰到）从家到办公室的对⾓线，那么有多少条可能的道路？
11. 填充阶梯图形
⽤n个长⽅形填充⼀个⾼度为n的阶梯状图形的⽅法个数？
12. 摞碗问题
饭后，洗碗，妹妹把洗过的碗⼀个⼀个放进碗橱摞成⼀摞。⼀共有n个不同的碗，洗前也是摞成⼀摞的，也许因为⼩妹贪玩⽽使碗拿进碗橱不及时，则把洗过的碗摞在旁边，问：⼩妹摞起的碗有多少种可能的⽅式？
13. 汽车胡同加油问题
⼀个汽车队在狭窄的路⾯上⾏驶，不得超车，但可以进⼊⼀个死胡同去加油，然后再插队⾏驶，共有n辆汽车，问共有多少种不同的⽅式使得车队开出城去？
14. 还书借书问题
在图书馆⼀共2n个⼈在排队，n个还《⾯试宝典》⼀书，n个在借《⾯试宝典》⼀书，图书馆此时没有了⾯试宝典了，求他们排队的总数
二叉树公式
15. ⾼矮排队问题
2n个⾼矮不同的⼈，排成两排，每排必须是从矮到⾼排列,⽽且第⼆排⽐对应的第⼀排的⼈⾼，问排列⽅式有多少种?