企业官网建设流程全解析

卡特兰数（Catalan number）在组合数学里属于出场率极高的那类数列，我第一次被它绊倒是刷一道“括号匹配计数”题的时候——当时随手写了个组合数除法，交上去连挂三发，回头对着答案楞了半天才发现自己漏掉了一条“任何前缀都不能失衡”的隐式约束。后来题目刷得多了才慢慢摸出规律：凡是带“配对”“嵌套”“不越界”“剖分”味道的计数问题，背后十有八九站着这串数列 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862。它既是组合数学里被研究得最透的序列之一，也是算法面试和竞赛里最容易被拿来当“分水岭”的知识点：会推导的人一眼看穿，不会推导的人就只能对着样例猜规律。这篇文章我打算按自己平时做笔记的路子写——先把“它到底在数什么”讲透，再把推导的两条主线（反射原理和生成函数）捋一遍，然后落到代码实现、取模细节和踩坑实录，最后聊怎么在考场上三秒钟判断一道题是不是卡特兰数。刷题党、准备面试的、写解析器或表达式求值模块的工程师，以及单纯对组合计数好奇的人，都能从里面拿走点东西。

1. 卡特兰数到底在数什么：先从一道找零问题说起

1.1 一个具体到能背下来的场景

假设电影院门口排队买票，票价 5 元，窗口一开始没有备用零钱。队伍里有 n 个人手里只有一张 5 元，另外 n 个人手里只有一张 10 元。问：这 2n 个人有多少种排列顺序，能让售票员从头到尾都不会出现找不开钱的尴尬？

这就是最经典的卡特兰数模型。想明白它的关键是一句废话式的观察：在任何时刻，已经付过钱的 5 元顾客数量，必须不少于已经付过钱的 10 元顾客数量，否则找零的零钱池就空了。把“5 元顾客”记成 +1，“10 元顾客”记成 -1，问题就变成了：长度为 2n、由 n 个 +1 和 n 个 -1 组成的序列里，有多少个序列的所有前缀和恒不为负？

答案就是第 n 个卡特兰数 C_n。n=1 时只有“5 元、10 元”一种排法，C_1=1；n=2 时合法排法是 (5,5,10,10) 和 (5,10,5,10)，C_2=2；n=3 时是 5 种，C_3=5。你可以拿张纸手动枚举一遍，5 种不多不少，这个手感比任何公式都管用。

我当时理解这个模型花了点时间，因为总想从“哪个人站哪儿”的角度去数，结果越数越乱。换个角度，把它当成“走格子”就好办多了：从 (0,0) 出发，每遇到一个 5 元顾客就往右走一格，每遇到一个 10 元顾客就往上走一格，最后一定要停在 (n, n)。而“前缀和恒不为负”这条约束，等价于整条路径永远不跑到对角线 y=x 的上方去。于是抽象的排队问题，变成了一道肉眼可见的几何计数题——这个“翻译”动作，是解决所有卡特兰类问题的通用钥匙。

1.2 数列长相与那条卷积型递推

先把前若干项写完整，方便后面随时对照：

它在 OEIS 里的编号是 A000108，如果你想不起某个具体值，直接去 OEIS 搜前几项 1, 1, 2, 5, 14 是最快的辨认方式。

卡特兰数最好用的递推式是这一条：

$$C_0 = 1,\qquad C_{n} = \sum_{i=0}^{n-1} C_i \cdot C_{n-1-i} \quad (n \ge 1)$$

乍一看有点唬人，但它的直觉非常朴素：任何一个合法的“平衡结构”，都必然存在一个唯一的“分解点”，在这一点上结构被切成左右两半，而这两半各自又是一个同类型的合法结构，两边的规模加起来正好是 n-1。

拿括号匹配举例。一个合法的括号串一定以左括号开头、以右括号结尾，而且一定会存在一个“第一次回到平衡”的位置：从这个位置的左括号开始计数，前缀和首次归零。这个左括号和它配对的那个右括号，把整个串切成“里面”和“后面”两段，里面是一个规模 i 的合法串，后面是一个规模 n-1-i 的合法串。i 从 0 到 n-1 遍历，就得到了上面那条递推。

这套“找一个唯一的切分点，把问题拆成两个同类子问题”的思路，是识别卡特兰数的第一信号。反过来说，如果你面对的问题不能这样一刀切开，那它大概率就不是卡特兰数。

1.3 通项公式和那个碍眼的 1/(n+1)

递推式虽然漂亮但这只是 O(n²) 的算法骨架，真正让人一眼记住的是通项：

$$C_n = \frac{1}{n+1}\binom{2n}{n} = \binom{2n}{n} - \binom{2n}{n+1}$$

