卡特兰数——精简版
卡特兰数(Catalan Number)
引言
卡特兰数(Catalan number)是组合数学中一个常出现于各种计数问题中的数列。它以中国蒙古族数学家明安图和比利时数学家欧仁·查理·卡特兰的名字命名。
基本性质
- 前几项：1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786…
- 递推公式：
$$C_n = C_0 C_{n-1} + C_1 C_{n-2} + \cdots + C_{n-1} C_0$$ - 通项公式：
$$C_n = \frac{1}{n+1} \binom{2n}{n} = \frac{(2n)!}{(n+1)!n!}$$
数学推导
我们以最经典的栈问题来推导卡特兰数。
问题描述：n个元素的进栈序列为1,2,3,4…..n，求有多少种不同的出栈序列？
思路1: 路径计数法
将进栈表示为+1，出栈表示为-1
合法的出栈序列必须满足：
- 任意前缀和必须≥0（栈不能为空时出栈）
- +1和-1的总数各为n（n个元素都要进出栈）
分析过程：
- 所有可能的进出栈序列总数为 $\binom{2n}{n}$（从2n个位置中选n个放+1）
- 非法序列：存在某个前缀和<0
- 对于每个非法序列，找到第一个前缀和为-1的位置，将此位置及之前所有元素取反
- 取反后得到的序列有n+1个+1和n-1个-1
- 非法序列总数为 $\binom{2n}{n+1}$
结论：合法出栈序列数 = $\binom{2n}{n} - \binom{2n}{n+1} = \frac{\binom{2n}{n}}{n+1}$
思路2: 递归分解法
设 f(n) = 元素个数为n的出栈序列种数
假设第一个出栈的元素序号为k（1≤k≤n）
当k出栈时：
- 元素1到k-1必须已经进栈
- 元素k+1到n尚未进栈
- 此时问题分解为两个子问题：
- 元素1到k-1的出栈序列：f(k-1)种可能
- 元素k+1到n的出栈序列：f(n-k)种可能
递推公式：
$$f(n) = \sum_{k=1}^{n} f(k-1) \cdot f(n-k)$$令f(0)=1，可得：
$$f(n) = \sum_{i=0}^{n-1} f(i) \cdot f(n-1-i)$$这与卡特兰数的递推公式完全一致，因此f(n) = $C_n$
应用实例
1. 括号匹配
问题：n对括号，有多少种合法的括号匹配序列？
分析：
- 左括号视为+1，右括号视为-1
- 任意前缀和≥0（右括号不能多于左括号）
- 最终和为0（左右括号数量相等）
结论：合法括号序列数为 $C_n$
2. 二叉树计数
问题：n+1个叶子结点可以构成多少种形状不同的满二叉树？
分析方法一：
- 深度优先遍历二叉树，向左记为+1，向右记为-1
- 每个右分支都对应一个左分支
- n+1个叶子对应n个内部节点，需要2n次扩展
分析方法二：
- 根节点将树分为左右两棵子树
- 设T(i,j)表示左子树有i个节点，右子树有j个节点
- 递推关系：$C_n = \sum_{i=0}^{n-1} C_i \cdot C_{n-1-i}$
结论：不同形状的满二叉树数量为 $C_n$
3. 电影购票问题
问题：电影票价50元，售票处无零钱。m个人持100元，n个人持50元(n>m)，问有多少种排队方式使每人都能买到票？
分析：
- 持50元的人标记为+1，持100元的人标记为-1
- 任意前缀和≥0（售票处必须有足够零钱）
- 考虑人的排列，总方案数为 $C_m^{m+n} \cdot m! \cdot n!$
4. 矩阵连乘
问题：表达式a₁×a₂×…×aₙ有多少种不同的加括号方式？
分析：
- 通过括号将表达式分为两部分，再递归处理
- 递推关系：$f(n) = \sum_{i=1}^{n-1} f(i) \cdot f(n-i)$
- 初始条件：f(1) = 1
结论：n个矩阵的不同括号化方案数为 $C_{n-1}$
5. 凸多边形三角剖分
问题：n+2边凸多边形可以划分为三角形的方法数？
分析：
- 选定一条边为基准，从其余顶点选一个连接，将多边形分为三部分
- 递推关系：$f(n) = \sum_{i=0}^{n-1} f(i) \cdot f(n-1-i)$
结论：n+2边凸多边形的三角剖分数为 $C_n$
6. 圆上非交叉连线
问题：圆上2n个点，将这些点成对连接使得n条线段不相交的方法数？
分析：
- 选定一个点，它必须与某个点相连
- 这条连线将其余点分为两部分，递归处理
- 递推关系与卡特兰数相同
结论：不相交连线方式数为 $C_n$
7. 单调路径
问题：从(0,0)到(n,n)，只能向右或向上移动，且不能越过对角线，有多少条路径？
分析：
- 设E表示向东，N表示向北
- 任意前缀中E的个数不小于N的个数
- 等价于合法括号序列问题
结论：合法路径数为 $C_n$
8. 阶梯图形填充
问题：用n个长方形填充高度为n的阶梯状图形的方法数？
分析：
- 递归分解问题
- 递推关系与卡特兰数相同
结论：填充方法数为 $C_n$
9. 两队排队问题
问题：2n个高矮不同的人排成两队，每队n人，要求第二排的人比对应第一排的人高，有多少种排法？
分析：
- 先将2n人按高矮排序
- 问题转化为从2n人中选n人排在第一排
- 等价于进出栈问题
结论：排队方式数为 $C_n$
其他应用
以下问题也可用卡特兰数解决：
汽车队在狭窄路面上行驶，可进入死胡同调头但不能超车，n辆车有多少种不同的行驶顺序？
n个不同的碗从一摞变为另一摞，中间可临时放置，有多少种可能的放置顺序？