数学大学
Catalan数
组合数学 · 神奇的序列
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
数学大学
Catalan数
组合数学 · 神奇的序列
计算机界的精灵
Catalan 数是组合计数的明星：合法括号、二叉树、出栈序列全是它。
递推
Cₙ₊₁ = Σ CᵢCₙ₋ᵢ，按首个组成部分分类
无处不在
凡是「两两配对不交叉」的计数都收敛到它
Catalan数的直接表达式
Catalan 数有简洁封闭式：Cₙ = C(2n,n)/(n+1)。
公式
中心二项系数除以 n+1
数值
1, 1, 2, 5, 14, 42, 132…
Catalan数的各种实例
同一数字的百变化身：出栈序列数、凸多边形三角剖分、二叉树计数……
出栈序列
n 个元素入栈出栈的合法序列数 Cₙ
三角剖分
凸 n+2 边形的三角剖分数 Cₙ
对应本质
实例间存在一一对应，故同数
本节要点
- ✓Catalan 数：配对不交叉类计数的答案
- ✓递推按首个组成部分分类
- ✓Cₙ = C(2n,n)/(n+1)
延伸主题：手算 C₁ 到 C₅证明括号序列与出栈序列对应
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1为什么「合法括号序列」「出栈序列」「二叉树」计数相同？
参考答案它们之间存在显式的一一对应：每个对象都能翻译成另一个。例如括号序列对应栈操作（入栈=左括号、出栈=右括号）。计数相同不是巧合，是同构。
2Catalan 递推「按首个组成部分分类」是如何想到的？
参考答案找一个「锚点」把对象分成两段独立子问题：如首个返回原点的位置、根与左子树。锚点两侧互不干扰，数目相乘，锚点扫过全体相加——这是组合计数最通用的分解思路。
3遇到一个新计数问题，怎么判断答案是不是 Catalan 数？
参考答案看结构：能否把对象分解为「一对配对符号包裹的内外两部分」，或问题等价于 n 个 +1 与 n 个 −1 的前缀和恒非负序列。凡能化成这两类模型的，答案就是 Catalan 数 Cₙ。