1. 卡特兰数 (Catalan Number) 核心公式
(1) 封闭形式（最常用）
$$C_n = \frac{\binom{2n}{n}}{n+1} = \binom{2n}{n} - \binom{2n}{n-1}$$ 注意：这个公式适合在有大质数取模的情况下，配合逆元来直接计算。
(2) 递推形式一（卷积递推）
$$C_{n+1} = \sum_{i=0}^{n} C_i C_{n-i}$$ * 对应场景：这种形式最能体现“分治”思想。比如你提到的多边形三角剖分和二叉树计数。一个大问题被分成左右两个子问题。 * 边界：$C_0 = 1, C_1 = 1$。
(3) 递推形式二（线性递推）
$$C_n = \frac{4n-2}{n+1} C_{n-1}$$ * 对应场景：当需要线性时间 $O(n)$ 求出前 $n$ 个卡特兰数时使用。
2. 深入理解：折线法 (Reflection Principle)
你提到的“非法路径”对称很有启发性。这里明确一下坐标： 1. 总方案数：从 $(0,0)$ 走到 $(n,n)$，步数共 $2n$，其中 $n$ 步向上，$n$ 步向右，方案数为 $\binom{2n}{n}$。 2. 非法路径特征：至少触碰或越过直线 $y = x + 1$。 3. 对称映射：将非法路径第一次接触 $y = x + 1$ 之后的路径关于该直线对称，终点 $(n, n)$ 会变成 $(n-1, n+1)$。 4. 非法数：从 $(0,0)$ 走到 $(n-1, n+1)$ 的总方案数为 $\binom{2n}{n-1}$。 5. 结果：$C_n = \binom{2n}{n} - \binom{2n}{n-1}$。
3. 应用场景的逻辑联想（信息学必备）
卡特兰数的应用非常有规律，如果你发现某种方案可以转化为 “在任意时刻，A操作次数 $\ge$ B操作次数”，那么它几乎一定是卡特兰数。
- 括号匹配：任意前缀中，左括号数量 $\ge$ 右括号数量。
- 入栈出栈：任意时刻，入栈次数 $\ge$ 出栈次数。
- 买票找零：$n$ 个人拿 5 元，$n$ 个人拿 10 元，任意时刻售票员手中 5 元纸币数 $\ge$ 需要找出去的次数。
- 二叉树计数：$n$ 个节点的二叉树形态。
- 逻辑：根节点占 1 个点，左子树占 $i$ 个点，右子树占 $n-1-i$ 个点。
- 公式：$f(n) = \sum f(i) \times f(n-1-i)$，正好符合卷积递推式。
- 阶梯矩形切割：将 $n$ 阶阶梯状矩形切割成 $n$ 个矩形的方案数。
- 凸多边形三角剖分：
- 逻辑：固定一条边，选一个顶点连成三角形，将多边形分成左右两部分。
4. 补充：C++ 代码实现（取模版）
在编程竞赛中，计算卡特兰数通常需要处理大数取模，利用公式 $C_n = \frac{(2n)!}{(n+1)!n!}$ 结合费马小定理求逆元：
#include <iostream>
using namespace std;
long long power(long long a, long long b, long long m) {
long long res = 1;
while (b > 0) {
if (b & 1) res = res * a % m;
a = a * a % m;
b >>= 1;
}
return res;
}
long long inv(long long n, long long m) {
return power(n, m - 2, m); // 费马小定理求逆元
}
long long Catalan(int n, int mod) {
if (n == 0) return 1;
// C(2n, n) / (n + 1)
long long up = 1, down = 1;
for (int i = 1; i <= n; i++) {
up = up * (2 * n - i + 1) % mod;
down = down * i % mod;
}
return up * inv(down, mod) % mod * inv(n + 1, mod) % mod;
}
总结
你的笔记中关于“非法方案映射”的描述是核心精华。建议你在复习时，把 “括号匹配”、“出栈序列”、“网格路径” 这三个模型强行绑定在一起，因为它们的本质都是：
在坐标轴上从 $(0,0)$ 走到 $(2n, 0)$，每步只能走 $(1,1)$ 或 $(1,-1)$，且路径永远不降到 $x$ 轴以下。
—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com
