卡特兰数

初始条件：C0=1C0​=1

递推式1：

Cn=∑i=0n−1Ci⋅Cn−i−1Cn​=i=0∑n−1​Ci​⋅Cn−i−1​

含义：将规模为 nn 的问题拆分为两个独立子问题，左子问题规模 ii，右子问题规模 n−1−in−1−i，通过乘法原理计算单种拆分的方案数，求和得到总方案数。

递推式2：

Cn=2(2n−1)n+1⋅Cn−1Cn​=n+12(2n−1)​⋅Cn−1​

通项：

Cn=1n+1(2nn)=(2nn)−(2nn−1)Cn​=n+11​(n2n​)=(n2n​)−(n−12n​)

参考资料：https://www.cnblogs.com/willeywindsor/p/19733310

卡特兰数（Catalan Number）全面详解与典型例题

卡特兰数是组合数学中用于解决带约束的计数问题的经典数列，核心描述「两类对等元素的排列中，任意前缀满足某类元素数量不小于另一类」的场景，广泛应用于括号匹配、栈操作、二叉树计数、路径规划等领域。

目录

1. 卡特兰数核心定义与公式 1.1 基本定义与前几项 1.2 核心递推公式 （1）二阶求和递推式（本质分治思想） （2）一阶线性递推式（编程计算首选） 1.3 通项公式 （1）闭合式（最常用，直接计算） （2）容斥式（反射原理推导，体现核心本质） 1.4 生成函数与渐近特性
2. 底层原理：反射原理与核心判据 2.1 基础模型：Dyck路径 2.2 反射原理推导通项 2.3 卡特兰数问题核心判据
3. 经典应用场景
4. 典型例题详解 （一）基础例题：直接套用核心模型 例题1 括号匹配计数 例题2 栈的出栈序列判断 例题3 凸多边形三角划分 （二）进阶例题：模型转化与边界处理 例题4 买票找零进阶版 例题5 不相交握手问题 例题6 选票问题（广义卡特兰数） （三）编程实战例题（力扣真题） 例题7 力扣96. 不同的二叉搜索树 例题8 力扣22. 括号生成
5. 易错点与注意事项

1 卡特兰数核心定义与公式

1.1 基本定义与前几项

卡特兰数下标从0开始，初始条件 C0=1C0​=1 第 nn 个卡特兰数记为 CnCn​。

前11项（C0C0​ ~ C10C10​）：1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796

直观感受：C3=5C3​=5、C4=14C4​=14 是最常用的基础值，C20C20​ 已达百亿级，呈指数级增长。

1.2 核心递推公式

（1）二阶求和递推式（本质分治思想）

初始条件：C0=1C0​=1 对 n≥1n≥1，有：

Cn=∑i=0n−1Ci⋅Cn−1−iCn​=i=0∑n−1​Ci​⋅Cn−1−i​

含义：将规模为 nn 的问题拆分为两个独立子问题，左子问题规模 ii，右子问题规模 n−1−in−1−i，通过乘法原理计算单种拆分的方案数，求和得到总方案数。

（2）一阶线性递推式（编程计算首选）

初始条件：C0=1C0​=1 对 n≥1n≥1，有：

Cn=2(2n−1)n+1⋅Cn−1Cn​=n+12(2n−1)​⋅Cn−1​

优势：无需循环求和，单步递推即可计算，时间复杂度 O(n)O(n)，适合大数取模场景，由通项公式直接化简得到。

1.3 通项公式

（1）闭合式（最常用，直接计算）

Cn=1n+1(2nn)Cn​=n+11​(n2n​)

其中 (2nn)(n2n​) 为组合数，表示从 2n2n 个元素中选 nn 个的方案数。

（2）容斥式（反射原理推导，体现核心本质）

Cn=(2nn)−(2nn−1)Cn​=(n2n​)−(n−12n​)

含义：总方案数 - 非法方案数 = 合法方案数，是所有卡特兰数问题的底层逻辑。

1.4 生成函数与渐近特性

普通生成函数：

G(x)=∑n=0∞Cnxn=1−1−4x2xG(x)=n=0∑∞​Cn​xn=2x1−1−4x​​

渐近增长式（n→∞n→∞）：

Cn∼4nn3/2πCn​∼n3/2π​4n​

说明卡特兰数呈指数级增长，计算时需注意数值溢出。

2 底层原理：反射原理与核心判据

