序言

由于卡特兰数在很多公司的面试题中频繁出现，在竞赛中更是多次考察，所以特地总结下卡特兰数的应用。

定义

卡特兰数又称卡塔兰数，是组合数学中一个常出现在各种计数问题中的数列。以比利时的数学家欧仁·查理·卡塔兰 (1814–1894)的名字来命名。

原理

令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)=h(n-1)(4n-2)/(n+1);
递推关系的解为：
h(n)=C(2n,n)/(n+1)=(2n)!/(n+1)!n! (n=0,1,2,…)　　　　　C(2n，n)代表从2n个数中取得n个数的组合数
递推关系的另类解为：
h(n)=C(2n,n)-C(2n,n-1)(n=0,1,2,…)

应用

求卡特兰数

题目要求
根据递推式或递归关系求解

解法
任何有关catalan数的题目最后都是要进行求h(n)的运算，大多用h(n)=h(n-1)(4n-2)/(n+1)进行推导。牵涉到大数的乘除。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

//数组a存放大数，b为进行乘除的数字。
void multiply(int a[],int len,int b)
{  
    for(int i=len-1,carry=0;i>=0;--i)
    {
        carry+=b*a[i];  
        a[i]=carry%BASE;  
        carry/=BASE;  
    }   
}  
void divide(int a[],int len,int b) 
{
    for(int i=0,div=0;i<len;++i)
    {  
        div=div*BASE+a[i];  
        a[i]=div/b;
        div%=b;  
    }  
}
//具体运算在ACM-HDOJ 1023题已给出

出栈问题

题目要求
一个栈(无穷大)的进栈序列为1、2、3、…、n，有多少个不同的出栈序列?

解法
此方法在ACM-HDOJ 1023题思路中已给出证明。1023链接

由高到矮排队问题

题目要求
12个高矮不同的人，排成两排，每排必须是从矮到高排列，而且第二排比对应的第一排的人高，问排列方式有多少种？

解法
我们先把这12个人从低到高排列,然后,选择6个人排在第一排,那么剩下的6个肯定是在第二排.
用0表示对应的人在第一排,用1表示对应的人在第二排,那么含有6个0,6个1的序列,就对应一种方案.
比如000000111111就对应着
第一排：0 1 2 3 4 5
第二排：6 7 8 9 10 11
010101010101就对应着
第一排：0 2 4 6 8 10
第二排：1 3 5 7 9 11
问题转换为，这样的满足条件的01序列有多少个。
观察规律我们发现1的出现前边必须有一个相应的0对应，所以从左到右的所有序列中0的个数要一直大于1的个数。那么我们从左往右扫描，第一次出现1的个数
等于0的个数是第k位，那么在此之前，0的个数是大于1的个数的。在此之后，0的个数也是大于1的个数的。所以第k位0和1的个数第一次相等的排列有他们这两
部分的个数相乘的结果。那么所有的k有多少种，则把它们相加起来，就是最后的排列数。每一项的种类是f（k-1）*f（n-k），求和后便是卡特兰数。
如果把0看成入栈操作，1看成出栈操作，等价于给定6个元素，合法的入栈出栈序列有多少个。依旧转换成求卡特兰数的问题。
需要注意此题中n个人，那么带入通项的数字应为n/2。

括号化问题

题目要求
矩阵链乘： P=A1×A2×A3×……×An，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方案？

解法
n个矩阵需要连乘(n-1)次，因此需要(n-1)对括号。且这里的括号只是为了使矩阵两两结合，而不是单纯为加括号而加括号，像( (a1) (a2))，这里将两个矩
阵分别括起来是不符合要求的。因此这里如果确定了括号的顺序，那么矩阵的结合顺序也会确定，如(()())对应了(( a1 a2) (a3 a4))。注意到是(n-1)
对括号，即(n-1)个左括号和(n-1)个右括号，那么应该使用h[n-1]来计算。

买票找零问题

题目要求
2n个人排队买票，其中n个人持50元，n个人持100元。每张票50元，且一人只买一张票。初始时售票处没有零钱找零。请问这2n个人一共有多少种排队顺序，不至
于使售票处找不开钱？

解法
队伍的序号标为0,1,…,2n-1,并把50元看作左括号，100元看作右括号，合法序列即括号能完成配对的序列。对于一个合法的序列，第0个一定是左括号，它必然与
某个右括号配对，记其位置为k。那么从1到k-1、k+1到2n-1也分别是两个合法序列。每一项的种类是f（k-1）*f（n-k），求和后便是卡特兰数。也需注意此题中n
个人，带入通项的数字应为n/2。

凸多边形三角划分

题目要求

解法
使用卡特兰数通项进行计算。

圆上点对互连问题

题目要求

解法
将圆上的点依次标为P0,P1,…P2n-1。为了避免混淆，使用F(2n)表示2n个点可连成的线段数，选择Pk与P0相连(0<k<n)，同样地可以看出，k必为奇数，否则1至k-1
之间有奇数个点，不可能成对连成直线。同样地把k设为2i+1，那么线段P0Pk把剩余的点分为了1…2i和2i+2…2n-1，且新的连线不能与0k相交，它们只能属于0k
把园划分出的这两个区域之一。即F(2n) = ∑F(2i)F(2n-1-(2i+2)+1) = ∑F(2i)F(2n-2i-2)，其中i = 0 … n-1。这时，又转化成熟悉的形式了。

给定节点组成二叉搜索树

题目要求

解法
从递推公式出发，记为F3(n)，选出一点为根，k个点作为左子树，n-k-1个点作为右子树。那么F3(n) = ∑F3(k)F3(n-k-1)，k=0,…,n-1。该公式是以F3（0）=1开始的。
满足卡特兰数的形式。

街区对角线问题

题目要求

解法
为了不跨越对角线，向东走的步数时刻要大于等于向北走的步数。可以看出路线序列由n次向东和n次向北组成，且从第一个元素开始的任意子序列中向东次数不少于向北次数此
时可以等效为按高矮排队问题。用卡特兰数递推式求解。注意为h(n)。

n层阶梯切割问题

题目要求

解法
使用卡特兰数通项进行计算。

01串问题

题目要求
要求长度为2*n的字符串中只由0和1组成 且0和1的个数相等 且对应任意一个前缀1的个数不小于0的个数
求有多少种组合方法

解法
答案为h(n)的卡特兰数