算法提高篇--数学基础（七）：组合数学（2）--卡特兰数
不学不知道，算法真奇妙。又到了将“算法”刻到骨子里的时刻，今天为大家带来的是数学基础的第七讲——组合数学（2）--卡特兰数。
1、卡特兰（Catalan）数
卡特兰（又译卡塔兰）数，英文名Catalan number，又称明安图数，是组合数学中一个常出现于各种计数问题中的数列。以中国蒙古族数学家明安图 (1692-1763)和比利时的数学家欧仁·查理·卡塔兰 (1814–1894)的名字来命名。其前几项为（从第0项开始） : 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, ...
若令C(0)=1,C(1)=1，Catalan数满足递推式：C(n)= C(0)*C(n-1)+C(1)*C(n-2) + ... + C(n-1)C(0) (n>=2)。
例如：C(2) = C(0)*C(1)+C(1)*C(0) = 1*1 +1*1 = 2。
卡特兰数递推式通常也会表示为：Cn = Cn-1*(4n-2)/(n+1)。
2、应用
题型一：进出栈序列（括号序列）模型。
1)、进出栈序列：
我们以一道03年NOIP普及组真题为例，来进一步了解卡特兰数的应用。在一本通对应该题题号为：1924：【03NOIP普及组】栈。
题解：
一个出栈操作，必定会有一个进栈操作与之对应，否则就出了个空气。把进出栈的动作序列化。对于n个整数，其进栈和出栈的次数总和必定是2n次。即n次出栈，对应n次进栈。
把进出动作抽象为符号表示，即进栈动作记为+1，出栈动作记为-1。则213的出栈次序就可以表示为：+1，+1，-1，-1，+1，-1。如下图所示：
聪明的你肯定想到了为什么用+1和-1去抽象进栈和出栈的动作，因为刚好可以利用前缀和的思想来维护当前操作序列的合理性，即对应第i次操作，前缀和sum[i]必定会≥0，否则当前操作序列是不合理的进出栈序列。
接下来，我们按照组合数的思想，很快可以得出所有操作序列（包括合理和不合理的序列），即对应2n个动作，取其中n个动作作为进栈，剩下的就是出栈了，对应的组合数为
。现在问题来了，如何把非法的序列给排除掉呢？
我们分析，对于非法序列：+1 -1 -1 +1 +1 -1，第一次出现前缀和小于0的的项（从第1项开始算起）是第3项开始，将前三项取反后，对应得到的序列为：-1 +1 +1 +1 +1 -1。很容易理解的一点是，取反后的序列肯定是n+1个1对应n-1个-1，且对应取反的序列是唯一的，反过来思考也是一样，因此就把非法序列的排除问题，转化为2n个动作中，取n+1个“+1”的组合数，每一个这样的序列跟非法序列是一一对应的关系。因此，最终的结果是
。
又有：
= (2n)!/(n)!(2n-n)!=(2n)!/(n)!(n)!
=(2n)!/(n+1)!(2n-n-1)!=(2n)!/(n+1)!(n-1)!=
*n/(n+1)
即：我们可以推导出通项公式为：
以上，我们也可以推导出卡特兰数Cn的递推公式，因此本题的代码如下：
#includeusing namespace std;const int N=19;typedef long long ll;
ll c[N];
int main(){ int n; cin>>n; c[0] = 1; for(int i=1;i<=n;++i){ c[i] = c[i-1]*(4*i-2)/(i+1); } printf("%lld\n",c[n]); return 0;}
2）、括号序列：有n对括号，有多少种“括号匹配”的括号序列？
题解：其实跟上一题一样，也是要利用栈的思想，跟进出栈的序列的题一样，把左括号看成是+1，右括号看成是-1，则就转化为上述可以用卡特兰数列解决的问题了。
3）、二叉树：n+1个叶子结点能够构成多少种形状不同的国外（国际）满二叉树。
国外(国际)满二叉树定义:a binary tree T is full if each node is either a leaf or possesses exactly two childnodes.
题解：一样的思路，根据国际满二叉树的定义，从一个结点出发，左孩子和右孩子是成对出现的，左孩子记为+1，右孩子记为-1，则又可以转化为上述的题型。如下图所示是n=4时的转化示例：
4）、电影购票：有2n 个人排成一行进入剧场。入场费 5 元。其中只有n个人有一张 5 元钞票，另外n人只有 10 元钞票，剧院无其它钞票（初始钞票为0），问有多少种方法使得只要有 10 元的人买票，售票处就有 5 元的钞票找零？即有多少种排队方式，可以让每个人都买到电影票。
题解：持有5元的人买票不用找零，并且可以给后面持有10元的人找零用。而持有10元的人则每次购买都需要找零，且刚好跟之前买票的5元“对冲”掉了。聪明的你一定可以由上面的题触类旁通。即将持有5元的购买标记为+1，持有10元的购买标记为-1。这样就又把问题转化为跟第一题一样的题型了。
5）、路线问题：一位大城市的律师在她住所以北n个街区和以东n个街区处工作。每天她走2n个街区去上班。如果他从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？（思路也是一样的，向北记为+1，向东记为-1）（注：通过路线问题，也可以启发另外一种解题思路，就是利用直角坐标系，画出对应的格点，然后以y=x为界限进行分析。）
题型二：多边形三角划分方案数。
6）、对角线不相交的情况下，将一个凸多边形区域分成三角形区域的方案数？
题解：记C(n)表示n个顶点的多边形划分出的小三角形数量，并规定C(0) = 1。则C(n-1)表示去掉一个顶点后可以划分出的小三角形的数量，如下图所示：
表示去掉顶点“1”后，C(0)是由顶点“1、2、6”构成的三角形数量，C(n-1)表示的是剩余顶点构成的三角形的数量，显然两者之间是分步骤的关系，因此在加上其他的分类情况，可以得到C(n)=C(0)*C(n-1)+C(1)*C(n-2)+...+C(n-1)*C(0)。也就是卡特兰数列的递推式了。
7）、在圆上选择2n个点，将这些点成对连接起来使得所得到的n条线段不相交的方案数？（思路跟上述的题一样，最终都是卡特兰数列）
3、小结
卡特兰数的问题，在初赛和复赛中都会有，比如凸多边形三角划分问题就是复赛中典型的dp题，实质上很多dp题都是跟组合数学有关的。通过应用，我们知道卡特兰数问题，基本可以分类两大类的问题进行讨论。因此，只要我们能够学会进出栈问题的解法，以及多边形三角划分模型，则能够以不变应万变。
当遇到匹配关系的计数问题时，我们就可以考虑是否是卡特兰数问题。更一般地，我们还可以记住序列前四项：1、 1、 2、 5，这些也可以帮助我们用作判断卡特兰数问题的线索。这一讲就先到这里，谢谢大家的时间。