阅读 桌面完整版

组合数学入门（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 (终极计算与技术博客) —

微信公众号: 小赖子的英国生活和资讯 JustYYUK

阅读 桌面完整版