什么是卡特兰数？有哪些应用？
“ 卡特兰数又称卡塔兰数，是组合数学中一种常出现于各种计数问题中的数列。”
一、简单介绍
卡特兰数是一个数列，其前几项为（从第零项开始） : 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, ......
卡特兰数满足如下递推关系：
其中 表示数列的第 项。根据上述第一个式子我们可以推出：
第二个推导式用于编程实现卡特兰数。
二、应用
2.1进出栈问题
【问题描述】
1， 2， 3， 4依次进栈，则可能的一种进出栈顺序为：1in->2in->2out->3in->4in->4out->3out->1out，所以出栈顺序为：2431，那么请问按照1， 2， 3， 4，...， n依次进栈，出栈顺序种数h(n)为多少？
【问题分析】
对n个数，假设数k最后一个出栈，k有n种可能，即每一个数都有可能最后出栈，我们算出每一种可能各有多少种情况，最后相加即可。
因为k最后一个出栈，而进栈顺序又是从小到大来的，所以k前面的k-1个数在k进栈以前就已经全部出栈了，我们把前面k-1个数看出一个整体，那么全面k-1个数的出栈情况实际上就有h(k-1)种。
在k进栈之后，比k大的n-k个数才能进栈，但是它们又比k早出栈，把这n-k个数同样看成一个整体，共有h(n-k)种可能。 二者综合一下，当数k最后出栈时，一共有h(k-1)h(n-k)种可能，k从1取到n，再把每种可能相加即得到最终答案：
简而言之就是数k把这段序列分成了两部分：比k大的部分和比k小的部分。因为中间有k隔着，而它们又必须按照从小到大的次序进栈，所以这两部分进出栈是相互不影响的。
很明显可以看出，该表达式就是卡特兰数的递推式。
2.2排队方式
【问题描述】
n个人手拿5元，n个人手拿10元，他们去排队买东西，东西价值5元，老板没有零钱（老板必须用收取的5元钞票给支付10元的顾客找零钱），请问一共有多少种排队方式？
【问题分析】
将持5元者到达视作将5元入栈，持10元者到达视作使栈中某5元出栈， 实际上也就转换成了进出栈问题，答案也为h(n)。
2.3二叉树生成问题
【问题描述】
有n个结点，请问总共能构成多少种不同的二叉树？
【问题分析】
假设采用中序遍历，根节点第k个被访问，则根的左子树共有k-1个结点，右子树共有n-k个结点，k同样可以取1-n，这就与进出栈问题分析思路一致了，所以一共h(n)种。
2.4凸多边形三角形划分
【问题描述】
一个凸的n边形，用直线连接它的两个顶点使之分成多个三角形，每条直线不能相交，问一共多少种方案？比如凸六边形的划分情况为： 。
【问题分析】
我们将凸多边形顶点从p1一直编号到pn，以p1pn这条边为基准，任选一个数k（2<=k<=n-1），将p1，pk以及pn三点连接，构成了一个三角形。该三角形把该凸边形划分成了两个凸边形，一边顶点为1 ~ k-1，另一边为k+1 ~ n，于是又回到了进出栈问题，所以答案依旧为：h(n)。
2.5括号匹配问题
【问题描述】
由1对括号，可以组成一种合法括号序列：()。 由2对括号，可以组成两种合法括号序列：()()、(())。 由n对括号组成的合法括号序列一共有多少种？
【问题分析】
考虑n对括号时的任意一种配对方案，最后一个右括号有唯一的与之匹配的左括号，于是有唯一的表示A(B)，其中A和B也是合法的括号匹配序列。
假设S(n)为n对括号的正确配对数目，那么有递推关系S(n)=S(0)S(n-1)+S(1)S(n-2) +...+S(n-1)S(0)，显然S(n)是卡特兰数。
2.6满二叉树个数
【问题描述】
n+1个叶子的满二叉树个数为多少？
【问题分析】
不再分析，答案为h(n)。
2.7圆划分问题
【问题描述】
在圆上选2n个点，讲这些点成对连接起来，保证所有直线不相交，问一共多少种可能？
【问题分析】
答案为h(n)。
2.8填充问题
【问题描述】
n个长方形填充一个高度为n的阶梯状图像方法数为多少？
【问题分析】
答案为h(n)。
代码实现：
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn = 20;
int n;
ll f1[maxn], f2[maxn];
ll f[maxn * 2][maxn];
//公式1:
int solve1() {
f1[0] = f1[1] = 1;
cin >> n;
for(int i = 2; i <= n; i++) {
for(int j = 0; j < i; j++) {
f1[i] += (f1[j] * f1[i-j-1]); //f(n)=f(0)f(n-1)+f(1)f(n-2)+...+f(n-1)f(0)
}
}
printf("%lld\n",f1[n]);
return 0;
}
//公式2:
int solve2() {
f2[0] = f2[1] = 1;
cin >> n;
for(int i = 2; i <= n; i++)
{
f2[i] += f2[i - 1] * (4 * i - 2) / (i + 1); //f(n)=f(n-1)*(4*n-2)/(n+1)
}
printf("%lld\n", f2[n]);
return 0;
}
//公式3:
int solve3() {
cin >> n;
for(int i = 1; i <= 2 * n; i++) {
f[i][0] = f[i][i] = 1;
for(int j = 1; j < i; j++) {
f[i][j] = f[i - 1][j] + f[i - 1][j - 1]; //f(n)=c(2n,n)/(n+1)
}
}
printf("%lld",f[2 * n][n] / (n + 1));
return 0;
}
int main() {
solve1();
solve2();
solve3();
return 0;
}