卡特兰数的所有应用，本质都是Dyck路径模型的映射，通过反射原理完成严谨推导。

2.1 基础模型：Dyck路径

定义：从原点 (0,0)(0,0) 出发，到终点 (n,n)(n,n)，每步仅能向右 R(1,0)R(1,0) 或向上 U(0,1)U(0,1)，且路径全程不越过直线 y=xy=x（即任意点 (x,y)(x,y) 满足 y≤xy≤x）。

合法Dyck路径的总数，就是第 nn 个卡特兰数 CnCn​。

2.2 反射原理推导通项

总路径数：从 (0,0)(0,0) 到 (n,n)(n,n) 共需 2n2n 步，其中 nn 步 RR、nn 步 UU，总方案数为 (2nn)(n2n​)。

非法路径数：路径越过 y=xy=x（即触碰直线 y=x+1y=x+1）的方案数。 对任意非法路径，找到其第一次触碰 y=x+1y=x+1 的点，将起点到该点的路径关于 y=x+1y=x+1 镜像反射，起点 (0,0)(0,0) 会被反射到 (−1,1)(−1,1)。

该反射是双射：每条非法路径唯一对应一条从 (−1,1)(−1,1) 到 (n,n)(n,n) 的路径，反之亦然。 从 (−1,1)(−1,1) 到 (n,n)(n,n) 共需 2n2n 步，其中 n+1n+1 步 RR、n−1n−1 步 UU，方案数为 (2nn−1)(n−12n​)。

合法路径数：总路径数 - 非法路径数 = (2nn)−(2nn−1)(n2n​)−(n−12n​)，化简后即闭合式 1n+1(2nn)n+11​(n2n​)。

2.3 卡特兰数问题核心判据

一个问题可通过卡特兰数计数，当且仅当满足以下3个条件：

1. 可抽象为两类对等的操作/元素（记为A、B），总数量均为 nn；
2. 排列/操作过程中，任意前缀中A的数量 ≥ B的数量；
3. 最终A、B的总数量完全相等。

3 经典应用场景

所有场景均严格匹配核心判据，只需完成元素与约束的映射即可套用卡特兰数：

应用场景	元素映射（A/B）	核心约束	方案数
n对括号合法匹配	左括号/右括号	任意前缀左括号数 ≥ 右括号数	CnCn​
n个元素合法出栈序列	入栈操作/出栈操作	任意前缀入栈次数 ≥ 出栈次数
n个节点的不同二叉树	左子树节点/右子树节点	根节点拆分后，左右子树独立计数
凸n+2边形三角划分	拆分后的左右凸多边形	三角形拆分后无重叠、无遗漏
圆周2n个点不相交弦	弦分割的左右点集	所有弦两两不相交，点不重复连接
2n人买票找零（5元/10元各n人）	持5元者/持10元者	任意前缀5元人数 ≥ 10元人数
(0,0)到(2n,0)非降路径（步长±1）	+1步/-1步	路径全程不越过x轴（y≥0）

4 典型例题详解

分基础入门、进阶转化、编程实战三个层级，覆盖从概念理解到落地应用的全场景。

（一）基础例题：直接套用核心模型

例题1 括号匹配计数

题目：求n=4时，合法的括号匹配序列有多少种？验证结果的正确性。

思路：直接匹配卡特兰数经典模型，n对括号的合法匹配数为 CnCn​。

解答： 闭合式计算：

C4=14+1(84)=15×70=14C4​=4+11​(48​)=51​×70=14

递推验证：

C4=C0C3+C1C2+C2C1+C3C0=1×5+1×2+2×1+5×1=14C4​=C0​C3​+C1​C2​+C2​C1​+C3​C0​=1×5+1×2+2×1+5×1=14

结果一致。

合法性校验：所有序列满足「任意前缀左括号数≥右括号数，总左=右=4」，符合核心判据。

核心考点：卡特兰数基础模型识别，公式直接应用。

例题2 栈的出栈序列判断

题目：元素1、2、3、4按顺序入栈，请问有多少种合法出栈序列？判断序列 3,2,4,1 和 4,1,2,3 是否合法。

思路：合法出栈序列数对应卡特兰数 C4C4​；序列合法性的核心是「任意时刻出栈次数不超过入栈次数」。

解答： 合法序列总数：n=4，对应 C4=14C4​=14 种。 序列 3,2,4,1：操作过程为「1入、2入、3入、3出、2出、4入、4出、1出」，全程栈非空时出栈，合法。 序列 4,1,2,3：要先出4，必须1、2、3、4全部入栈，栈顶为4，出栈后栈顶只能是3，无法出1，非法。

