卡特兰数（出现于各种计数问题中的数列）-趣爱秀

基本简介

卡特兰数又称卡塔兰数，英文名Catalan number，是组合数学中一个常出现在各种计数问题中出现的数列。以比利时的数学家欧仁·查理·卡塔兰 (1814–1894)的名字来命名，其前几项为（从第零项开始） : 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, ...

卡特兰数

满足以下递推关系：

历史沿革

1730年我国清朝时期的明安图（蒙古人）比Catalan更早使用了Catalan数，在发现三角函数幂级数的过程中，见《割圜密率捷法》。后来他的学生在1774年将其完成发表。
1753欧拉在解决凸包划分成三角形问题的时候，推出了Catalan数。
1758年，Johann Segner 给出了欧拉问题的递推关系；
1838年，研究热潮：
- GabrielLame给出完整证明和简洁表达式；
- EugèneCharlesCatalan在研究汉诺塔时探讨了相关问题,解决了括号表达式的问题。
- 1900年，EugenNetto在著作中将该数归功于Catalan。
内蒙古师范大学教授罗见今1988年以及1999年的文献研究表明实际上最初发现Catalan数的也不是Euler，而是明安图。

最后由比利时的数学家欧仁·查理·卡塔兰(1814–1894)命名。在中国却应当由清代蒙古族数学家明安图(1692-1763)命名。

python应用

class Solution:

def numTrees(self,n):

#初始化一个数组，并将首个元素初始化为1

s=[0]*(n+1)

s[0]=1

#开始循环遍历

for i in range(1,n+1):

#为节约内存，首先算出i-1的值

b=i-1

#为节约内存，只遍历一半，并将这个结果乘以2即可

