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

2301_80054842

378人浏览 · 2026-06-13 11:16:17

2301_80054842 · 2026-06-13 11:16:17 发布

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

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

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

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

1. 数列直观感受

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

n	第 n 项卡特兰数 Cₙ
0	1
1	1
2	2
3	5
4	14
5	42
6	132

2. 三大核心公式

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

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

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

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

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

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

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

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

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

可递归拆分
规模为 n 的整体问题，可通过一个分界点拆分为左右两个独立的子问题，最终结果为所有拆分情况的乘积之和，完美匹配卷积递推公式。
前缀约束性
过程中任意前缀位置，A 类元素的数量始终 ≥ B 类元素的数量（非严格领先），不会出现 B 反超的非法情况。
对等性
两类操作/元素的总数量完全相等，均为 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 支持大整数，直接用通项公式即可，代码极简：

from math import comb

def catalan(n):
    # 通项公式：C(n) = 1/(n+1) * C(2n, n)
    return comb(2 * n, n) // (n + 1)

# 测试
print(catalan(3))  # 输出 5
print(catalan(5))  # 输出 42

2. 线性递推实现

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

def catalan_dp(n):
    res = 1
    for i in range(1, n + 1):
        res = res * (4 * i - 2) // (i + 1)
    return res

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

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

MOD = 20100403  # 题目给定质数模数

def comb_small(n, k, p):
    if k < 0 or k > n:
        return 0
    k = min(k, n - k)
    numerator = denominator = 1
    for i in range(1, k + 1):
        numerator = numerator * (n - k + i) % p
        denominator = denominator * i % p
    # 费马小定理求逆元：分母逆元 = 分母^(p-2) mod p
    return numerator * pow(denominator, p - 2, p) % p

def lucas(n, k, p):
    if k == 0:
        return 1
    return lucas(n // p, k // p, p) * comb_small(n % p, k % p, p) % p

def catalan_mod(n, p):
    c = lucas(2 * n, n, p)
    return c * pow(n + 1, p - 2, p) % p

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

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

1. 伯特兰选票问题

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

非严格领先：全程 A 票数 ≥ B 票数，公式为
$\frac{a-b+1}{a+1} \cdot \binom{a+b}{a} \quad (a\ge b)$
严格领先：全程 A 票数 > B 票数，公式为
$\frac{a-b}{a+b} \cdot \binom{a+b}{a} \quad (a > b)$

2. 与卡特兰数的关联

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

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

题目	平台	考点	难度
96. 不同的二叉搜索树	LeetCode	卡特兰数入门	中等
22. 括号生成	LeetCode	卡特兰数 + 回溯构造	中等
P1044 栈	洛谷	出栈序列计数	普及-
P1641 [SCOI2010] 生成字符串	洛谷	广义伯特兰选票 + 取模	提高+/省选-
1023 Train Problem II	HDU	卡特兰大数计算	入门