这两个形式完全等价，但在写代码的时候我更推荐用后面那个减法形式，原因后面第 4 节会详细说——减法形式里没有除法，遇到模运算时能省掉一堆逆元的麻烦。

那么多出来的 1/(n+1) 到底是从哪冒出来的？最直观的解释来自“循环引理”（Dvoretzky–Motzkin cycle lemma）：考虑长度为 2n+1 的序列，其中含 n+1 个 +1、n 个 -1。把这条序列首尾相接放在一个环上，对它做 2n+1 种循环移位，会有且仅有 1 种移位满足“所有前缀和恒为正”。也就是说，环上等价类里真正“合法”的比例恰好是 1/(2n+1)。把所有序列总数乘以这个比例：

$$\frac{1}{2n+1}\binom{2n+1}{n} = \frac{(2n)!}{n!(n+1)!} = \frac{1}{n+1}\binom{2n}{n}$$

那个 1/(n+1) 就是“环上的对称性”在整数世界里的投影。这个解释不一定能让所有人都满意，但它比纯代数变形更有画面感，我自己是靠这个想通的。

1.4 增长速度：为什么 n 一过 20 就爆炸

卡特兰数的渐近展开是：

$$C_n \sim \frac{4^n}{n^{3/2}\sqrt{\pi}}$$

翻译成人话就是：每增加 1，数值大约翻 4 倍，再略微被 n^{1.5} 拖一点后腿。精确的相邻比值为：

$$\frac{C_{n+1}}{C_n} = \frac{2(2n+1)}{n+2}$$

代进去看：n=0 时比值是 1，n=1 时是 2，n=5 时是 22/7 ≈ 3.143，n=100 时是 2×201/102 ≈ 3.941，随着 n 增大迅速逼近 4。这个“比值趋近 4”的性质在考场上特别有用——当你算出题目前几项是 1, 2, 5, 14, 42，相邻比值 2、2.5、2.8、3.0，一路往 4 靠，那基本可以确认是卡特兰数。

规模上要有个概念：C_20 = 6564120420，已经超过 32 位整数上限；C_36 超过 64 位有符号整数上限；C_100 大约是 8.9×10^56，位数接近 57 位；C_10000 则有约 6019 位十进制数字，用 Python 的 bigint 算出来是一瞬间的事，但用 C++ 的双精度浮点去碰它纯属自找没趣。这也是为什么实际题目里几乎都会给你一个模数让你取模。

2. 十二个藏得最深的卡特兰模型与对照表

2.1 括号、出栈与一切“前缀守恒”问题

这一族问题的共同点是：题目里一定藏着一句“任何时刻 A 的数量不能少于 B 的数量”之类的约束。

括号匹配：n 对括号能组成的合法序列数为 C_n。这是教科书版本，也是最好记的版本。

出栈序列：1 到 n 依次入栈，允许任意时刻出栈，问可能的出栈序列有多少种。答案是 C_n。这个模型特别值得琢磨，因为它和括号问题其实是同一个东西——把一次入栈记成左括号、一次出栈记成右括号，整个操作序列就是一个长度为 2n 的合法括号串，出入栈的合法性天然保证了“已入栈数量不少于已出栈数量”。我第一次意识到这个等价关系时愣了几秒，因为它把两个看起来毫无关系的领域缝在了一起。

栈排序可行排列：n 个元素的排列中，能通过一个栈排序变成升序的排列数为 C_n。更学术的说法是“231-avoiding 排列”的数量。这个模型有点反直觉，因为 n! 看起来那么大一坨，真正“能被一个栈救回来”的排列居然只有指数级的一小撮。

找零问题：前面讲过的那道，答案 C_n。

投票问题（ballot problem）：A 得 p 票、B 得 q 票且 p > q，要求计票过程中 A 始终严格领先于 B，方案数是 (p-q)/(p+q) × C(p+q, p)。这个公式是卡特兰数的自然推广，考试里偶尔会以“变体”的身份出现，如果只会 C_n 的公式就容易卡壳。

这一类问题的通用招式：把两类操作映射成两个方向的步，把约束翻译成“路径不越界”，然后套用第 3 节的反射原理。

2.2 树形结构：半数卡特兰题都藏在这里

n 个结点的不同二叉树形态数：答案是 C_n。这里的“不同”指的是结构不同，结点不编号，且左右子树有区分。

n 个叶子的满二叉树（每个内部结点恰有两个孩子）：答案是 C_{n-1}。注意这个下标！这是最常见的错位陷阱，我在第 5 节会专门展开。

