卡特兰数：组合计数的递归经典，括号栈树全解

在组合数学与算法竞赛的世界里，有一类数列总能在看似毫不相干的场景中反复出现：合法括号的计数、栈的出栈序列、二叉树的形态数、网格路径数……它们看似形态各异，背后却对应着同一个经典的递归计数模型——卡特兰数（Catalan Number）。

如果说 Dijkstra 是单源最短路的贪心标杆，那卡特兰数就是组合递归计数的代名词。本文将从定义公式、核心本质、经典场景、代码实现到进阶拓展，一次性讲透卡特兰数的全部核心内容。

一、基础认知：定义与核心公式

卡特兰数是一组满足特定递推关系的自然数数列，是组合数学中最经典的计数序列之一，广泛应用于括号匹配、树结构、路径规划等多个领域。

1. 数列直观感受

卡特兰数前 7 项如下，数值增长极快，呈指数级上升：

2. 三大核心公式

卡特兰数有三种常用表达形式，分别对应不同的使用场景：

（1）通项公式（组合数形式）

最常用的计算式，直接通过组合数求解：
Cn=1n+1(2nn) C_n = \frac{1}{n+1}\binom{2n}{n}Cn​=n+11​(n2n​)
适用于已知 n 直接计算结果，编程中可配合组合数函数快速求解。

（2）卷积递推公式（本质形式）

卡特兰数的递归定义，对应「拆分左右子问题」的核心思想：
C0=1,Cn+1=∑i=0nCi⋅Cn−i C_0 = 1,\quad C_{n+1} = \sum_{i=0}^{n} C_i \cdot C_{n-i}C0​=1,Cn+1​=i=0∑n​Ci​⋅Cn−i​
该公式是所有卡特兰应用场景的数学本质：整体问题拆分为左右两个独立子问题，结果相乘后累加。

（3）线性递推公式（优化计算）

由通项推导而来，适合编程线性遍历计算，时间复杂度 O(n)：
C0=1,Cn=Cn−1⋅4n−2n+1 C_0 = 1,\quad C_n = C_{n-1} \cdot \frac{4n-2}{n+1}C0​=1,Cn​=Cn−1​⋅n+14n−2​

二、底层本质：为什么万千问题殊途同归？

很多人觉得卡特兰数场景多、难记忆，实则所有应用都满足三个共同的核心特征。抓住这三点，就能快速识别卡特兰模型，无需死记硬背场景。

1. 可递归拆分
   规模为 n 的整体问题，可通过一个分界点拆分为左右两个独立的子问题，最终结果为所有拆分情况的乘积之和，完美匹配卷积递推公式。

2. 前缀约束性
   过程中任意前缀位置，A 类元素的数量始终 ≥ B 类元素的数量（非严格领先），不会出现 B 反超的非法情况。

3. 对等性
   两类操作/元素的总数量完全相等，均为 n 个。

所有经典卡特兰问题，本质都是这三个特征的不同场景包装。

三、五大经典应用场景全解

1. 合法括号序列（最经典原型）

问题描述：给定 n 对圆括号，求所有合法的括号组合总数。合法要求：任意前缀中左括号数量 ≥ 右括号数量。
模型映射：左括号 = A类元素，右括号 = B类元素，天然满足「前缀约束+总数相等」。
示例：n=3 时，共有((()))、(()())、(())()、()(())、()()()共 5 种，对应 C₃=5。

2. 栈的出栈序列

问题描述：元素 1~n 按顺序依次入栈，可随时出栈，求不同的出栈序列总数。
模型映射：入栈操作 = A类元素，出栈操作 = B类元素；前缀中入栈次数 ≥ 出栈次数，总数相等。
示例：n=3 时，合法出栈序列共 5 种，对应 C₃=5。

3. 二叉树形态计数

问题描述：求 n 个节点能构成的互不相同的二叉树（或二叉搜索树）的数量。
模型映射：选定根节点后，左子树有 i 个节点、右子树有 n-1-i 个节点，左右子树独立计数后相乘，完全匹配卷积递推式。
示例：n=3 时，二叉树形态共 5 种，对应 C₃=5。

