在组合数学与算法竞赛的世界里有一类数列总能在看似毫不相干的场景中反复出现合法括号的计数、栈的出栈序列、二叉树的形态数、网格路径数……它们看似形态各异背后却对应着同一个经典的递归计数模型——卡特兰数Catalan Number。如果说 Dijkstra 是单源最短路的贪心标杆那卡特兰数就是组合递归计数的代名词。本文将从定义公式、核心本质、经典场景、代码实现到进阶拓展一次性讲透卡特兰数的全部核心内容。一、基础认知定义与核心公式卡特兰数是一组满足特定递推关系的自然数数列是组合数学中最经典的计数序列之一广泛应用于括号匹配、树结构、路径规划等多个领域。1. 数列直观感受卡特兰数前 7 项如下数值增长极快呈指数级上升n第 n 项卡特兰数 Cₙ0111223541454261322. 三大核心公式卡特兰数有三种常用表达形式分别对应不同的使用场景1通项公式组合数形式最常用的计算式直接通过组合数求解Cn1n1(2nn) C_n \frac{1}{n1}\binom{2n}{n}Cn​n11​(n2n​)适用于已知 n 直接计算结果编程中可配合组合数函数快速求解。2卷积递推公式本质形式卡特兰数的递归定义对应「拆分左右子问题」的核心思想C01,Cn1∑i0nCi⋅Cn−i C_0 1,\quad C_{n1} \sum_{i0}^{n} C_i \cdot C_{n-i}C0​1,Cn1​i0∑n​Ci​⋅Cn−i​该公式是所有卡特兰应用场景的数学本质整体问题拆分为左右两个独立子问题结果相乘后累加。3线性递推公式优化计算由通项推导而来适合编程线性遍历计算时间复杂度 O(n)C01,CnCn−1⋅4n−2n1 C_0 1,\quad C_n C_{n-1} \cdot \frac{4n-2}{n1}C0​1,Cn​Cn−1​⋅n14n−2​二、底层本质为什么万千问题殊途同归很多人觉得卡特兰数场景多、难记忆实则所有应用都满足三个共同的核心特征。抓住这三点就能快速识别卡特兰模型无需死记硬背场景。可递归拆分规模为 n 的整体问题可通过一个分界点拆分为左右两个独立的子问题最终结果为所有拆分情况的乘积之和完美匹配卷积递推公式。前缀约束性过程中任意前缀位置A 类元素的数量始终 ≥ B 类元素的数量非严格领先不会出现 B 反超的非法情况。对等性两类操作/元素的总数量完全相等均为 n 个。所有经典卡特兰问题本质都是这三个特征的不同场景包装。三、五大经典应用场景全解1. 合法括号序列最经典原型问题描述给定 n 对圆括号求所有合法的括号组合总数。合法要求任意前缀中左括号数量 ≥ 右括号数量。模型映射左括号 A类元素右括号 B类元素天然满足「前缀约束总数相等」。示例n3 时共有((()))、(()())、(())()、()(())、()()()共 5 种对应 C₃5。2. 栈的出栈序列问题描述元素 1~n 按顺序依次入栈可随时出栈求不同的出栈序列总数。模型映射入栈操作 A类元素出栈操作 B类元素前缀中入栈次数 ≥ 出栈次数总数相等。示例n3 时合法出栈序列共 5 种对应 C₃5。3. 二叉树形态计数问题描述求 n 个节点能构成的互不相同的二叉树或二叉搜索树的数量。模型映射选定根节点后左子树有 i 个节点、右子树有 n-1-i 个节点左右子树独立计数后相乘完全匹配卷积递推式。示例n3 时二叉树形态共 5 种对应 C₃5。4. 凸多边形三角剖分问题描述对凸 n2 边形进行三角剖分连接不相交对角线全部分割为三角形求不同剖分方案总数。模型映射任选一条边构造三角形将多边形拆分为左右两个子凸多边形递归计数后累加。示例凸四边形n2有 2 种剖分方案对应 C₂2。5. 不越对角线格路问题描述从 (0,0) 走到 (n,n)仅能向右、向上移动要求路径全程不越过对角线 yx求合法路径总数。模型映射向右走 A类元素向上走 B类元素前缀中向右步数 ≥ 向上步数总数相等。示例n2 时合法路径共 2 种对应 C₂2。四、Python 代码实现从本地计算到竞赛取模1. 本地无取模最简实现日常练习、作业计算中Python 支持大整数直接用通项公式即可代码极简frommathimportcombdefcatalan(n):# 通项公式C(n) 1/(n1) * C(2n, n)returncomb(2*n,n)//(n1)# 测试print(catalan(3))# 输出 5print(catalan(5))# 输出 422. 线性递推实现无需依赖组合数函数纯递推计算适合理解递推逻辑defcatalan_dp(n):res1foriinrange(1,n1):resres*(4*i-2)//(i1)returnres3. 竞赛取模场景逆元 Lucas 定理算法竞赛中题目通常要求结果对质数取模此时不能直接用整除必须使用费马小定理求乘法逆元处理除法若 n 达到 1e18 级别需配合 Lucas 定理拆分计算MOD20100403# 题目给定质数模数defcomb_small(n,k,p):ifk0orkn:return0kmin(k,n-k)numeratordenominator1foriinrange(1,k1):numeratornumerator*(n-ki)%p denominatordenominator*i%p# 费马小定理求逆元分母逆元 分母^(p-2) mod preturnnumerator*pow(denominator,p-2,p)%pdeflucas(n,k,p):ifk0:return1returnlucas(n//p,k//p,p)*comb_small(n%p,k%p,p)%pdefcatalan_mod(n,p):clucas(2*n,n,p)returnc*pow(n1,p-2,p)%p五、进阶拓展从卡特兰到广义伯特兰选票定理卡特兰数并非孤立的知识点它是广义伯特兰选票定理的一个特例。1. 伯特兰选票问题设定候选人 A 总计得 a 票候选人 B 总计得 b 票逐张计票。根据约束不同分为两类非严格领先全程 A 票数 ≥ B 票数公式为Na−b1a1⋅(aba)(a≥b) N \frac{a-b1}{a1} \cdot \binom{ab}{a} \quad (a\ge b)Na1a−b1​⋅(aab​)(a≥b)严格领先全程 A 票数 B 票数公式为Na−bab⋅(aba)(ab) N \frac{a-b}{ab} \cdot \binom{ab}{a} \quad (a b)Naba−b​⋅(aab​)(ab)2. 与卡特兰数的关联当a b n且要求非严格领先时代入公式可得N1n1(2nn)Cn N \frac{1}{n1}\binom{2n}{n} C_nNn11​(n2n​)Cn​即n 对元素的非严格领先选票问题就是标准卡特兰数。卡特兰数是选票定理在「两类元素数量相等」时的特殊情况。六、真题对应面试与竞赛刷题指南题目平台考点难度96. 不同的二叉搜索树LeetCode卡特兰数入门中等22. 括号生成LeetCode卡特兰数 回溯构造中等P1044 栈洛谷出栈序列计数普及-P1641 [SCOI2010] 生成字符串洛谷广义伯特兰选票 取模提高/省选-1023 Train Problem IIHDU卡特兰大数计算入门写在最后卡特兰数的魅力在于它能将纷繁复杂的场景统一到同一个递归模型之下。掌握卡特兰数从来不是死记硬背多少种应用场景而是抓住「递归拆分前缀约束」的核心本质遇到新问题时能快速识别模型、套用公式。从基础的括号计数到进阶的选票定理再到竞赛中的取模与 Lucas 优化卡特兰数既是组合数学的入门经典也是算法进阶的必经之路。