for j in range(i//2):

s[i]+=s[j]*s[b-j]

s[i]*=2

#当i为奇数时，还要将s[i//2]的值加上

if i%2==1:

s[i]+=s[i//2]**2

#返回数组最后一个元素

return s[-1]

基本原理

令

，catalan数满足递推式^{[1]：
例如：
另类递推式：
;递推关系的解为：
递推关系的另类解为：
应用介绍
实质上都是递推等式的应用
括号化
矩阵连乘：
，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方案？(
种)^{[2]出栈次序
卡特兰数
一个栈(无穷大)的进栈序列为1，2，3，…，n，有多少个不同的出栈序列?常规分析
首先，我们设
序列个数为n的出栈序列种数。（我们假定，最后出栈的元素为k，显然，k取不同值时的情况是相互独立的，也就是求出每种k最后出栈的情况数后可用加法原则，由于k最后出栈，因此，在k入栈之前，比k小的值均出栈，此处情况有
种，而之后比k大的值入栈，且都在k之前出栈，因此有
种方式，由于比k小和比k大的值入栈出栈情况是相互独立的，此处可用乘法原则，
种，求和便是Catalan递归式。ps.author.陶百百）首次出空之前第一个出栈的序数k将1~n的序列分成两个序列，其中一个是
，序列个数为
，另外一个是
，序列个数是
。此时，我们若把k视为确定一个序数，那么根据乘法原理，f（n）的问题就等价于——序列个数为k-1的出栈序列种数乘以序列个数为
的出栈序列种数，即选择k这个序数的
。而k可以选1到n，所以再根据加法原理，将k取不同值的序列种数相加，得到的总序列种数为：
。看到此处，再看看卡特兰数的递推式，答案不言而喻，即为
。最后，令
。非常规分析
对于每一个数来说，必须进栈一次、出栈一次。我们把进栈设为状态‘1’，出栈设为状态‘0’。n个数的所有状态对应n个1和n个0组成的2n位二进制数。由于等待入栈的操作数按照1‥n的顺序排列、入栈的操作数b大于等于出栈的操作数a(
)，因此输出序列的总数目=由左而右扫描由n个1和n个0组成的2n位二进制数，1的累计数不小于0的累计数的方案种数。在2n位二进制数中填入n个1的方案数为
,不填1的其余n位自动填0。从中减去不符合要求（由左而右扫描，0的累计数大于1的累计数）的方案数即为所求。不符合要求的数的特征是由左而右扫描时，必然在某一奇数位
位上首先出现
个0的累计数和m个1的累计数，此后的
位上有
个 1和
个0。如若把后面这
位上的0和1互换，使之成为
个0和
个1，结果得1个由
个0和
个1组成的2n位数，即一个不合要求的数对应于一个由
个0和
个1组成的排列。反过来，任何一个由
个0和
个1组成的2n位二进制数，由于0的个数多2个，2n为偶数，故必在某一个奇数位上出现0的累计数超过1的累计数。同样在后面部分0和1互换，使之成为由n个0和n个1组成的2n位数，即
个0和
个1组成的2n位数必对应一个不符合要求的数。因而不合要求的2n位数与
个0，
个1组成的排列一一对应。显然，不符合要求的方案数为
。由此得出输出序列的总数目
。类似问题买票找零
有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票，另外n人只有10元钞票，剧院无其它钞票，问有多少种方法使得只要有10元的人买票，售票处就有5元的钞票找零？(将持5元者到达视作将5元入栈，持10元者到达视作使栈中某5元出栈)
凸多边形三角划分
在一个凸多边形中，通过若干条互不相交的对角线，把这个多边形划分成了若干个三角形。任务是键盘上输入凸多边形的边数n，求不同划分的方案数f（n）。比如当
时，
。卡特兰数
分析如果纯粹从
慢慢去归纳，恐怕很难找到问题的递推式，我们必须从一般情况出发去找规律。因为凸多边形的任意一条边必定属于某一个三角形，所以我们以某一条边为基准，以这条边的两个顶点为起点
和终点
（P即Point），将该凸多边形的顶点依序标记为
，再在该凸多边形中找任意一个不属于这两个点的顶点
，来构成一个三角形，用这个三角形把一个凸多边形划分成两个凸多边形，其中一个凸多边形，是由
构成的凸k边形（顶点数即是边数），另一个凸多边形，是由
构成的凸
边形。此时，我们若把Pk视为确定一点，那么根据乘法原理，f（n）的问题就等价于——凸k多边形的划分方案数乘以凸
多边形的划分方案数，即选择
这个顶点的
。而k可以选2到
，所以再根据加法原理，将k取不同值的划分方案相加，得到的总方案数为：
。看到此处，再看看卡特兰数的递推式，答案不言而喻，即为
。最后，令
。此处
和
的具体缘由须参考详尽的“卡特兰数”，也许可从凸四边形
倒推，四边形的划分方案不用规律推导都可以知道是2，那么
，则
，又
和
若存在的话一定是整数，则
，
。（因为我没研究过卡特兰数的由来，此处仅作刘抟羽的臆测）。类似问题
一位大城市的律师在她住所以北n个街区和以东n个街区处工作。每天她走2n个街区去上班。如果她从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？
在圆上选择2n个点，将这些点成对连接起来使得所得到的n条线段不相交的方法数？
给定节点组成二叉搜索树
给定N个节点，能构成多少种不同的二叉搜索树？
（能构成
个）（这个公式的下标是从
开始的）n对括号正确匹配数目
给定n对括号，求括号正确配对的字符串数，例如：
0对括号：[空序列] 1种可能
1对括号：() 1种可能
2对括号：()() (()) 2种可能
3对括号：((())) ()(()) ()()() (())() (()()) 5种可能
那么问题来了，n对括号有多少种正确配对的可能呢？
考虑n对括号时的任意一种配对方案，最后一个右括号有唯一的与之匹配的左括号，于是有唯一的表示A(B)，其中A和B也是合法的括号匹配序列
假设
为n对括号的正确配对数目，那么有递推关系
，显然
是卡特兰数。
扩展介绍
对于在n位的2进制中，有m个0，其余为1的catalan数为：
。证明可以参考标准catalan数的证明。^{[1]问题1的描述：有n个1和m个-1（
），共n+m个数排成一列，满足对所有
的前k个数的部分和
的排列数。问题等价为在一个格点阵列中，从（0，0）点走到（n，m）点且不经过对角线
的方法数（
）。考虑情况I：第一步走到（0，1），这样从（0，1）走到（n，m）无论如何也要经过
的点，这样的方法数为
;考虑情况II：第一步走到（1，0），又有两种可能：
a . 不经过
的点；（所要求的情况）b . 经过
的点，我们构造情况II.b和情况I的一一映射，说明II.b和I的方法数是一样的。设第一次经过
的点是（
），将（0，0）到（
）的路径沿对角线翻折，于是唯一对应情况I的一种路径；对于情况I的一条路径，假设其与对角线的第一个焦点是（
），将（0，0）和（
）之间的路径沿对角线翻折，唯一对应情况II.b的一条路径。问题的解就是总的路径数
- 情况I的路径数 - 情况II.b的路径数。
或：
问题2的描述：有n个1和m个-1（
），共
个数排成一列，满足对所有
的前k个数的部分和
的排列数。（和问题1不同之处在于此处部分和可以为0，这也是更常见的情况）问题等价为在一个格点阵列中，从（0，0）点走到（n，m）点且不穿过对角线
的方法数（可以走到
的点）。把（n，m）点变换到（
）点，问题变成了问题1。方法数为：
或：
Java的应用
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70 import java.util.*;

import java.math.BigInteger;

public class Catalan {  //求卡特兰数

    public static void main(String[] args){

    int numberOfCatalan = 101; //要求多少个卡特兰数

    BigInteger[] digis = new BigInteger[numberOfCatalan];

    digis = generateCatalan(numberOfCatalan);


    Scanner scanner = new Scanner(System.in);


    int number;

    while(true) {
        number = scanner.nextInt();
        if(number == -1) {
            break;
            String answer = digis[number].toString();
            System.out.println(answer);
            }
        }
    }


static BigInteger[] generateCatalan(int numberOfCatalan) {
   //产生卡特兰数
    BigInteger digis[] = new BigInteger[numberOfCatalan + 1];

    BigInteger x = new BigInteger("1"); //第一个卡特兰数为1

    digis[1] = x;

    int y = 0;

    int z = 0;


        for(int counter = 2; counter <= numberOfCatalan; ++ counter) {

            y = 4 * counter - 2;

            z = counter + 1;

            digis[counter] = digis[counter-1].multiply(new BigInteger("" + y));
            digis[counter] = digis[counter].divide(new BigInteger("" + z));
        }
        return digis;
    }
}
//使用递归的方式解决卡特兰数
public static double CatalanNumber(int n) {
    if (n == 1) {
        return 1;
    } else {
        return CatalanNumber(n - 1) * 2 * (2 * n - 1) / (n + 1);
    }
}
public static void main(String[] args) {
    for (int i = 1; i <= 50; i++) {
        System.out.println(i + "'s Catalan Number is " + CatalanNumber(i));
    }
}
C++的应用
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33 void catalan() //求卡特兰数
{
    int i, j, len, carry, temp;
    a[1][0] = b[1] = 1;
    len = 1;
    for(i = 2; i <= 100; i++)
    {
        for(j = 0; j < len; j++) //乘法
        a[i][j] = a[i-1][j]*(4*(i-1)+2);
        carry = 0;
        for(j = 0; j < len; j++) //处理相乘结果
        {
            temp = a[i][j] + carry;
            a[i][j] = temp % 10;
            carry = temp / 10;
        }
        while(carry) //进位处理
        {
            a[i][len++] = carry % 10;
            carry /= 10;
        }
        carry = 0;
        for(j = len-1; j >= 0; j--) //除法
        {
            temp = carry*10 + a[i][j];
            a[i][j] = temp/(i+1);
            carry = temp%(i+1);
        }
        while(!a[i][len-1]) //高位零处理
        len --;
        b[i] = len;
    }
}
参考资料
[1] 卡特兰数 · CSDN博客-幽兰止水[引用日期2012-06-16]
[2] 2012腾讯实习笔试中看到的Catalan数 · CSDN博客[引用日期2012-06-16]}}}