组合数学入门（2）：卡特兰数
卡特兰数是组合数学中最重要的数列之一。它们出现在许多表面上看起来完全不同的计数问题中，但实际上这些问题都具有相同的内在结构：平衡性、递归性以及“不交叉”约束。
在本文中，我们将介绍卡特兰数/Catalan，展示几个重要公式，并解释一些经典应用场景，特别是路径不能越过对角线的网格行走问题。
什么是卡特兰数？
卡特兰数列如下：
第 n 个卡特兰数的一般公式为：
一个等价形式为：
这两个公式完全等价，在组合数学中都经常出现。
为什么卡特兰数很重要
卡特兰数用于计数许多具有递归结构或平衡结构的问题。它们通常出现在以下情形中：
- 对象必须以平衡方式构造，
- 路径必须保持在某个边界之内，
- 配对之间不能交叉，
- 结构可以被拆分为独立的左右部分。
因此，它们广泛出现在括号、树、网格、多边形以及栈操作等问题中。
一些重要的卡特兰公式
闭式公式
差分等价形式
递推公式
这个递推公式非常重要。它说明：如果一个规模为 n 的结构可以拆分为左侧大小为 i、右侧大小为 n-1-i 的两个部分，那么总数就是对所有可能拆分方式求和。
生成函数
渐近增长
这说明卡特兰数增长非常快，但仍然略慢于纯指数增长的 4^n。
卡特兰数的经典应用
1. 合法括号
一个经典例子是：计算由 n 对括号构成的所有合法表达式的数量。
当 n = 3 时，合法表达式为：
((())) (()()) (())() ()(()) ()()() 共有 5 种，因此：
关键在于：从左到右扫描时，任意时刻右括号数量都不能超过左括号数量。
2. 二叉树结构
含有 n 个节点的不同二叉树结构数量也是第 n 个卡特兰数。
为什么？因为一旦选择了根节点，其余节点就会分成左子树和右子树。如果左子树有 i 个节点，那么右子树就有 n – 1 – i 个节点。这直接对应递推公式：
这种解释在数据结构、递归算法以及语法解析中非常有用。
3. 多边形三角剖分
一个具有 n + 2 条边的凸多边形，其三角剖分方式数量为：
例如，一个五边形的三角剖分数量为：
这同样是一种“不交叉”结构：所有对角线都不能相交。
4. 栈排列
卡特兰数还用于计数一个包含 n 个元素的栈的合法入栈出栈序列，其中不能出现“未入栈先出栈”的非法操作。
同样体现了“平衡”的约束条件。
5. 不相交握手（配对）
假设有 2n 个人围坐在圆桌旁，每个人与另一个人握手，并要求所有握手连线不能相交。
这种不相交配对的数量为：
这是卡特兰结构的又一个经典例子。
不越过对角线的网格路径
现在我们来看一个最直观、也最优美的卡特兰数解释。
问题描述
假设你从网格上的点 (0,0) 出发，目标是到达 (n,n)。
每一步你只能进行以下操作：
- 向右走一步，或
- 向上走一步。
在没有任何限制的情况下，每条路径恰好包含 n 次向右和 n 次向上，因此总路径数为：
这是因为我们只需从 2n 步中选择哪 n 步是“向右”。
限制条件
现在加入一个约束：路径不能越过对角线：
这意味着在路径的任意时刻，已经走过的“向上”步数不能超过“向右”步数。
满足该约束的路径数量正好是卡特兰数：
为什么这与括号问题一致
两者之间存在直接对应关系：
- 向右一步对应一个左括号，
- 向上一步对应一个右括号。
一条不越过对角线的路径，就对应一个在任意前缀中右括号数量不超过左括号数量的括号序列。
因此，网格路径问题与合法括号问题，本质上是同一个组合结构的不同表现形式。
示例：n = 3
从 (0,0) 到 (3,3)，不加限制的路径总数为：
但不越过对角线的路径数为：
也就是说，20 条路径中只有 5 条满足条件。
反射原理
一种经典推导方法是：
- 先计算所有从 (0,0) 到 (n,n) 的路径数，然后
- 减去那些越过对角线的“非法路径”。
总路径数为：
利用反射原理可以证明，非法路径数为：
因此合法路径数为：
化简后得到：
这正是卡特兰数。
卡特兰数表
| n | C_n |
|---|---|
| 0 | 1 |
| 1 | 1 |
| 2 | 2 |
| 3 | 5 |
| 4 | 14 |
| 5 | 42 |
| 6 | 132 |
| 7 | 429 |
| 8 | 1430 |
如何识别卡特兰问题
在解决组合问题时，如果你看到以下特征，很可能就是卡特兰数：
- 平衡表达式，
- 合法前缀，
- 不相交配对，
- 路径受到对角线或边界限制，
- 可以递归地拆分为左右两部分。
当一个计数问题中隐藏着“平衡”约束时，就值得考虑是否与卡特兰数有关。
总结
卡特兰数完美地展示了：不同的数学问题如何共享相同的内部结构。
它们可以计数：
- 合法括号序列，
- 二叉树结构，
- 多边形三角剖分，
- 不相交配对，
- 栈合法序列，
- 不越过对角线的网格路径。
其中，网格路径的解释尤其直观。从一个简单的路径计数问题出发，引入对角线约束后，就转化为组合数学中最著名的数列之一。
如果你理解了为什么“不能越过对角线”会导出卡特兰数，那么你已经掌握了组合数学的一个核心思想：看似不同的问题，往往可以用完全相同的方法来计数。
关键公式总结
英文：Teaching Kids Programming – Introduction to Combinatorial Mathematics 2 (Catalan Number)
–EOF (终极计算与技术博客) —
本文一共 1586 个汉字, 你数一下对不对.上一篇: 中年男人: 得到、去魅、失落
下一篇: Pearson Vue在线考试体验: 流程/坑点/建议
