卡特兰数
一、课上练习
编程练习
- 栈：L49970
二、知识总结
✨ 核心思想
卡特兰数（Catalan Number）是组合数学中一个神奇的数列，它在看似毫不相关的问题中反复出现。从合法括号序列、二叉搜索树计数到出栈序列，许多经典计数问题的答案都是卡特兰数。识别出"卡特兰数结构"是竞赛中的重要技能。
✨ 定义与公式
卡特兰数列：1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, ...
第 n 个卡特兰数 Cₙ（从第 0 项开始）有多种等价公式：
通项公式：
Cₙ = C(2n, n) / (n+1)
等价形式：
Cₙ = C(2n, n) - C(2n, n+1)
递推公式：
C₀ = 1, Cₙ = Σ(i=0 to n-1) Cᵢ × C(n-1-i)（n ≥ 1）
递推关系：
Cₙ = Cₙ₋₁ × 2(2n-1) / (n+1)
✨ 经典计数问题
以下问题的答案都是卡特兰数 Cₙ：
1. 合法括号序列：n 对括号组成的合法序列数。例如 n=3 时有 5 种：((())), (()()), (())(), ()(()), ()()()
2. 二叉搜索树（BST）：n 个不同键值能构成的不同 BST 数量。
3. 出栈序列：1, 2, ..., n 依次入栈，可能的出栈序列数。
4. 三角剖分：凸 (n+2) 边形的三角剖分方案数。
5. 路径计数：从 (0,0) 到 (n,n) 的格点路径中，不穿过对角线 y=x 的路径数（每步只能向右或向上）。
6. 满二叉树：n+1 个叶子的满二叉树（每个内部节点恰有两个儿子）的形态数。
✨ 反射原理（路径计数证明）
为什么路径计数的答案是 C(2n,n) - C(2n,n+1)？
问题：从 (0,0) 到 (n,n)，每步向右(R)或向上(U)，要求路径不越过对角线（任何前缀中 R 的个数 ≥ U 的个数）。
总路径数：C(2n, n)（从 2n 步中选 n 步向右）
不合法路径数：路径越过对角线，即触碰到 y = x+1 这条线。
反射技巧：对于每条不合法路径，找到它第一次触碰 y=x+1 的点，将此点之前的部分关于 y=x+1 做镜像反射。这样的路径变成从 (-1, 1) 到 (n, n) 的路径，总步数不变，且与不合法路径一一对应。
从 (-1, 1) 到 (n, n) 的路径数 = C(2n, n+1)
所以合法路径数 = C(2n, n) - C(2n, n+1) = C(2n, n) / (n+1) = Cₙ
✨ 代码实现
1#include <iostream>
2using namespace std;
3typedef long long ll;
4const int MOD = 1e9 + 7;
5const int MAXN = 2000005;
6
7ll fac[MAXN], inv_fac[MAXN];
8
9ll qpow(ll base, ll exp, ll mod) {
10 ll result = 1;
11 base %= mod;
12 while (exp > 0) {
13 if (exp & 1) result = result * base % mod;
14 base = base * base % mod;
15 exp >>= 1;
16 }
17 return result;
18}
19
20void init(int n) {
21 fac[0] = 1;
22 for (int i = 1; i <= n; i++)
23 fac[i] = fac[i-1] * i % MOD;
24 inv_fac[n] = qpow(fac[n], MOD - 2, MOD);
25 for (int i = n - 1; i >= 0; i--)
26 inv_fac[i] = inv_fac[i+1] * (i+1) % MOD;
27}
28
29ll C(int n, int k) {
30 if (k < 0 || k > n) return 0;
31 return fac[n] % MOD * inv_fac[k] % MOD * inv_fac[n-k] % MOD;
32}
33
34// 方法1：通项公式 Cn = C(2n, n) / (n+1)
35ll catalan_formula(int n) {
36 return C(2 * n, n) % MOD * qpow(n + 1, MOD - 2, MOD) % MOD;
37}
38
39// 方法2：差值公式 Cn = C(2n, n) - C(2n, n+1)
40ll catalan_diff(int n) {
41 return (C(2 * n, n) - C(2 * n, n + 1) + MOD) % MOD;
42}
43
44int main() {
45 int n;
46 cin >> n;
47 init(2 * n);
48
49 cout << "C_" << n << " = " << catalan_formula(n) << endl;
50 cout << "验证: " << catalan_diff(n) << endl;
51
52 return 0;
53}1#include <iostream>
2using namespace std;
3typedef long long ll;
4const int MOD = 1e9 + 7;
5
6// 递推公式: cat[n] = sum(cat[i] * cat[n-1-i]) for i in 0..n-1
7// 时间复杂度 O(n^2)，适合 n ≤ 5000
8ll cat[5005];
9
10void init_catalan(int n) {
11 cat[0] = 1;
12 for (int i = 1; i <= n; i++) {
13 cat[i] = 0;
14 for (int j = 0; j < i; j++) {
15 cat[i] = (cat[i] + cat[j] % MOD * cat[i-1-j]) % MOD;
16 }
17 }
18}
19
20int main() {
21 int n;
22 cin >> n;
23 init_catalan(n);
24
25 cout << "卡特兰数列前 " << n + 1 << " 项：" << endl;
26 for (int i = 0; i <= n; i++) {
27 cout << "C_" << i << " = " << cat[i] << endl;
28 }
29 return 0;
30}1#include <iostream>
2using namespace std;
3typedef long long ll;
4const int MOD = 1e9 + 7;
5const int MAXN = 2000005;
6
7ll fac[MAXN], inv_fac[MAXN];
8
9ll qpow(ll base, ll exp, ll mod) {
10 ll result = 1; base %= mod;
11 while (exp > 0) {
12 if (exp & 1) result = result * base % mod;
13 base = base * base % mod; exp >>= 1;
14 }
15 return result;
16}
17
18void init(int n) {
19 fac[0] = 1;
20 for (int i = 1; i <= n; i++) fac[i] = fac[i-1] * i % MOD;
21 inv_fac[n] = qpow(fac[n], MOD - 2, MOD);
22 for (int i = n-1; i >= 0; i--) inv_fac[i] = inv_fac[i+1] * (i+1) % MOD;
23}
24
25ll C(int n, int k) {
26 if (k < 0 || k > n) return 0;
27 return fac[n] % MOD * inv_fac[k] % MOD * inv_fac[n-k] % MOD;
28}
29
30// n 对括号的合法序列数 = 第 n 个卡特兰数
31ll count_parentheses(int n) {
32 return (C(2*n, n) - C(2*n, n+1) + MOD) % MOD;
33}
34
35int main() {
36 int n;
37 cin >> n;
38 init(2 * n);
39 cout << n << " 对括号的合法序列数: " << count_parentheses(n) << endl;
40 return 0;
41}✨ 应用示例
示例 1：3 个元素 1,2,3 依次入栈，有多少种可能的出栈序列？
C₃ = C(6,3)/4 = 20/4 = 5
5 种出栈序列为：
- 1,2,3（push1, pop1, push2, pop2, push3, pop3）
- 1,3,2（push1, pop1, push2, push3, pop3, pop2）
- 2,1,3（push1, push2, pop2, pop1, push3, pop3）
- 2,3,1（push1, push2, pop2, push3, pop3, pop1）
- 3,2,1（push1, push2, push3, pop3, pop2, pop1）
注意 3,1,2 是不可能的（3 先出意味着 1,2 都在栈中，而 2 在 1 上面，必须先出 2）。
示例 2：4 个节点的不同 BST 数量
C₄ = C(8,4)/5 = 70/5 = 14
示例 3：凸六边形的三角剖分方案数
n+2 = 6，所以 n = 4，答案 = C₄ = 14
✨ 解题步骤详解
- 识别卡特兰结构：看到以下特征时考虑卡特兰数：
- 匹配/嵌套结构（括号、出栈）
- 二叉树形态
- 不穿过某条线的路径
- 递归分割结构
- 确定 n 的值：根据问题参数确定 Cₙ 中的 n
- 选择计算方法：
- 大 n + 大素数模数：通项公式 + 逆元
- 小 n 或需要前几项：递推
- 验证：用小数据手算验证
识别技巧：如果一个问题可以分解为"左半部分大小为 i，右半部分大小为 n-1-i"的递归结构，且答案满足 f(n) = Σ f(i) × f(n-1-i)，那么答案就是卡特兰数。
✨ 常见错误
- 卡特兰数的下标从 0 开始，搞错了 n 的对应关系
- 通项公式中除以 (n+1) 忘记用逆元（在模意义下不能直接除）
- 递推公式的复杂度是 O(n²)，当 n 很大时应该用通项公式
- 混淆"n 个元素"和"C_n"的关系（如出栈问题中 n 个元素对应 Cₙ）
- 差值公式中减法忘记加 MOD 防止负数
✨ 算法评价
| 方法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 通项公式 | O(n) | O(n) | 大 n，需预处理阶乘 |
| 递推（卷积） | O(n²) | O(n) | 小 n 或需要所有值 |
| 递推关系 | O(n) | O(n) | 需要顺序生成 |
卡特兰数是竞赛中出现频率最高的特殊数列之一，其核心在于识别问题中的卡特兰结构。当你发现一个计数问题具有"递归二分"的特征时，先算几个小值（1, 1, 2, 5, 14, ...），如果符合就大概率是卡特兰数。