n+1 个因数连乘的加括号方式：答案是 C_n。比如 a×b×c 有三种加括号方式：(ab)c、a(bc)，等等，其实是两种，对应 C_2=2。这个模型和二叉树是同一件事的两面：每一种加括号方式唯一对应一棵满二叉树。

有序森林 / 有序树的计数：n 个结点的有序树（孩子有顺序）数量也是 C_n 的一种变体，具体形式取决于是否允许空结点，实际做题时要仔细数一数 n=2、n=3 的小样例再套公式，不要凭记忆硬上。

这类问题的识别信号是“递归结构”：一棵树砍掉根之后，剩下的部分依然是树。只要题目描述的是一种可以递归拆解的结构，几乎必然是卡特兰。

2.3 几何与划分：三角剖分和非交叉连线

凸 (n+2) 边形的三角剖分数：答案是 C_n。n=3 时是五边形，它有 5 种三角剖分方式，对应 C_3=5。这个可以画图验证，是几何直觉最直观的一个模型。

圆周上 2n 个点两两连线且连线互不相交：答案是 C_n。这里的关键限定是“互不相交”——如果允许相交，答案就变成双阶乘 (2n-1)!!，也就是 1×3×5×…×(2n-1)，那是完全不同的一串数。这两者的对比我在第 6 节还会再提一次，因为它是区分卡特兰数和其他数列的经典分水岭。

n 元集合的非交叉划分（non-crossing partition）：答案是 C_n。把 n 个点按顺序摆在圆周上，用弧线把它们分成若干组，要求弧线两两不相交，划分数就是 C_n。这个概念在自由概率论和随机矩阵里出现过，平时刷题不太遇得到，但面试里作为“你听说过什么有趣的计数问题”的谈资很好用。

2.4 模型对照速查表

把上面这些整理成一张表，贴在显示器边上当参考：

提示：遇到具体题目时，务必先手动枚举 n=1、2、3 的小样例，和 1、2、5 对齐之后再套公式。这一步只要三十秒，但能拦住绝大多数下标错位。

3. 两条推导路线：反射原理与生成函数

3.1 反射原理：把越界的路径一一映射出去

这是我最喜欢的推导方式，因为它几乎不需要代数技巧，全靠一个“镜像”动作。

问题重述：从 (0,0) 走到 (n,n)，每步向右 (1,0) 或向上 (0,1)，要求整条路径不跑到直线 y=x 的上方。求路径数。

第一步，先算没有任何约束时的总数：一共要走 2n 步，其中选 n 步向右，方案数是 C(2n, n)。

第二步，把“坏路径”减掉。所谓坏路径，就是某个时刻跑到了 y=x 上方，也就是第一次触碰到直线 y = x+1的那些路径。

第三步，做镜像。对每条坏路径，找到它第一次碰到 y=x+1 的那个点，把从这个点到终点的那一段沿直线 y=x+1 做一个镜像翻转。翻转之后，起点不变，终点从 (n,n) 变成了 (n-1, n+1)。反过来，从 (0,0) 到 (n-1, n+1) 的任意一条路径，也必然穿过 y=x+1，镜像回去就得到一条坏路径。

这个一一对应关系是整段推导的灵魂：坏路径的数量，恰好等于从 (0,0) 走到 (n-1, n+1) 的路径总数。而后者很容易算——总共需要走 n-1 步向右、n+1 步向上，合计 2n 步，从中选 n-1 步向右，方案数是 C(2n, n-1)。

于是：

$$C_n = \binom{2n}{n} - \binom{2n}{n-1}$$

注意这里写成了 C(2n, n-1)，和前面提到的 C(2n, n+1) 是相等的（因为 C(2n, n-1) = C(2n, 2n-(n-1)) = C(2n, n+1)）。两种写法都对，取决于你对称的是起点还是终点。

最后一步化简：

$$\binom{2n}{n} - \binom{2n}{n+1} = \binom{2n}{n}\left(1 - \frac{n}{n+1}\right) = \frac{1}{n+1}\binom{2n}{n}$$

推导完毕。整个过程只有一次“镜像”是真正需要想明白的，其余全是组合数的运算法则。我建议你至少手推一遍，因为面试里被问到“为什么是 C(2n,n)-C(2n,n+1)”的时候，能讲清反射映射的人，比只会背公式的人可信度高出一个档次。

3.2 生成函数：解一个二次方程

第二条路更“代数”，但在研究卡特兰数的性质时威力更大。设

$$C(x) = \sum_{n \ge 0} C_n x^n$$

把递推式 C_n = Σ C_i·C_{n-1-i} 代进去，你会发现它描述的正是两个 C(x) 相乘时卷积项的形式，只是整体多乘了一个 x。于是：

