卡特兰数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。n1 时只有“5 元、10 元”一种排法C_11n2 时合法排法是 (5,5,10,10) 和 (5,10,5,10)C_22n3 时是 5 种C_35。你可以拿张纸手动枚举一遍5 种不多不少这个手感比任何公式都管用。我当时理解这个模型花了点时间因为总想从“哪个人站哪儿”的角度去数结果越数越乱。换个角度把它当成“走格子”就好办多了从 (0,0) 出发每遇到一个 5 元顾客就往右走一格每遇到一个 10 元顾客就往上走一格最后一定要停在 (n, n)。而“前缀和恒不为负”这条约束等价于整条路径永远不跑到对角线 yx 的上方去。于是抽象的排队问题变成了一道肉眼可见的几何计数题——这个“翻译”动作是解决所有卡特兰类问题的通用钥匙。1.2 数列长相与那条卷积型递推先把前若干项写完整方便后面随时对照n012345678910C_n112514421324291430486216796它在 OEIS 里的编号是 A000108如果你想不起某个具体值直接去 OEIS 搜前几项 1, 1, 2, 5, 14 是最快的辨认方式。卡特兰数最好用的递推式是这一条$$C_0 1,\qquad C_{n} \sum_{i0}^{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/(n1)递推式虽然漂亮但这只是 O(n²) 的算法骨架真正让人一眼记住的是通项$$C_n \frac{1}{n1}\binom{2n}{n} \binom{2n}{n} - \binom{2n}{n1}$$这两个形式完全等价但在写代码的时候我更推荐用后面那个减法形式原因后面第 4 节会详细说——减法形式里没有除法遇到模运算时能省掉一堆逆元的麻烦。那么多出来的 1/(n1) 到底是从哪冒出来的最直观的解释来自“循环引理”Dvoretzky–Motzkin cycle lemma考虑长度为 2n1 的序列其中含 n1 个 1、n 个 -1。把这条序列首尾相接放在一个环上对它做 2n1 种循环移位会有且仅有 1 种移位满足“所有前缀和恒为正”。也就是说环上等价类里真正“合法”的比例恰好是 1/(2n1)。把所有序列总数乘以这个比例$$\frac{1}{2n1}\binom{2n1}{n} \frac{(2n)!}{n!(n1)!} \frac{1}{n1}\binom{2n}{n}$$那个 1/(n1) 就是“环上的对称性”在整数世界里的投影。这个解释不一定能让所有人都满意但它比纯代数变形更有画面感我自己是靠这个想通的。1.4 增长速度为什么 n 一过 20 就爆炸卡特兰数的渐近展开是$$C_n \sim \frac{4^n}{n^{3/2}\sqrt{\pi}}$$翻译成人话就是每增加 1数值大约翻 4 倍再略微被 n^{1.5} 拖一点后腿。精确的相邻比值为$$\frac{C_{n1}}{C_n} \frac{2(2n1)}{n2}$$代进去看n0 时比值是 1n1 时是 2n5 时是 22/7 ≈ 3.143n100 时是 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 problemA 得 p 票、B 得 q 票且 p q要求计票过程中 A 始终严格领先于 B方案数是 (p-q)/(pq) × C(pq, p)。这个公式是卡特兰数的自然推广考试里偶尔会以“变体”的身份出现如果只会 C_n 的公式就容易卡壳。这一类问题的通用招式把两类操作映射成两个方向的步把约束翻译成“路径不越界”然后套用第 3 节的反射原理。2.2 树形结构半数卡特兰题都藏在这里n 个结点的不同二叉树形态数答案是 C_n。这里的“不同”指的是结构不同结点不编号且左右子树有区分。n 个叶子的满二叉树每个内部结点恰有两个孩子答案是 C_{n-1}。注意这个下标这是最常见的错位陷阱我在第 5 节会专门展开。n1 个因数连乘的加括号方式答案是 C_n。比如 a×b×c 有三种加括号方式(ab)c、a(bc)等等其实是两种对应 C_22。这个模型和二叉树是同一件事的两面每一种加括号方式唯一对应一棵满二叉树。有序森林 / 有序树的计数n 个结点的有序树孩子有顺序数量也是 C_n 的一种变体具体形式取决于是否允许空结点实际做题时要仔细数一数 n2、n3 的小样例再套公式不要凭记忆硬上。这类问题的识别信号是“递归结构”一棵树砍掉根之后剩下的部分依然是树。只要题目描述的是一种可以递归拆解的结构几乎必然是卡特兰。2.3 几何与划分三角剖分和非交叉连线凸 (n2) 边形的三角剖分数答案是 C_n。n3 时是五边形它有 5 种三角剖分方式对应 C_35。这个可以画图验证是几何直觉最直观的一个模型。圆周上 2n 个点两两连线且连线互不相交答案是 C_n。这里的关键限定是“互不相交”——如果允许相交答案就变成双阶乘 (2n-1)!!也就是 1×3×5×…×(2n-1)那是完全不同的一串数。这两者的对比我在第 6 节还会再提一次因为它是区分卡特兰数和其他数列的经典分水岭。n 元集合的非交叉划分non-crossing partition答案是 C_n。把 n 个点按顺序摆在圆周上用弧线把它们分成若干组要求弧线两两不相交划分数就是 C_n。这个概念在自由概率论和随机矩阵里出现过平时刷题不太遇得到但面试里作为“你听说过什么有趣的计数问题”的谈资很好用。2.4 模型对照速查表把上面这些整理成一张表贴在显示器边上当参考模型描述答案关键约束n 对括号的合法匹配C_n任意前缀左括号不少于右括号1..n 入栈的出栈序列C_n栈不空才能出栈n 个结点的二叉树形态C_n左右子树有序n 个叶子的满二叉树C_{n-1}注意下标错位n1 个数的加括号方式C_n完全括号化凸 (n2) 边形三角剖分C_n对角线互不相交(0,0) 到 (n,n) 不越对角线的路径C_n只能向右、向上长度 2n 的 Dyck 路径C_n前缀和恒非负2n 个点圆周不相交配对C_n弦互不相交231-avoiding 排列C_n单栈可排序n 元集合非交叉划分C_n分块块内不交叉p 票对 q 票始终领先(p-q)/(pq)·C(pq,p)pq严格领先提示遇到具体题目时务必先手动枚举 n1、2、3 的小样例和 1、2、5 对齐之后再套公式。这一步只要三十秒但能拦住绝大多数下标错位。3. 两条推导路线反射原理与生成函数3.1 反射原理把越界的路径一一映射出去这是我最喜欢的推导方式因为它几乎不需要代数技巧全靠一个“镜像”动作。问题重述从 (0,0) 走到 (n,n)每步向右 (1,0) 或向上 (0,1)要求整条路径不跑到直线 yx 的上方。求路径数。第一步先算没有任何约束时的总数一共要走 2n 步其中选 n 步向右方案数是 C(2n, n)。第二步把“坏路径”减掉。所谓坏路径就是某个时刻跑到了 yx 上方也就是第一次触碰到直线 y x1的那些路径。第三步做镜像。对每条坏路径找到它第一次碰到 yx1 的那个点把从这个点到终点的那一段沿直线 yx1 做一个镜像翻转。翻转之后起点不变终点从 (n,n) 变成了 (n-1, n1)。反过来从 (0,0) 到 (n-1, n1) 的任意一条路径也必然穿过 yx1镜像回去就得到一条坏路径。这个一一对应关系是整段推导的灵魂坏路径的数量恰好等于从 (0,0) 走到 (n-1, n1) 的路径总数。而后者很容易算——总共需要走 n-1 步向右、n1 步向上合计 2n 步从中选 n-1 步向右方案数是 C(2n, n-1)。于是$$C_n \binom{2n}{n} - \binom{2n}{n-1}$$注意这里写成了 C(2n, n-1)和前面提到的 C(2n, n1) 是相等的因为 C(2n, n-1) C(2n, 2n-(n-1)) C(2n, n1)。两种写法都对取决于你对称的是起点还是终点。最后一步化简$$\binom{2n}{n} - \binom{2n}{n1} \binom{2n}{n}\left(1 - \frac{n}{n1}\right) \frac{1}{n1}\binom{2n}{n}$$推导完毕。整个过程只有一次“镜像”是真正需要想明白的其余全是组合数的运算法则。我建议你至少手推一遍因为面试里被问到“为什么是 C(2n,n)-C(2n,n1)”的时候能讲清反射映射的人比只会背公式的人可信度高出一个档次。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/(n1))·C(2n,n)。这条路的额外收获是你会顺便看清收敛半径是 1/4——这正好对应了前面“每项大约乘 4”的增长速度两者是同一件事的两种表述。3.3 数值验证十行代码跑一遍心里就踏实了公式这东西光看推导还不够动手跑一遍才安心。下面这段 Python 同时实现了记忆化递归、动态规划和通项公式让三者互相校验from functools import lru_cache from math import comb lru_cache(maxsizeNone) 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 三种实现方式的横向对比方式时间复杂度空间复杂度适用场景备注记忆化递归O(n²)O(n²) 调用栈n ≤ 25 的精确值写起来最快递归深度是 n不会爆栈动态规划O(n²)O(n) 或 O(n²)n ≤ 5000 的精确值递推方向清晰方便加取模通项公式O(n) 预处理 O(1) 查询O(n) 存阶乘表单点求解、模数为质数需要处理逆元选型逻辑其实很简单小规模求精确值就用记忆化递归习惯什么写什么中等规模求精确值就用 DP注意用 Python 或者大整数库大规模求模值就上通项公式加阶乘表一次预处理多组查询最划算。如果题目是“多组询问每组给一个 n”那一定要预处理好阶乘表和逆阶乘表做到 O(1) 回答否则 O(n²) 的 DP 会被卡死。4.2 取模场景下的三个坑坑一除法必须换成逆元。C_n C(2n,n)/(n1) 里的那个除以 n1在整数域是精确除法但在模运算下必须换成乘以 (n1) 的模逆元。前提是模数 p 为质数且 n1 p此时 n1 与 p 互质逆元存在可以用费马小定理 a^(p-2) mod p 快速求。坑二模数不是质数时不能乱用费马小定理。如果题目给的模数是 10^97 这种常见质数那没问题但如果给的是 998244353 也行也是质数可万一给的是 10^9 这种合数就只能改用扩展欧几里得求逆元而且还得保证 gcd(n1, mod) 1。最省事的做法是直接用减法形式 C_n C(2n,n) - C(2n,n1)绕开这个除法虽然组合数本身还是要除法但至少不用纠结额外的因子。坑三n 接近或超过模数时阶乘会变成 0。因为 n! 在模意义下会包含因子 p一旦 n ≥ p阶乘表就全被污染了。这种情况必须上 Lucas 定理或者干脆用精确大整数算完再取模。另外还有个纯粹的工程细节long long的乘法。两个小于 1e97 的数相乘最大约 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, pMOD): # 适用条件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)) % pC 版本把组合数表封装成结构体方便多组查询时复用#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 { vectorlong 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 { // 减法形式避免显式除以 (n1) 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}。判断方法很土但有效手动构造 n1 的实例。1 个叶子的满二叉树只有 1 棵C_01所以答案应该是 C_{n-1}如果套成 C_nn1 时得到 C_11恰好也等于 1看不出问题但换成 n3正确答案是 C_22两个叶子分别挂在根的两个孩子上或者三层链式结构而 C_35差了 2.5 倍一眼就能发现。所以验证下标一定要用 n3 及以上的样例n1 和 n2 经常因为对称性而巧合相等。错法二约束方向搞反。“不越过对角线”和“不接触对角线”是两回事。前者允许路径贴着对角线走答案是 C_n后者要求中途不能碰到答案是 C_{n-1}。这两个在 n 小的时候差得不明显n 一大就差了好几倍。诀窍是看题目里允许不允许“零余额”的状态出现。找零问题里零钱刚好用光是可以的因为下一笔是 5 元收入所以用 C_n如果题目说“售票员在任何时刻都必须有找零能力包括刚刚找完那一刻”那就要排除贴线情况。错法三多算一倍。这种情况通常发生在对称性处理上。比如“圆周上 2n 个点配对”如果题目不区分连线的方向那么正反两种连法算不算同一种会直接影响结果差一倍。还有一个更隐蔽的例子如果题目里两类元素本身是可区分的比如“男生和女生”而不是笼统的“A 类和 B 类”那么在枚举时你是按位置数的一般不需要额外乘 2但如果题目问的是“分成两组”那就要小心组合数里已经包含了顺序信息。遇到答案差一倍先怀疑是不是自己多乘了 2 或者漏了对称性。5.2 溢出与性能什么时候必须放弃暴力很多人卡在“我的代码小数据都对大数据就 WA”。这往往不是算法错了而是中间结果溢出。一个具体的判断流程n ≤ 20C_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 且带多组询问必须预处