[组合数学]卡特兰数
[TOC]
卡特兰数是在复习数据结构时遇到的一个问题。
问题描述
最初的问题是这样：
有n个元素按a1,a2,a3…an的次序依次进栈(容量无穷)，且每个元素只允许进一次栈，则可能的出栈序列有多少种？
这个问题在数量少的情况下可以进行模拟，但是仔细思索这是一个组合数学的问题。
递归写法
首先，我们设
f（n）=序列个数为n的出栈序列种数。（我们假定，最后出栈的元素为k，显然，k取不同值时的情况是相互独立的，也就是求出每种k最后出栈的情况数后可用加法原则，由于k最后出栈，因此，在k入栈之前，比k小的值均出栈，此处情况有f(k-1)种，而之后比k大的值入栈，且都在k之前出栈，因此有f(n-k)种方式，由于比k小和比k大的值入栈出栈情况是相互独立的，此处可用乘法原则，f(n-k)*f(k-1)种，求和便是Catalan递归式。首次出空之前第一个出栈的序数k将1~n的序列分成两个序列，其中一个是1~k-1，序列个数为k-1，另外一个是k+1~n，序列个数是n-k。
此时，我们若把k视为确定一个序数，那么根据乘法原理，f（n）的问题就等价于——序列个数为k-1的出栈序列种数乘以序列个数为n - k的出栈序列种数，即选择k这个序数的f（n）=f（k-1）×f（n-k）。而k可以选1到n，所以再根据加法原理，将k取不同值的序列种数相加，得到的总序列种数为：
f（n）=f（0）f（n-1）+f（1）f（n-2）+……+f（n-1）f（0）。看到此处，再看看卡特兰数的递推式，答案不言而喻(哪里不言而喻了啊，下文给出稍好理解的证明)，即为f（n）=h（n）= C（2n,n）/（n+1）= c（2n,n）-c（2n,n-1）（n=0，1，2，……）。
最后，令f（0）=1，f（1）=1。
递推写法
关于递归式怎么化成递推式的简单证明
问题大意是用S表示入栈，X表示出栈，那么合法的序列有多少个(S的个数为n) 显然有c(2n, n)个含S，X各n个的序列，剩下的是计算不允许的序列数(它包含正确个数的S和X，但是违背其它条件). 在任何不允许的序列中，定出使得X的个数超过S的个数的第一个X的位置。然后在导致并包括这个X的部分序列中（就是自第一个元素其到包含此X的字串），以S代替所有的X并以X代表所有的S。结果是一个有(n+1)个S和(n-1)个X的序列（因为相当于有一个X转成了S，导致S多了一个，X少了一个）。反过来，对于后一种类型的每个序列，我们都能逆转这个过程，而且找出导致它的前一种类型的不允许序列（且此处一定一一对应）。例如
SSXXXSXSSXSX必然来自XXSSSSXSSXSX。这个对应说明，不允许的序列的个数是c(2n, n-1)，即含有(n-1)个X和(n+1)个S的序列的排序数，因此an = c(2n, n) - c(2n, n-1)
适用范围
可用于解决的问题有很多：
- 买票找零
有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票，另外n人只有10元钞票，剧院无其它钞票，问有多少中方法使得只要有10元的人买票，售票处就有5元的钞票找零？(将持5元者到达视作将5元入栈，持10元者到达视作使栈中某5元出栈)
-
一个有n个1和n个-1组成的字串，且前k个数的和均不小于0，那这种字串的总数为多少？
-
饭后，姐姐洗碗，妹妹把姐姐洗过的碗一个一个地放进碗橱摞成一摞。一共有n个不同的碗，洗前也是摞成一摞的，也许因为小妹贪玩而使碗拿进碗橱不及时，姐姐则把洗过的碗摞在旁边，问：小妹摞起的碗有多少种可能的方式？
-
凸多边形三角划分
在一个凸多边形中，通过若干条互不相交的对角线，把这个多边形划分成了若干个三角形。任务是键盘上输入凸多边形的边数n，求不同划分的方案数f（n）。
-
给定节点组成二叉搜索树
给定N个节点，能构成多少种不同的二叉搜索树？
-
n对括号正确匹配数目
给定n对括号，求括号正确配对的字符串数，例如：
0对括号：[空序列] 1种可能
1对括号：() 1种可能
2对括号：()() (()) 2种可能
3对括号：((())) ()(()) ()()() (())() (()()) 5种可能
求n对括号有多少种正确配对的可能
-
对于在n位的2进制中，有m个0，其余为1的catalan数
-
在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数？
-
一位大城市的律师在她住所以北n个街区和以东n个街区处工作。每天她走2n个街区去上班。如果她从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？
