卡特兰(Catalan)数入门详解

卡特兰(Catalan)数入门详解

卡特兰数（Catalan数）是组合数学中一个重要的数列，在各类计数问题中有着广泛的应用。本文将从基本概念出发，通过递归定义、递推关系和通项公式等多个角度深入解析卡特兰数，并结合多个经典实例帮助读者全面理解这一数学概念。

基本概念

介绍

卡特兰数是一个在组合数学里经常出现的数列，它并没有一个具体的意义，却是一个十分常见的数学规律。对卡特兰数的初步理解：有一些操作，这些操作有着一定的限制，如一种操作数不能超过另外一种操作数，或者两种操作不能有交集等，这些操作的合法操作顺序的数量。为了区分组合数，这里用
fn
表示卡特兰数的第
n
项。从零开始，卡特兰数的前几项为。

  
1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845,35357670,129644790…
  

定义

递归定义
$f_{n} = f_{0}f_{n-1} + f_{1}f_{n-2}+\cdots+f_{n-1}*f_{0}$

递推关系
$f_{n} = \frac{4n-2}{n+1}f_{n-1}$

通项公式
$f_{n} = \frac{1}{n+1}C_{2n}^{n}$

经化简后可得
$f_{n} = C_{2n}^{n} - C_{2n}^{n-1}$

只要我们在解决问题时得到了上面的一个关系，那么你就已经解决了这个问题，因为他们都是卡特兰数列

实际问题

先用一个最经典的问题来帮助理解卡特兰数，去掉了所有的掩饰，将问题直接写出来就是

例题1

在一个
w×h
的网格上，你最开始在
(0,0)
上，你每个单位时间可以向上走一格，或者向右走一格，在任意一个时刻，你往右走的次数都不能少于往上走的次数，问走到
(n,n),0≤n
有多少种不同的合法路径。

合法路径个数为$C_{2n}^{n} - C_{2n}^{n-1}$，直接求不好，考虑求有多少种不合法路径路径总数为在
2n
次移动中选n次向上移动，即$C_{2n}^{n}$，画一下图，我们把
y=x+1
这条线画出来，发现所有的合法路径都是不能碰到这条线的，碰到即说明是一条不合法路径先随便画一条碰到这条线的不合法路径，所有的不合法路径都会与这条线有至少一个交点，我们把第一个交点设为
(a,a+1)
如图

我们把
(a,a+1)
之后的路径全部按照
y=x+1
这条线对称过去，这样，最后的终点就会变成
(n−1,n+1)
由于所有的不合法路径一定会与
y=x+1
有这么一个交点，我们可以得出，所有不合法路径对称后都唯一对应着一条到
(n−1,n+1)
的路径，且所有到
(n−1,n+1)
的一条路径都唯一对应着一条不合法路径（只需将其对称回去即可），所以不合法路径总数是$C_{2n}^{n-1}$，那么合法的路径总数为$C_{2n}^{n} - C_{2n}^{n-1}$，这是一个非常好用且重要的一个方法，其它的问题也可以用该方法解决即找到不合法路径唯一对应的到另一个点的路径

其它卡特兰数例子

01序列

你现在有
n
个
0
和
n
个
1
，问有多少个长度为
2n
的序列，使得序列的任意一个前缀中
1
的个数都大于等于
0
的个数 例如
n = 2
时有
1100,1010
两种合法序列，而
1001、0101、0110、0011
都是不合法的序列，合法的序列个数为$C_{2n}^{n} - C_{2n}^{n-1}$，我们把出现一个
1
看做向右走一格，出现一个
1
看做向上走一格，那么这个问题就和上面的例题
1
一模一样了

拓展

如果是
n
个
1
，
m
个
0
呢，不过是最后的终点变为了
(n,m)
罢了。如果是
1
的个数不能够比
m
少
k
呢，我们只需将
y=x+1
这条线上下移动即可。

括号匹配

你有
n
个左括号，
n
个右括号，问有多少个长度为
2n
的括号序列使得所有的括号都是合法的合法的序列个数为$C_{2n}^{n} - C_{2n}^{n-1}$，要使所有的括号合法，实际上就是在每一个前缀中左括号的数量都不少于右括号的数量，将左括号看做
1
，右括号看做
0
，这题又和上面那题一模一样了

进出栈问题

有一个栈，我们有
2n
次操作，
n
次进栈，
n
次出栈，问有多少中合法的进出栈序列，合法的序列个数为$C_{2n}^{n} - C_{2n}^{n-1}$，要使序列合法，在任何一个前缀中进栈次数都不能少于出栈次数…后面就不用我说了吧，和上面的问题又是一模一样的了

312排列

一个长度为
n
的排列
a
，只要满足
i<j<k
且
aj<ak<ai
就称这个排列为
312
排列，求
n
的全排列中不是
312
排列的排列个数，答案也是卡特兰数。

我们考虑
312
排列有什么样的特征，如果考虑一个排列能否被
1,2,3,…,n−1,n
排列用进栈出栈来表示，那么
312
排列就是所有不能被表示出来的排列，那么这个问题就被转化成进出栈问题了。

不相交弦问题

在一个圆周上分布着
2n
个点，两两配对，并在这两个点之间连一条弦，要求所得的
2n
条弦彼此不相交的配对方案数，当
n=4
时，一种合法的配对方案为如图

合法的序列个数为$C_{2n}^{n} - C_{2n}^{n-1}$ 这个问题没有上面的问题那么显然，我们规定一个点为初始点，然后规定一个方向为正方向，如规定最上面那个点为初始点，逆时针方向为正方向，然后我们把一个匹配第一次遇到的点（称为起点）旁边写一个左括号((，一个匹配第二次遇到的点（称为终点）旁边写一个右括号))，如图

看出来吗，在规定了这样的一个顺序后，在任意一个前缀中起点的个数都不能少于终点的个数，于是这又是一个卡特兰数列了。

二叉树构成问题

有
n
个点，问用这
n
个点最终能构成多少二叉树，答案仍然是卡特兰数列。这个问题不是用上面的方法，是用递归定义的卡特兰数，一个二叉树分为根节点，左子树，右子树，其中左子树和右子树也是二叉树，左右子树节点个数加起来等于
n−1
，设
i
个点能构成
fi
个二叉树，我们枚举左子树有几个点可得$f_{n} = f_{0}f_{n-1} + f_{1}f_{n-2}+\cdots+f_{n-1}*f_{0}$，这个和卡特兰数列的递归定义是一模一样的。

凸多边形的三角划分

一个凸的
n
边形，用直线连接他的两个顶点使之分成多个三角形，每条直线不能相交，问一共有多少种划分方案，答案还是卡特兰数列，我们在凸多边形中随便挑两个顶点连一条边，这个凸多边形就会被分成两个小凸多边形，由于每条直线不能相交，接下来我们就只要求这两个小凸多边形的划分方案然后乘起来即可，和二叉树的构成问题一样，我们枚举大凸多边形被分成的两个小凸多边形的大小即可。