卡特兰数相关问题
卡特兰数：规定C0＝1，而C1＝1，C2＝2，C3＝5，C4＝14，C5＝42，C6＝132，C7＝429，C8＝1430，C9＝4862，C10＝16796，C11＝58786，C12＝208012，C13＝742900，C14＝2674440，C15＝9694845
公式为Cn=C(2n, n)/(n+1)=C(2n, n)-C(2n, n-1)
| n | 推导过程 | C(n) |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 1 1 | 2 |
| 3 | 1 2 2 | 5 |
| 4 | 1 3 5 5 | 14 |
| 5 | 1 4 9 14 14 | 42 |
| 6 | 1 5 14 28 42 42 | 132 |
| 7 | 1 6 20 48 90 132 132 | 429 |
| .. | …… | … |
1. 买票找零问题（编程之美4.3）
总数是2n，解是Cn。其中给出了一种容易理解的分析。将两种面值看作左括号和右括号。两个必须成对出现，因此第0个是左括号，并且与其对应的右括号之间括号个数是偶数2i。之后剩余的括号个数是2n-2i-2，0<=i<=n-1。递推求解，得到即为卡特兰数。
2. 出栈次序问题。一个栈(无穷大)的进栈序列为1,2,3,..n,有多少个不同的出栈序列?
解是Cn。
3. 12个高矮不同的人,排成两排,每排必须是从矮到高排列,而且第二排比对应的第一排的人高,问排列方式有多少种?
解是C6。这个问题从另一个角度来看，就是1-12分别放到第一排和第二排。第一排用左括号表示，第二排用右括号表示。这样就转换成了出栈次序问题。
更多问题http://blog.csdn.net/wuyuegb2312/article/details/9339529#suggestion