$$C(x) = 1 + x \cdot C(x)^2$$

这个二次方程有两根：

$$C(x) = \frac{1 \pm \sqrt{1-4x}}{2x}$$

取哪个？用 x→0 的极限判断：C(0) 应该等于 C_0 = 1，所以必须取减号那一支：

$$C(x) = \frac{1 - \sqrt{1-4x}}{2x}$$

然后对 (1-4x)^{1/2} 做二项式展开，逐项提取系数，就能重新得到 C_n = (1/(n+1))·C(2n,n)。这条路的额外收获是，你会顺便看清收敛半径是 1/4——这正好对应了前面“每项大约乘 4”的增长速度，两者是同一件事的两种表述。

3.3 数值验证：十行代码跑一遍心里就踏实了

公式这东西，光看推导还不够，动手跑一遍才安心。下面这段 Python 同时实现了记忆化递归、动态规划和通项公式，让三者互相校验：

from functools import lru_cache from math import comb @lru_cache(maxsize=None) def catalan_rec(n): if n <= 1: return 1 return sum(catalan_rec(i) * catalan_rec(n - 1 - i) for i in range(n)) def catalan_dp(n): c = [0] * (n + 1) c[0] = 1 for i in range(1, n + 1): c[i] = sum(c[j] * c[i - 1 - j] for j in range(i)) return c[n] def catalan_formula(n): return comb(2 * n, n) - comb(2 * n, n + 1) for n in range(12): assert catalan_rec(n) == catalan_dp(n) == catalan_formula(n), n print([catalan_formula(n) for n in range(12)]) # [1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786]

三种写法结果完全一致，说明推导没问题。顺带一提，math.comb需要 Python 3.8 及以上版本，老版本可以用阶乘除法手写。

4. 代码实现：从 O(n²) 递推到 O(n) 公式

4.1 三种实现方式的横向对比

选型逻辑其实很简单：小规模求精确值就用记忆化递归，习惯什么写什么；中等规模求精确值就用 DP，注意用 Python 或者大整数库；大规模求模值就上通项公式加阶乘表，一次预处理多组查询最划算。

如果题目是“多组询问，每组给一个 n”，那一定要预处理好阶乘表和逆阶乘表，做到 O(1) 回答，否则 O(n²) 的 DP 会被卡死。

4.2 取模场景下的三个坑

坑一：除法必须换成逆元。C_n = C(2n,n)/(n+1) 里的那个除以 n+1，在整数域是精确除法，但在模运算下必须换成乘以 (n+1) 的模逆元。前提是模数 p 为质数且 n+1 < p，此时 n+1 与 p 互质，逆元存在，可以用费马小定理 a^(p-2) mod p 快速求。

坑二：模数不是质数时不能乱用费马小定理。如果题目给的模数是 10^9+7 这种常见质数，那没问题；但如果给的是 998244353 也行（也是质数），可万一给的是 10^9 这种合数，就只能改用扩展欧几里得求逆元，而且还得保证 gcd(n+1, mod) = 1。最省事的做法是直接用减法形式 C_n = C(2n,n) - C(2n,n+1)，绕开这个除法，虽然组合数本身还是要除法，但至少不用纠结额外的因子。

坑三：n 接近或超过模数时阶乘会变成 0。因为 n! 在模意义下会包含因子 p，一旦 n ≥ p，阶乘表就全被污染了。这种情况必须上 Lucas 定理，或者干脆用精确大整数算完再取模。

另外还有个纯粹的工程细节：long long的乘法。两个小于 1e9+7 的数相乘最大约 1e18，刚好在 64 位有符号整数上限（约 9.22e18）之内，安全；但如果你写成了三个数连乘再取模，比如a * b % MOD * c % MOD这种写法其实是对的，而a * b * c % MOD就会溢出。这个坑我在比赛里踩过不止一次，调试半天发现是溢出而不是逻辑问题。

4.3 两个可直接抄的模板

Python 版本，适合 n ≤ 10^6 且需要精确值或者大素数模数的场合：

MOD = 10**9 + 7 def catalan_mod(n, p=MOD): # 适用条件：p 为质数，且 2n < p fac = [1] * (2 * n + 1) for i in range(1, 2 * n + 1): fac[i] = fac[i - 1] * i % p inv_fac = [1] * (2 * n + 1) inv_fac[2 * n] = pow(fac[2 * n], p - 2, p) for i in range(2 * n, 0, -1): inv_fac[i - 1] = inv_fac[i] * i % p def C(a, b): if b < 0 or b > a: return 0 return fac[a] * inv_fac[b] % p * inv_fac[a - b] % p # 减法形式，即使 p 不是质数也能少一个逆元 return (C(2 * n, n) - C(2 * n, n + 1)) % p