核心考点：栈操作与卡特兰数的映射关系，非法序列的本质识别。

例题3 凸多边形三角划分

题目：凸六边形有多少种不同的三角划分方案？

思路：凸 mm 边形的三角划分方案数对应卡特兰数 Cm−2Cm−2​（m=n+2  ⟹  n=m−2m=n+2⟹n=m−2）。

解答： 凸六边形 m=6m=6，对应 n=6−2=4n=6−2=4，方案数为 C4=14C4​=14。

核心考点：几何问题的组合转化，卡特兰数分治递推的应用。

（二）进阶例题：模型转化与边界处理

例题4 买票找零进阶版

题目：12个人排队买电影票，票价5元，6人仅持5元纸币，6人仅持10元纸币，售票员无初始零钱。请问：

1. 仅考虑纸币类型，有多少种合法排队顺序？
2. 若每个人都是不同个体，总方案数是多少？

思路：基础版对应卡特兰数 C6C6​；人可区分时，需给两类人群分别排序，乘以对应排列数。

解答： 仅考虑纸币类型：n=6，

C6=17(126)=17×924=132C6​=71​(612​)=71​×924=132种。 人可区分的总方案数：6个持5元的人有 6!6! 种排列，6个持10元的人有 6!6! 种排列，总方案数为：C6×6!×6!=132×720×720=68428800C6​×6!×6!=132×720×720=68428800

核心考点：有序与无序场景的区分，避免遗漏排列数。

例题5 不相交握手问题

题目：圆周上有8个点，编号1-8顺时针排列，每个点与另一个点握手，所有连线不能相交，求不同的握手方案数。

思路：2n个点的不相交握手方案数对应卡特兰数 CnCn​，通过分治递推验证。

解答： 2n=8  ⟹  n=42n=8⟹n=4，方案数为 C4=14C4​=14 种。

递推验证：选定点1，仅能和偶数号点握手（否则两侧点数为奇数，无法配对）： 1和2握手：剩余6个点，方案数 C3=5C3​=5； 1和4握手：左2个点、右4个点，方案数 C1×C2=2C1​×C2​=2； 1和6握手：左4个点、右2个点，方案数 C2×C1=2C2​×C1​=2； 1和8握手：剩余6个点，方案数 C3=5C3​=5；

总和 5+2+2+5=145+2+2+5=14，与 C4C4​ 一致。

核心考点：环形问题的线性转化，卡特兰数分治递推的应用。

例题6 选票问题（广义卡特兰数）

题目：候选人A得m票，B得n票，m>n。求计票过程中，A的票数始终领先B的方案数。

思路：卡特兰数的通用推广，通过反射原理推导，又称Bertrand选票问题。

解答： 总方案数：从m+n个位置选m个给A，共 (m+nm)(mm+n​) 种。 非法方案数：计票中出现A票数≤B的情况，通过反射原理得非法方案数为 (m+nm+1)(m+1m+n​)。

合法方案数：

(m+nm)−(m+nm+1)=m−nm+n(m+nm)(mm+n​)−(m+1m+n​)=m+nm−n​(mm+n​)

特殊情况：当m=n时，要求A始终≥B，即卡特兰数 Cn=1n+1(2nn)Cn​=n+11​(n2n​)，与公式完全匹配。

核心考点：反射原理的通用应用，「≥」与「>」约束的公式区分。

5 易错点与注意事项

1. 下标混淆：卡特兰数下标从0开始，C0=1C0​=1 对应0对括号、0个节点的二叉树，切勿将 C1C1​ 作为首个值导致结果错误。
2. 约束条件误判：必须严格满足「任意前缀A≥B」，若为「严格大于」，需调整公式，如m=n时严格领先的方案数为0，而非 CnCn​。
3. 有序与无序区分：卡特兰数计算的是「类型」的方案数，若元素可区分，需乘以对应排列数，如买票问题中不同个体需乘 n!⋅n!n!⋅n!。
4. 数值溢出：卡特兰数增长极快，n≥20时需用大数类型或模运算，模运算中除法需用逆元处理。
5. 模型转化错误：仅满足核心判据的问题可套用卡特兰数，并非所有组合计数都适用，如n个元素的全排列并非卡特兰阵计算和矩阵快速幂