鉴于Noip初赛考到了卡特兰数.....整理一下。凑合着看。
一、介绍
卡特兰数是一种经典的组合数，经常出现在各种计算中，其前几项为:
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(n) = C(1)*C(n-1) + C(2)*C(n-2) + ... + C(n-1)C(1)，n>=2
一般性质：
三、证明 (挺神奇的.jpg
给你一个只有0和1的序列，n个0和n个1，从左向右扫描，要求任何是一个位置前缀1的个数大于等于
前缀0的个数，若不符合要求，则为不合法序列。则合法序列的个数为C(n,2n)-C(n+1,2n);证明这个问
题的答题思路是用所有序列的个数-不符合条件的个数。
S1：如果不考虑前缀1的个数大于等于0的个数，则方案数有C(n,2n)种。
S2：那么不符合条件的方案数有多少种呢？接下来证明，不符合条件的方案数有C(n+1,2n)种。
假如n=5,我随便写一种不符合条件的序列。1010010101
从左往右扫描，发现到第5个位置，0的个数为3,1的个数为2，这是第一个不符合要求的位置。那么我们
可以知道任何个不符合要求的序列，一定存在一个奇数位,此时前缀有m+1个0和m个1。则这个位置后面
还有n-(m+1)个0和(n-m)个1.此时把后面的0改成1,1改成0；那么后面就有了n-(m+1)个1和(n-m)个0；
那么总的序列就有，(m+1)+(n-m)=n+1个0，m+(n-m-1)=n-1个1。此时序列就变成有n+1个0，n-1个
1的序列。由于0比1多两个。所以这个序列无论怎么排一定不合法。设第一个不合法的位置是x,则前
有m+1和0和m个1。这时把x后的0变成1,1变成0后，这个序列又回到了n个1，n个0的序列。所以不符
合条件的序列个数就是n+1个0和n-1个1的所有排列。
四、应用
下面其实都是网上抄的...
(1)
对于一个n*n的正方形网格，每次只能向右或者向上移动一格，那么从左下角到右上角
所有在副对角线右下方的路径总数为
(2)对凸n+2边形进行不同的三角形分割（只连接顶点对形成n个三角形）数为Cn
(3)n个数入栈后的出栈的排列总数是
(4)n层的阶梯切割为n个矩形的切法数也是
(5)在一个2*n的格子中填入1到2n这些数值使得每个格子内的数值都
比其右边和上边的所有数值都小的情况数也是
(6)我们可以将应用1变换形式：将-1看成右括号，+1看成左括号，就变成了左括号和右括号各有n个时，合法括号表达式的个数。比如2个左括号和2个右括号组成的合法表达式有
种，是()()和(())。