卡特兰数

数列特征为：1, 1, 2, 5, 14, 42, 132, 429，…

#用python实现是为了防止计算溢出，因为catalan实在是递增太猛了，calanta(20) 就能使得int溢出
def catalan(int n):
    if n==0 or n==1:
        return 1
    return (4*n-2)*catalan(n-1)/(n+1)

应用场景：

由n个+1和n个-1构成2n项其部分和满足的序列个数等于第n个Catalan数

左括号和右括号各有n个时，合法括号表达式的个数

对于n+1个数连乘，乘法顺序有种

n个节点构造二叉树的所有可能形态数为

n个非叶节点的满二叉树的形态数（对称后得到的二叉树除非自己本身对称，否则算是不同）

对于一个n*n的正方形网格，每次只能向右或者向上移动一格，那么从左下角到右上角所有在副对角线右下方的路径总数为

可以将一条水平边记为+1,垂直边记为-1,那么就组成了一个n个+1和n个-1的序列，并且保证前k步中水平边数不小于垂直边数，换句话说前k个元素的和非负

对凸n+2边形进行不同的三角形分割（只连接顶点对形成n个三角形）数为Cn

也可以换一种说法： 平面上连接可以形成凸包的2n个点分成2个一组连成n条线段，两两线段之间不相交的情况总数是

n个数入栈后的出栈的排列总数是

对于集合，将集合元素两两分为n个子集，若任意两个子集都不交叉，那么我们称此划分为一个不交叉划分。此时不交叉的划分数就是

n层的阶梯切割为n个矩形的切法数也是。如下图所示：

在一个2*n的格子中填入1到2n这些数值使得每个格子内的数值都比其右边和上边的所有数值都小的情况数也是。

n+m个人排队买票，并且满足，票价为50元，其中n个人各手持一张50元钞票，m个人各手持一张100元钞票，初始时候售票窗口没有钱，问有多少种排队的情况数能够让大家都买到票。 如果m=n的话那么这就是初始的Catalan数问题，也就是将手持50元的人看成是+1，手持100元的人看成是-1，任前k个数值的和都非负的序列数。

其他著名的数列有：
Fibonacci ：0, 1, 1, 2, 3, 5, 8, 13, 21,…
碰到有些组合问题，求有多少种组合方式的，在看不出规律时，不妨从简单的开始，数学归纳法举例，或许可以发现这是一个特殊的数列呢。
比如
如果不举例归纳，就不会发现这是一个Fibonacci 数列了，竟如此简单。