Catalan数-卡特兰数

一、定义

卡特兰数是一个数列，满足递推关系：h(0)=1，h(1)=1，h(n) = h(0)*h(n-1) + h(1)*h(n-2) + … + h(n-1)h(0)，n>=2该递推关系的解为：h(n+1) = C(2n,n)/n+1，n=1,2,3,…（其中C(2n,n)表示2n个中取n个的组合数）

二、应用

1.进出栈问题
【问题描述1】
  1， 2， 3， 4依次进栈，则可能的一种进出栈顺序为：
1in->2in->2out->3in->4in->4out->3out->1out，所以出栈顺序为：2431，那么请问按照1， 2， 3， 4，…， n依次进栈，出栈顺序种数h(n)为多少？
【问题分析1】
  对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，再把每种可能相加即得到最终答案：

很明显可以看出，该表达式就是卡特兰数的递推式。

【问题描述2】
排队方式
  n个人手拿5元，n个人手拿10元，他们去排队买东西，东西价值5元，老板没有零钱（老板必须用收取的5元钞票给支付10元的顾客找零钱），请问一共有多少种排队方式？
【问题分析】
  将持5元者到达视作将5元入栈，持10元者到达视作使栈中某5元出栈， 转换成进出栈问题，答案也为h(n)。

2.二叉树生成问题
【问题描述】
  有n个结点，请问总共能构成多少种不同的二叉树？
【问题分析】
  假设采用中序遍历，根节点第k个被访问，则根的左子树共有k-1个结点，右子树共有n-k个结点，k同样可以取1-n，这就与进出栈问题分析思路一致了，所以一共h(n)种。
  
3.凸多边形三角形划分
【问题描述】
  一个凸的n边形，用直线连接它的两个顶点使之分成多个三角形，每条直线不能相交，问一共多少种方案？
比如凸六边形的划分情况为：

h(6)=14。
【问题分析】
  我们将凸多边形顶点从p₁一直编号到p_n，以p₁p_n这条边为基准，任选一个数k（2<=k<=n-1），将p₁，p_k以及p_n三点连接，构成了一个三角形。该三角形把该凸边形划分成了两个凸边形，一边顶点为1 ~ k-1，另一边为k+1 ~ n，于是又回到了进出栈问题，所以答案依旧为：h(n)。

4.括号匹配问题
【问题描述】
由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)是卡特兰数。

5.满二叉树个数
【问题描述】
  n+1个叶子的满二叉树个数为多少？
【问题分析】
  不再分析，答案为h(n)。

6.圆划分问题
【问题描述】
  在圆上选2n个点，讲这些点成对连接起来，保证所有直线不相交，问一共多少种可能？
【问题分析】
  答案为h(n)。

7.填充问题
【问题描述】
  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;
} 

原博客1