C++ 版本，把组合数表封装成结构体，方便多组查询时复用：

#include <bits/stdc++.h> using namespace std; const long long MOD = 1000000007LL; long long modpow(long long a, long long e, long long mod) { long long r = 1; a %= mod; while (e) { if (e & 1) r = r * a % mod; a = a * a % mod; e >>= 1; } return r; } struct CombTable { vector<long long> fac, inv; long long mod; CombTable(int N, long long m = MOD) : mod(m) { fac.assign(N + 1, 1); inv.assign(N + 1, 1); for (int i = 1; i <= N; ++i) fac[i] = fac[i - 1] * i % mod; inv[N] = modpow(fac[N], mod - 2, mod); for (int i = N; i >= 1; --i) inv[i - 1] = inv[i] * i % mod; } long long binom(int n, int k) const { if (k < 0 || k > n) return 0; return fac[n] * inv[k] % mod * inv[n - k] % mod; } long long catalan(int n) const { // 减法形式，避免显式除以 (n+1) return (binom(2 * n, n) - binom(2 * n, n + 1) + mod) % mod; } }; int main() { CombTable ct(200000); for (int n = 0; n <= 10; ++n) cout << ct.catalan(n) << " "; cout << "\n"; // 输出 1 1 2 5 14 42 132 429 1430 4862 16796 }

注意++i和i++在这类循环里性能差异现代编译器基本抹平了，别在那上面纠结；真正影响性能的是把mod存在结构体里，避免每次调用都从全局读，编译器优化后差异可以忽略，但代码可读性会好一点。

如果连除法形式都不想用（比如模数是任意合数），可以退化成 Pascal 三角逐行递推求组合数，完全避开逆元，代价是 O(n²) 的时间和空间。这个方案在 n ≤ 3000 且模数诡异的情况下反而更稳妥。

5. 常见问题与排查实录

5.1 差一倍、差一个、多算一倍：三种典型错法

错法一：下标错位。最常见的表现形式是“n 个叶子的满二叉树”被写成 C_n 而不是 C_{n-1}。判断方法很土但有效：手动构造 n=1 的实例。1 个叶子的满二叉树只有 1 棵，C_0=1，所以答案应该是 C_{n-1}；如果套成 C_n，n=1 时得到 C_1=1，恰好也等于 1，看不出问题；但换成 n=3，正确答案是 C_2=2（两个叶子分别挂在根的两个孩子上，或者三层链式结构），而 C_3=5，差了 2.5 倍，一眼就能发现。所以验证下标一定要用 n=3 及以上的样例，n=1 和 n=2 经常因为对称性而巧合相等。

错法二：约束方向搞反。“不越过对角线”和“不接触对角线”是两回事。前者允许路径贴着对角线走，答案是 C_n；后者要求中途不能碰到，答案是 C_{n-1}。这两个在 n 小的时候差得不明显，n 一大就差了好几倍。诀窍是：看题目里允许不允许“零余额”的状态出现。找零问题里，零钱刚好用光是可以的（因为下一笔是 5 元收入），所以用 C_n；如果题目说“售票员在任何时刻都必须有找零能力，包括刚刚找完那一刻”，那就要排除贴线情况。

错法三：多算一倍。这种情况通常发生在对称性处理上。比如“圆周上 2n 个点配对”，如果题目不区分连线的方向，那么正反两种连法算不算同一种，会直接影响结果差一倍。还有一个更隐蔽的例子：如果题目里两类元素本身是可区分的（比如“男生和女生”而不是笼统的“A 类和 B 类”），那么在枚举时你是按位置数的，一般不需要额外乘 2；但如果题目问的是“分成两组”，那就要小心组合数里已经包含了顺序信息。遇到答案差一倍，先怀疑是不是自己多乘了 2 或者漏了对称性。

5.2 溢出与性能：什么时候必须放弃暴力

很多人卡在“我的代码小数据都对，大数据就 WA”。这往往不是算法错了，而是中间结果溢出。

一个具体的判断流程：

• n ≤ 20：C_n 还在 64 位整数范围内（C_20 ≈ 6.56×10⁹），随便算，甚至可以用浮点验证一下数量级。
• 20 < n ≤ 36：需要 128 位或者大整数库。C_36 ≈ 1.2×10^19，已经超过 9.22×10^18。
• n > 36：必须取模，或者用 Python 的 bigint / Java 的 BigInteger。
• n > 10^6 且带多组询问：必须预处