卡特兰数这个名词第一次听到的人多半是在刷算法题的时候——一道“n 对括号有多少种合法的匹配方式”题解里冷不丁冒出一个C(2n, n) / (n1)然后告诉你这叫卡特兰数。第二次、第三次再遇到它可能是在二叉树计数、出栈序列、凸多边形三角剖分甚至是在组合数学的课堂上。它属于那种“名字不起眼、出镜率却高得离谱”的数列前几项是 1、1、2、5、14、42、132、429……看着人畜无害稍微大一点就猛地窜到几百万、几十亿n 到 30 就能顶到 3.8×10^15n 到 36 直接溢出 64 位整数。很多人在这一步栽跟头公式背得滚瓜烂熟代码一跑就溢出或者取模取错。这篇东西就是把我这些年处理卡特兰数相关问题的经验整理出来从它到底怎么来的、为什么一个数列能对应那么多种问题到四种主流计算方法的选型、Python 和 C 双版本实现、取模与大数的坑全部摊开讲。适合正在准备算法面试的人、需要写组合计数模块的开发者也适合理科老师或者对组合数学感兴趣的爱好者对照着看。读完你至少能做到两件事看到一类计数问题能主动反应过来“这可能是卡特兰数”以及遇到具体约束条件时知道该用哪种算法、哪里最容易翻车。1. 卡特兰数到底是什么从一个括号匹配问题说起1.1 一个让人抓头的计数场景先别急着上公式我们把问题摊平了看。假设你手里有 n 对圆括号也就是 n 个左括号和 n 个右括号问把它们排成一排且满足“任意前缀中左括号数量不小于右括号数量”的排列有多少种。n1 只有()一种n2 有(())和()()两种n3 有五种分别是((()))、(()())、(())()、()(())、()()()。这串数字 1、2、5、14、42 就是卡特兰数从 C_1 开始的部分。这个“任意前缀合法”的约束条件非常关键它等价于括号序列一直是“平衡”的不会在某个位置突然冒出一个无处配对的右括号。你在纸上随手画一下就会明白n 稍微大一点合法方案的增长速度远没有总排列数C(2n, n)那么夸张——绝大多数排列都在某个前缀处踩了红线被判定为非法。卡特兰数的魅力就在这个地方一个看起来只属于括号匹配的约束能原封不动地搬到十几个完全不同的问题上。n 个节点的二叉树形态数、n 个元素的出栈序列数、从 (0,0) 走到 (n,n) 且不越过对角线的路径数、凸 n2 边形的三角剖分数……答案全是同一个数列。这不是巧合后面我会专门解释这个“为什么”。1.2 两种定义递推式和通项公式卡特兰数通常有两种写法你得都记住因为不同场景下用哪个差很多。第一种是递推定义。规定 C_0 1然后对于 n ≥ 1 有C_n Σ (i 从 0 到 n-1) C_i * C_{n-1-i}也就是C_n C_0*C_{n-1} C_1*C_{n-2} ... C_{n-1}*C_0。这个式子看着像卷积它的组合含义很直观把问题从某个位置劈成两半左边和右边各自独立计数然后乘起来再求和所有可能的劈法。括号匹配里那个“劈”的位置就是第一次左右括号数量重新相等的点。第二种是通项公式C_n C(2n, n) / (n1) (2n)! / (n! * (n1)!)这两个表达式完全等价因为C(2n, n) (2n)!/(n!n!)再除以 (n1) 就得到第二个写法。通项公式的好处是 O(1) 就能查一个值前提是组合数能快速算坏处是涉及大数除法取模场景下要小心处理。注意通项里除的是 (n1)不是 (2n1)也不是 (2n-1)。我见过太多人凭印象写错分母n 小的时候前几项碰巧对得上一到大数就崩排查半天。1.3 增长速度有多吓人给个直观的表你会对“为什么必须上大数”有个清醒认识nC_n量级01111154210^1101679610^415969484510^620656412042010^925486194640145210^1230381498650209230410^1535311628549490730126210^183611959798385860453492约 1.2×10^19爆 signed 64 位signed long long的上限大约是 9.22×10^18也就是说 n36 就已经装不下了。你在 C 里用long long一路乘下去大概在 n36 前后就会得到负数——典型的溢出信号。这时候要么换 Python要么老老实实上大数要么题目本身就要求取模三选一。2. 为什么卡特兰数能“一数多用”背后的组合结构拆解2.1 核心密码找到那个“第一次回到起点”的位置前面埋的伏笔现在揭。为什么括号匹配、二叉树、出栈序列这些问题答案都一样因为它们共享同一个结构一个序列的构造过程可以反复拆分成“一段完整的小结构 剩下的部分”。拿括号匹配举例。任何合法序列从左往右数第一次左右括号数量重新相等的那个位置是唯一的。这个位置之前必然是一个(开头、)结尾的合法块这个块内部又是一个合法的括号序列。于是整个序列被劈成( A ) B的形式其中 A 和 B 都是合法的括号序列。A 的长度是 2iB 的长度是 2(n-1-i)i 可以取 0 到 n-1。所有方案数就是Σ C_i * C_{n-1-i}。这就是递推式的来源。你把这个“劈法”的逻辑套到别的场景上试试出栈序列第一个出栈的元素把它前面的入栈和后面的操作分开第一次入栈和出栈数量相等的位置就是分界点。二叉树计数根节点固定占一个左子树和右子树的形态数相乘遍历根节点标号的所有可能分配得到同样的递推。凸多边形三角剖分固定一条边它对应某个三角形三角形把多边形劈成两个更小的多边形。所有这些问题共享的抽象模型数学上叫Dyck 路径只用右上和右下两种步伐、始终不落到对角线以下的路径。卡特兰数就是长度为 2n 的 Dyck 路径的条数。这也是为什么它又被叫做“第二类斯特林数之外的组合计数万金油”。2.2 常见应用场景对照表我整理了一份自己在面试和刷题时高频遇到的对应关系你可以直接背下来当反射弧用问题描述对应卡特兰数n 对括号的合法匹配数C_nn 个节点的不同二叉搜索树数目C_nn 个节点的不同二叉树形态数C_nn 个元素依次入栈可能的出栈序列数C_n凸 n2 边形的三角剖分方案数C_n从 (0,0) 到 (n,n) 且不越过对角线 yx 的路径数C_nn 个数相乘加括号的不同方案数C_{n-1}2n 个人围成圈两两连线且不交叉的配对数C_nn 个左括号 n 个右括号形成的“栈排序”合法序列数C_n看到“合法匹配”“不交叉”“不越过”“两两配对且互不干扰”这类字眼脑子里就该亮灯。尤其是“入栈出栈”和“二叉树形态”这两个出题人特别爱用。2.3 它和斐波那契数的本质区别很多人第一次学卡特兰数会把它和斐波那契混因为都是递推出来的数列。区别在于递推式里的结构斐波那契F_n F_{n-1} F_{n-2}是线性的把规模减一或减二。卡特兰C_n Σ C_i * C_{n-i-1}是卷积型的把规模拆成两段再相乘。这个差异意味着卡特兰数的增长是指数级但底数更大的渐进增长约为4^n / (n^{1.5} * √π)而斐波那契是φ^nφ≈1.618。卡特兰数的底数接近 4所以它涨得飞快。你算一下 n30 时斐波那契才一百多万卡特兰数已经 3.8×10^15差了好几个数量级。这也是为什么卡特兰数相关的题目往往在 n35 附近就开始强制取模。3. 四种计算方法与选型从暴力递归到线性递推3.1 方法一直接套递推定义教学友好生产慎用最原始的写法就是照着递推式翻译def catalan_recursive(n): if n 1: return 1 total 0 for i in range(n): total catalan_recursive(i) * catalan_recursive(n - 1 - i) return total这个版本的时间复杂度是指数级的因为同一个子问题被反复计算。n20 左右你就会明显感觉到卡顿n30 基本跑不动。它的价值在于帮你理解递推结构适合在讲原理的时候用实际写题绝对不要这么干——除非你加记忆化。加了记忆化之后复杂度降到 O(n²)写法简单、结果精确、天然支持大数Python 里是中等规模n ≤ 10^4且不需要取模时的稳妥选择def catalan_memo(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]心得递推版本的循环边界特别容易写错。内层求和是从 j0 到 i-1对应的是C_j * C_{i-1-j}如果你写成C_j * C_{i-j}就错了会算成完全不同的数列。3.2 方法二组合数通项公式适合单次快速求解如果你只需要某一个n 的卡特兰数而且 n 不大或者能用 Python直接上通项from math import comb def catalan_formula(n): return comb(2 * n, n) // (n 1)math.comb在 Python 3.8 以后是内置的底层用高效算法算组合数配合 Python 的任意精度整数n 到几千都能秒出。注意用整除//而不是普通除法/因为结果本身是整数用浮点会有精度风险。这个方法的优点是单点查询极快缺点是如果你要一整个序列C_0..C_n每次单独调用就浪费了不如用后面的线性递推。3.3 方法三线性递推序列计算的首选卡特兰数有一个非常漂亮的相邻项递推关系C_{n1} C_n * (4n 2) / (n 2)推导也不难从通项出发C_{n1} / C_n [C(2n2, n1) / (n2)] / [C(2n, n) / (n1)]展开组合数化简后正好得到(4n2)/(n2)。这个式子的最大好处是从 C_0 1 出发一路乘除下去就能得到整个序列时间复杂度 O(n)而且每步的中间量都控制在合理范围。def catalan_linear(n): c [0] * (n 1) c[0] 1 for i in range(n): c[i 1] c[i] * (4 * i 2) // (i 2) return c验证一下i0 时1 * 2 // 2 1C_1i1 时1 * 6 // 3 2C_2i2 时2 * 10 // 4 5C_3完全正确。注意这里的整除能成立是因为C_n * (4n2)必然能被(n2)整除——这是数列的整数性质保证的不是巧合。提醒在 Python 里这个写法没问题因为有精确的任意精度整数。在 C 里直接用整数除法会丢精度必须改成乘逆元取模场景或大数非取模场景下面会讲。3.4 方法四取模 组合数预处理竞赛和工程的主力真正落到算法题和工程代码里绝大多数情况都要求取模常见模数是 1e97、1e99、998244353。这时候通项公式里的除法必须转成乘逆元。以C_n (2n)! / (n! (n1)!)为例取模后变成C_n mod p fact[2n] * invfact[n] % p * invfact[n1] % p其中invfact[i]是i!的模逆元。当 p 是素数且 n p 时用费马小定理inv(a) a^(p-2) mod p就能求。预先算好阶乘数组和逆阶乘数组之后每个卡特兰数都是 O(1) 查询这是多组查询场景下的最优解。这种方法的适用边界很重要当 2n ≥ p 时阶乘数组会出现 0整个公式失效。因为 1 到 2n 里包含了 p 的倍数乘进去模 p 就是 0逆元也不存在。这时需要换用 Lucas 定理把C(2n, n) mod p拆成多个小于 p 的组合数分段计算。4. 代码实现与实战细节Python/C 双版本4.1 Python 版本大数场景随便造Python 的优势就是内置大整数不用为溢出操心。我平时写脚本验证结果、跑大规模数列都用这个def catalan_sequence(n): 返回 C_0 到 C_n 的完整序列 c [0] * (n 1) c[0] 1 for i in range(n): c[i 1] c[i] * (4 * i 2) // (i 2) return c if __name__ __main__: seq catalan_sequence(30) for i, v in enumerate(seq): print(fC_{i} {v})跑出来 C_30 3814986502092304跟标准值一致。这个脚本 n 到几千也就几秒n 到上万会慢一些但不会崩。如果你要极致一点的单点计算可以用质因数分解法避免大数乘除法def sieve(limit): is_prime [True] * (limit 1) is_prime[0] is_prime[1] False for i in range(2, int(limit**0.5) 1): if is_prime[i]: for j in range(i * i, limit 1, i): is_prime[j] False return [i for i in range(2, limit 1) if is_prime[i]] def legendre_exp(n, p): 勒让德公式n! 中质数 p 的指数 s 0 while n: n // p s n return s def catalan_prime_factor(n): primes sieve(2 * n 1) result 1 for p in primes: e legendre_exp(2 * n, p) - legendre_exp(n, p) - legendre_exp(n 1, p) result * p ** e return result这个方法的原理是C_n (2n)! / (n!(n1)!)把分子分母各自用勒让德公式算出每个质数的指数相减得到结果的质因数分解再乘起来。全程没有除法只有乘法和幂运算对大数库不友好或者需要质因数信息的场景很有用。n40 的时候这个版本大概几毫秒。4.2 C 版本取模与逆元的正确姿势到了 C一切都要自己安排。先给出最常用的线性递推取模版#include bits/stdc.h using namespace std; const long long MOD 1000000007LL; long long power(long long a, long long b, long long m) { long long r 1 % m; a % m; while (b) { if (b 1) r r * a % m; a a * a % m; b 1; } return r; } vectorlong long catalan_mod(int n, long long mod) { vectorlong long c(n 1); c[0] 1; for (int i 0; i n; i) { long long num (4LL * i 2) % mod; long long den (i 2) % mod; c[i 1] c[i] * num % mod * power(den, mod - 2, mod) % mod; } return c; }这个版本每步都乘逆元单个卡特兰数的复杂度是 O(n log MOD)因为求逆元用了快速幂。如果 n 不大或者只求少数几个够用。多组查询场景下阶乘预处理版更快const int MAXN 2000005; long long fact[MAXN], invfact[MAXN]; void init_fact(int n, long long mod) { fact[0] 1; for (int i 1; i n; i) fact[i] fact[i - 1] * i % mod; invfact[n] power(fact[n], mod - 2, mod); for (int i n; i 1; i--) invfact[i - 1] invfact[i] * i % mod; } long long catalan_query(int n, long long mod) { // (2n)! / (n! * (n1)!) if (2 * n MAXN) return -1; // 越界保护 return fact[2 * n] * invfact[n] % mod * invfact[n 1] % mod; }预处理 O(MAXN)每次查询 O(1)。这里要特别注意MAXN至少要开到2n因为查的是fact[2n]。我踩过一次坑MAXN 按 n 开结果数组越界读了一堆脏数据输出全是乱码。4.3 参数选择与边界处理几个必须记住的参数约定参数说明常见取值MOD取模的模数1e97、998244353MAXN阶乘数组上限2n 向上取整C_0卡特兰数起点恒为 1溢出点long long 极限n ≥ 36阶乘失效点2n ≥ MOD需改用 Lucas关于阶乘失效如果你用 1e97n 可以大到约 5×10^8 都不会让 2n 超过 MOD这种情况下阶乘版一直有效。但如果你想用比较小的模数比如 1e63n 只要超过 5×10^5 就会触发失效必须上 Lucas。实际写题时模数往往是 1e97 附近所以大部分情况阶乘预处理是安全的只要 n 不夸张。实操提示写 Lucas 之前先判断一下2n和MOD的关系如果2n MOD直接阶乘版就好了别给自己找麻烦。5. 常见问题与排查技巧实录5.1 溢出与取模的“隐形杀手”最常见的翻车就是这么写的// 错误示范 long long catalan(int n) { long long res 1; for (int i 0; i n; i) { res res * (4 * i 2) / (i 2); // 这里会丢精度 } return res; }这个版本在 n 很小的时候碰巧对因为每步乘法结果足够小、除法正好整除。但 n 一大中间乘积先溢出或者除法的整除性在计算顺序上被破坏结果就错了。正确做法要么用__int128撑一下__int128 res 1; for (int i 0; i n; i) { res res * (4 * i 2) / (i 2); }__int128能撑到约 1.7×10^38n 到 60 左右都没问题。要么就直接取模。还有一个更隐蔽的坑取模时先除后模。比如res res * num / den % MOD中间除法在模运算下没有意义必须先求逆元。我见过有人在模意义下直接写/ (n1)小数据看不出问题一提交就 WA。5.2 递推下标与边界条件递推式的下标写错是第二个高发区。整理一下容易混淆的几个点递推求和里是C_j * C_{i-1-j}不是C_j * C_{i-j}。线性递推里从i0推到in-1最后得到C_n别多推或少推一项。C_0 1是约定如果题目问的是“n 个元素的出栈序列数”当 n0 时答案一般是 1空序列算一种别返回 0。组合数公式里分母是n1写n! * (n1)!时别漏掉那个n1。5.3 常见问题速查表现象可能原因解决方向小 n 正确、大 n 变成负数long long 溢出换大数或取模取模后结果完全不对用了整数除法而非逆元改成快速幂求逆元只有前几项对之后就错递推下标写错检查i-1-j提交 RE运行时错误数组开小访问越界MAXN 至少开到 2n特定 n 结果突然变 02n ≥ MOD 导致阶乘为 0改用 Lucas 定理结果比正确答案大一倍漏了某个边界处理检查 C_0 和 C_1独家避坑调试卡特兰数最有效的一句话是“打表验证前 15 项”。把 1、1、2、5、14、42、132、429、1430、4862、16796、58786、208012、742900、2674440 这串存下来写完代码先跑前 15 项对比能一眼看穿绝大部分错误——包括递推错、公式错、边界错。这招我已经用了很多年比单步调试快多了。6. 实操心得与后续扩展从工程角度再补几句掏心窝的经验。第一永远优先考虑问题规模对应的数据范围n ≤ 20 直接算、n ≤ 10^5 用线性递推、n 需要多组查询用阶乘预处理、n 大到让 2n 超过模数就上 Lucas。先看范围再选工具比一上来就写最复杂的版本靠谱得多。第二卡特兰数经常不是独立出现的它会以“中间结果”的身份出现在更大的组合问题里。比如某些动态规划题目状态转移方程拆到某一步会发现某个维度就是在数卡特兰数这时候能识别出来就能把 O(n²) 或 O(n³) 直接降到 O(n)。识别信号就是前面说的那几个关键词场景。第三如果你想继续深挖有两个方向值得走。一个是Dyck 路径的加权推广比如限制路径高度不超过某个值这类问题对应的是带参数的卡特兰数变体可以用生成函数或者反射原理处理。另一个是卡特兰数在形式语言和编译原理里的应用比如语法分析树的数量、表达式加括号的方案数这些在写词法分析器、语法解析器的时候是有实际用处的尤其是做表达式求值和 AST 构造时理解加括号方案数背后的组合结构能帮你设计更合理的递归下降逻辑。最后再分享一个小工具级的技巧当你在 C 里既要大数又要取模其实可以考虑用 Python 生成小规模的参考表再用 C 去跑大规模两边交叉验证。我自己做组合计数模块时就是这么干的先用 Python 快速打出前几十项当基准然后 C 的实现跑同样的输入对比几轮下来基本能保证逻辑正确。毕竟卡特兰数这种东西答案本身就是一个很好的“自校验器”——它的整数性质、递推关系、通项三者互相印证只要你多留个心眼很难真的算错还不自知。