数论——特殊数列_卡特兰数

卡特兰数：
一：基本逻辑：Catalan数主要是用于组合数学中，有两种操作，而且这两种操作的操作数量相同，N个操作一前要有N-1次操作二。其实Catalan数就是个具有一定几何意义的数列。
二：递推式：

令h(0)=1,h(1)=1，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) C(2n,n)指的是组合数学
h(n)=C(2n,n)-C(2n,n-1)

三：卡特兰数中的前几项：(当n>35的时候，数据就越界了，需要配合高精度)
1, 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。

四：常见的题目类型;
1:括号匹配问题（他的解是第n个卡特兰数）
Cn表示长度2n的字符串str的个数。字符串str是一个有n个X和n个Y组成的字串，且所有的部分字串皆满足X的个数大于等于Y的个数。以下为长度为6的str:
XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY
将上例的X换成左括号，Y换成右括号，Cn表示所有包含n组括号的合法运算式的个数:
((())) ()(()) ()()() (())() (()())

2.栈的入栈出栈问题（他的解是第n个卡特兰数）
1）. 一个栈(无穷大)的进栈序列为1, 2 , 3 ,..n,有多少个不同的出栈序列 ?
2）. 有2n个人排成一行进入剧场。入场费1元。其中只有n个人有一张1元钞票，另外n人只有2元钞票，剧院无其它钞票，问有多少中方法使得只要有2元的人买票，售票处就有1元的钞票找零？(将持1元者到达视作将1元入栈，持10元者到达视作使栈中某1元出栈)
3）. 在圆上选择2n个点,将这些点成对连接起来，使得所得到的n条线段不相交的方法数。

3矩阵链乘问题（他的解是第n-1个卡特兰数）
P=a1×a2×a3×……×an，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方案？

4二叉树计数问题（他的解是第n个卡特兰数）
有n个节点构成的二叉树（非叶子节点都有2个儿子），共有多少种情形？
有n+1个叶子的二叉树的个数？

5 凸多边形划分 （他的解是第n-2个卡特兰数）
在一个n边形中，通过不相交于n边形内部的对角线，把n边形拆分为若干个三角形，问有多少种拆分方案？

6单调路径 （他的解是第n个卡特兰数）
一位大城市的律师在他住所以北n个街区和以东n个街区处工作，每天他走2n个街区去上班。如果他从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？

7填充阶梯图形（他的解是第n个卡特兰数）
用n个长方形填充一个高度为n的阶梯状图形的方法个数？

五：代码实现

//函数功能: 计算Catalan的第n项
//函数参数: n为项数
//返回值:  第n个Catalan数
int Catalan(int n)
{
    if(n<=1) return 1;
    int *h = new int [n+1]; //保存临时结果
    h[0] = h[1] = 1;        //h(0)和h(1)
    for(int i=2;i<=n;++i)    //依次计算h(2),h(3)...h(n)
    {
        h[i] = 0;
        for(int j = 0; j < i; j++) //根据递归式计算 h(i)= h(0)*h(i-1)+h(1)*h(i-2) + ... + h(i-1)h(0)
            h[i] += (h[j] * h[i-1-j]);
    }
    int result = h[n]; //保存结果
    delete [] h;       //注意释放空间
    return result;
}

参考博客
卡特兰数（Catalan）公式、证明、代码、典例.
卡特兰数 Catalan数 ( ACM 数论组合 )
数论之Catalan（卡特兰数）