什么是卡特兰数？有哪些应用？

“ 卡特兰数又称卡塔兰数，是组合数学中一种常出现于各种计数问题中的数列。”

一、简单介绍

卡特兰数是一个数列，其前几项为（从第零项开始） : 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;
}