4. 凸多边形三角剖分

问题描述：对凸 n+2 边形进行三角剖分（连接不相交对角线，全部分割为三角形），求不同剖分方案总数。
模型映射：任选一条边构造三角形，将多边形拆分为左右两个子凸多边形，递归计数后累加。
示例：凸四边形（n=2）有 2 种剖分方案，对应 C₂=2。

5. 不越对角线格路

问题描述：从 (0,0) 走到 (n,n)，仅能向右、向上移动，要求路径全程不越过对角线 y=x，求合法路径总数。
模型映射：向右走 = A类元素，向上走 = B类元素；前缀中向右步数 ≥ 向上步数，总数相等。
示例：n=2 时，合法路径共 2 种，对应 C₂=2。

四、Python 代码实现：从本地计算到竞赛取模

1. 本地无取模：最简实现

日常练习、作业计算中，Python 支持大整数，直接用通项公式即可，代码极简：

frommathimportcombdefcatalan(n):# 通项公式：C(n) = 1/(n+1) * C(2n, n)returncomb(2*n,n)//(n+1)# 测试print(catalan(3))# 输出 5print(catalan(5))# 输出 42

2. 线性递推实现

无需依赖组合数函数，纯递推计算，适合理解递推逻辑：

defcatalan_dp(n):res=1foriinrange(1,n+1):res=res*(4*i-2)//(i+1)returnres

3. 竞赛取模场景：逆元 + Lucas 定理

算法竞赛中题目通常要求结果对质数取模，此时不能直接用整除，必须使用费马小定理求乘法逆元处理除法；若 n 达到 1e18 级别，需配合 Lucas 定理拆分计算：

MOD=20100403# 题目给定质数模数defcomb_small(n,k,p):ifk<0ork>n:return0k=min(k,n-k)numerator=denominator=1foriinrange(1,k+1):numerator=numerator*(n-k+i)%p denominator=denominator*i%p# 费马小定理求逆元：分母逆元 = 分母^(p-2) mod preturnnumerator*pow(denominator,p-2,p)%pdeflucas(n,k,p):ifk==0:return1returnlucas(n//p,k//p,p)*comb_small(n%p,k%p,p)%pdefcatalan_mod(n,p):c=lucas(2*n,n,p)returnc*pow(n+1,p-2,p)%p

五、进阶拓展：从卡特兰到广义伯特兰选票定理

卡特兰数并非孤立的知识点，它是广义伯特兰选票定理的一个特例。

1. 伯特兰选票问题

设定：候选人 A 总计得 a 票，候选人 B 总计得 b 票，逐张计票。
根据约束不同分为两类：

• 非严格领先：全程 A 票数 ≥ B 票数，公式为
  N=a−b+1a+1⋅(a+ba)(a≥b) N = \frac{a-b+1}{a+1} \cdot \binom{a+b}{a} \quad (a\ge b)N=a+1a−b+1​⋅(aa+b​)(a≥b)
• 严格领先：全程 A 票数 > B 票数，公式为
  N=a−ba+b⋅(a+ba)(a>b) N = \frac{a-b}{a+b} \cdot \binom{a+b}{a} \quad (a > b)N=a+ba−b​⋅(aa+b​)(a>b)

2. 与卡特兰数的关联

当a = b = n且要求非严格领先时，代入公式可得：
N=1n+1(2nn)=Cn N = \frac{1}{n+1}\binom{2n}{n} = C_nN=n+11​(n2n​)=Cn​
即：n 对元素的非严格领先选票问题，就是标准卡特兰数。卡特兰数是选票定理在「两类元素数量相等」时的特殊情况。

六、真题对应：面试与竞赛刷题指南

写在最后

卡特兰数的魅力，在于它能将纷繁复杂的场景统一到同一个递归模型之下。掌握卡特兰数，从来不是死记硬背多少种应用场景，而是抓住「递归拆分+前缀约束」的核心本质，遇到新问题时能快速识别模型、套用公式。

从基础的括号计数，到进阶的选票定理，再到竞赛中的取模与 Lucas 优化，卡特兰数既是组合数学的入门经典，也是算法进阶的必经之路。