假期做题的时候做到一道关于入栈出栈的题，找到了一篇挺有用的文章。
卡特兰数(Catalan number) 其实来源于卡特兰解决凸 n + 2边形的剖分问题得到的数列 f ( n ) （为了便于区分组合数，这里用 f ( n )表示）。卡特兰数是组合数学中常出现在各种计数问题中的数列。
1 , 1 , 2 , 5 , 14 , 42 , 132… 1,1,2,5,14,42,132… 1,1,2,5,14,42,132…
卡特兰数的性质
通项公式: 
递推公式:
递归公式:
接下来我们通过一系列的例子来深入理解一下卡特兰数。
走格子
走格子问题是对应卡特兰数的一个几何问题，可以从几何的角度来解释。
Description:
在 n ∗ n 的网格中，起始点为 ( 0 , 0 ) ，终点为 ( n , n ) ，每次可以向右或者向上走一步，在任意一个时刻，往右走的次数要 ⩾ 往上走的的次数。
Answer: 经过发现，所有合格路径否是不能触碰 y = x + 1这条直线的，只要碰到就说明这是一条不合法的路径。
下面我们从反面的角度分析，画一条不合法的路径(紫色的)，然后把这条路径沿着 y = x + 1对称过去，然后我们会发现，路径的终点变成了 ( n − 1 , n + 1 )。其实不管哪条不合法路径通过这条线对称过去，最终的终点都会变成 ( n − 1 , n + 1 ) ，所以说，所有的不合法路径都是唯一对应着一条到 ( n − 1 , n + 1 )的路径，那么不合法的路径总数为 C 2 n n − 1 C_{2n}^{n-1} C2nn−1。那么合法的路径总数就为 C 2 n n − C 2 n n − 1 C_{2n}^{n}-C_{2n}^{n-1} C2nn−C2nn−1。 ==(通项公式)==
进出栈
Description:
给定一个栈，有 n 次进栈， n 次出栈，总共 2 n次操作，问总共有多少合法的进出栈序列。
Answer:
其实我们可以知道，每一次进栈必须与一个出栈相对应，也就是说，在任何一个进出栈序列的任意一个位置上，进栈的次数必须 ⩾出栈的次数。
和上述的走格子方法是一样的，可以将进栈看作向右走一步，出栈是向上走一步，因此合法的进出栈序列个数为 C 2 n n − C 2 n n − 1 C_{2n}^{n}-C_{2n}^{n-1} C2nn−C2nn−1。 (通项公式)
与之相同分析方法的还有:
- 括号问题 ， n 个左括号， n个右括号，问有多少个长度为 2 n的括号序列使得所有的括号都是合法的。 (通项公式)
- 312排列 ，一个长度为 n的排列 a，只要满足 i < j < k且 a j < a k < a i ，这个排列就称为312排列。求 n 中全排列中不是312排列得排列个数。
其实就是看一个排列 是否能用 1 , 2 , 3 , . . . , n − 1 , n利用进出栈来表示出来，312排列就是所有不能表示出来得排列，这个问题就转换成了进出栈问题，也是卡特兰数。 (通项公式) - 01序列 ，有 n个0， n 个1，问有多少个长度为 2n得序列，使得序列中的任意一个位置往前，1的个数≥0的个数。 (通项公式)
圆内连弦
Description:
圆上有 2n个点，以这些点为端点连互不相交的 n条弦，求连接的所有方法总数。
Answer:
我们规定start为起始点，顺时针方向为正方向。
从start开始，将一条弦 最先遇到的那个端点标记为 +，后来遇见的另一个端点为标记为 −，就可以得到如下图。
对于标蓝的点来说，我们可以看出，在它之前， +号的标记是必须 ⩾ −号的标记的。
这样一来，就又是上述问题同样的解法了， C 2 n n − C 2 n n − 1 C_{2n}^{n}-C_{2n}^{n-1} C2nn−C2nn−1。 (通项公式)
二叉树的构成问题
Description:
有 n个点，问用这 n个点最终能构成多少个不同的二叉树？
Answer:
这个问题使用的是 递归公式 推导的。
一个二叉树由根节点、左子树、右子树构成，左子树和右子树又是一个二叉树，并且左右子树的节点数之和为 n − 1。
我们假设 i个点可以构成 f ( i )个二叉树，那么 f ( i )就是左右子树可以构成的二叉树个数的乘积。
那么 f ( n ) = f ( 0 ) ∗ f ( n − 1 ) + f ( 1 ) ∗ f ( n − 2 ) + . . . + f ( n − 1 ) ∗ f ( 0 ) f(n)=f(0)*f(n-1)+f(1)*f(n-2)+…+f(n-1)*f(0) f(n)=f(0)∗f(n−1)+f(1)∗f(n−2)+…+f(n−1)∗f(0)，答案也是卡特兰数。
凸边形的剖分
Description:
求凸 n + 2 边形用其 n − 1 条对角线分割为互不重叠的三角形的分法总数。
Answer:
这个和上面那个二叉树的差不多。我们可以先随便连接两个顶点，这个凸多边形就会被划分为两个小的凸多边形，由于每条直线不能相交，那么这个凸多边形的方案数，就是两个小凸多边形的划分方案的乘积。
也是根据递推式推。
阶梯的矩形填充
用 n个长方形去填充一个高度为 n的阶梯图形的方法数。
我们可以看出每一个红色的小角肯定是属于不同的矩形。我们可以考虑一下与左下角那个紫色同属于一个矩形的是哪个角，假设是和第三个角属于一个矩形，那么这个矩形又将这个阶梯分成两个小梯形，这样就可以写出递推式了，所以所有的填充方案数就是卡特兰 f ( n ) 了。
