卡特兰数详解：定义、性质与应用
卡特兰数详解：定义、性质与应用
卡特兰数简介
卡特兰数（Catalan Number）是组合数学中一个重要的数列，在很多不同的组合问题中都有出现。它们在ACM-ICPC竞赛中也经常被用于解决各种复杂的问题。本节将详细介绍卡特兰数的定义、性质以及应用。
卡特兰数的定义
卡特兰数是一列自然数，通常用C_n表示。卡特兰数的递推公式为：
$$
C_n = \sum_{i=0}^{n-1} C_i C_{n-i-1}
$$
其中，C_0 = 1。卡特兰数也可以通过二项式系数表示：
$$
C_n = \frac{1}{n+1} \binom{2n}{n}
$$
卡特兰数的性质
卡特兰数有许多有趣的性质和组合解释，其中一些主要性质包括：
- 递归关系：如上所示，卡特兰数可以通过递归公式进行计算。
- 生成函数：卡特兰数的生成函数为：
$$
C(x) = \frac{1 - \sqrt{1 - 4x}}{2x}
$$
- 多项式表示：卡特兰数可以通过多项式表示，使其在组合数学中具有广泛的应用。
卡特兰数的应用
卡特兰数在许多组合问题中都有应用，以下是几个典型的例子：
- 括号匹配问题：有n对括号，有多少种合法的括号匹配方式？
- 二叉树问题：有n个节点的不同二叉树的数量。
- 凸多边形的三角剖分：有n+2个顶点的凸多边形可以分成多少个三角形。
Catalan 数列
Catalan 数列 H_n 可以应用于以下问题：
- 剧场排队问题：有 2n 个人排成一行进入剧场。入场费 5 元。其中只有 n 个人有一张 5 元钞票，另外 n 人只有 10 元钞票，剧院无其它钞票，问有多少种方法使得只要有 10 元的人买票，售票处就有 5 元的钞票找零？
- 方格路径问题：有一个大小为 n×n 的方格图，左下角为 (0, 0) 右上角为 (n, n)，从左下角开始每次都只能向右或者向上走一单位，不走到对角线 y=x 上方（但可以触碰）的情况下到达右上角有多少可能的路径？
- 圆上不相交线段问题：在圆上选择 2n 个点，将这些点成对连接起来使得所得到的 n 条线段不相交的方法数？
- 凸多边形三角剖分问题：对角线不相交的情况下，将一个凸多边形区域分成三角形区域的方法数？
- 栈出栈序列问题：一个栈（无穷大）的进栈序列为 1,2,3,...,n 有多少个不同的出栈序列？
- 不同二叉树问题：n 个结点可构造多少个不同的二叉树？
- 特定部分和问题：由 n 个 +1 和 n 个 -1 组成的 2n 个数 a_1,a_2,...,a_{2n}，其部分和满足 a_1+a_2+...+a_k ≥ 0 (k=1,2,3,...,2n)，有多少个满足条件的数列？
其对应的序列为：
H_0 H_1 H_2 H_3 H_4 H_5 H_6 ...
1 1 2 5 14 42 132 ...
递推式
该递推关系的解为：
$$
C_n = \frac{1}{n+1} \binom{2n}{n}
$$
关于 Catalan 数的常见公式：
例题 洛谷 P1044 栈
题目大意：入栈顺序为 1,2,...,n，求所有可能的出栈顺序的总数。
#include <iostream>
using namespace std;
int n;
long long f[25];
int main() {
f[0] = 1;
cin >> n;
for (int i = 1; i <= n; i++) f[i] = f[i - 1] * (4 * i - 2) / (i + 1);
// 这里用的是常见公式2
cout << f[n] << endl;
return 0;
}
封闭形式
卡特兰数的递推式为：
$$
C_n = \sum_{i=0}^{n-1} C_i C_{n-i-1}
$$
其中 H_0=1, H_1=1。设它的普通生成函数为 H(x)。
我们发现卡特兰数的递推式与卷积的形式很相似，因此我们用卷积来构造关于 H(x) 的方程：
$$
H(x) = 1 + xH(x)^2
$$
解得：
$$
H(x) = \frac{1 - \sqrt{1 - 4x}}{2x}
$$
那么这就产生了一个问题：我们应该取哪一个根呢？我们将其分子有理化：
$$
H(x) = \frac{1 - \sqrt{1 - 4x}}{2x} = \frac{2}{1 + \sqrt{1 - 4x}}
$$
代入 x=0，我们得到的是 H(x) 的常数项，也就是 H_0。当：
$$
H(x) = \frac{1 - \sqrt{1 - 4x}}{2x}
$$
的时候有 H(0)=1，满足要求。而另一个解会出现分母为 0 的情况（不收敛），舍弃。
因此我们得到了卡特兰数生成函数的封闭形式：
$$
H(x) = \frac{1 - \sqrt{1 - 4x}}{2x}
$$
接下来我们要将其展开。但注意到它的分母不是斐波那契数列那样的多项式形式，因此不方便套用等比数列的展开形式。在这里我们需要使用牛顿二项式定理。我们来先展开 1−4x\sqrt{1-4x}1−4x ：
$$
(1 - 4x)^{-\frac{1}{2}} = \sum_{k=0}^{\infty} \binom{-\frac{1}{2}}{k} (-4x)^k
$$
注意到：
$$
\binom{-\frac{1}{2}}{k} = \frac{(-\frac{1}{2})(-\frac{1}{2}-1)\cdots(-\frac{1}{2}-k+1)}{k!} = \frac{(-1)^k (2k-1)!!}{2^k k!}
$$
这里使用了双阶乘的化简技巧。那么带回得到：
$$
(1 - 4x)^{-\frac{1}{2}} = \sum_{k=0}^{\infty} \frac{(2k-1)!!}{2^k k!} (-4x)^k
$$
带回原式得到：
$$
H(x) = \frac{1}{2x} \left( 1 - \sum_{k=0}^{\infty} \frac{(2k-1)!!}{2^k k!} (-4x)^k \right)
$$
这样我们就得到了卡特兰数的通项公式。
实例分析
以下是一个使用卡特兰数解决括号匹配问题的例子：
def catalan_number(n):
if n == 0 or n == 1:
return 1
catalan = [0] * (n + 1)
catalan[0], catalan[1] = 1, 1
for i in range(2, n + 1):
for j in range(i):
catalan[i] += catalan[j] * catalan[i - 1 - j]
return catalan[n]
# 计算第5个卡特兰数
n = 5
print(f"第{n}个卡特兰数是: {catalan_number(n)}")
输出结果：
第5个卡特兰数是: 42
总结
卡特兰数是组合数学中的一个重要数列，广泛应用于括号匹配、二叉树计数和多边形三角剖分等问题。通过掌握卡特兰数的性质和应用，可以更好地解决ACM-ICPC竞赛中的组合数学问题。在实际应用中，递归和动态规划是计算卡特兰数的两种主要方法。