什么是 Catalan 数
说到 Catalan 数,就不得不提及 Catalan 序列。这是一个整数序列,其通项公式为:
$$ C_n = \frac{1}{n+1} \binom{2n}{n} $$
我们从中取出的第 n 项,就叫做第 n 个 Catalan 数。前几个 Catalan 数是:1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, … 乍看之下似乎没什么特别的,但 Catalan 数却是许多计数问题的最终形式。
Catalan 数的一些性质
Catalan 数的基本公式如上所示,但在实际应用中,还有一些变形和具体的性质值得注意:
- 递推关系:根据原来的式子推导,可以得到 $C_{n+1} = \sum_{i=0}^{n} C_i C_{n-i}$。这是最经典的递归结构。
- 另一种递推式:$C_{n+1} = \frac{2(2n+1)}{n+2} C_n$。这个递推式很容易从原来的式子中获得,适合编程计算。
- 生成函数:设 $C(x) = \sum_{n=0}^{\infty} C_n x^n$,则满足 $C(x) = 1 + x C(x)^2$。
- 渐近增长:当 n 趋于无穷大时,$C_n \sim \frac{4^n}{n^{3/2} \sqrt{\pi}}$。这反映了 Catalan 数的增长趋势。
Catalan 数在组合计算中的应用
在组合数学中,Catalan 数由一个应用推导出的公式,其具体的描述如下:n 个 +1 和 n 个 -1 构成 2n 项序列,其部分和满足 $S_k \ge 0$ 的序列个数等于第 n 个 Catalan 数。
其证明思路并不复杂。我们假设不满足条件的序列个数为 $N$,那么就有 $N = \binom{2n}{n-1}$。剩下的工作就是求合法序列数,即总数减去非法数。我们假设有一个最小的 k 令 $S_k < 0$。由于这里 k 是最小的,所以必有 $S_{k-1} = 0$,并且 k 是一个奇数。此时我们将前 k 项中的 +1 变为 -1,将 -1 变为 +1,那么就得到一个有 (n+1) 个 +1 和 (n-1) 个 -1 的序列了。这样的序列个数就是我们要求的非法数,数值大小为 $\binom{2n}{n-1}$。那么我们就得到了合法序列数为 $\binom{2n}{n} - \binom{2n}{n-1} = C_n$。
在具体的组合数问题中,很多都可以转换为 Catalan 数进行最后的计算,常见的场景包括:
- 合法括号表达式:对于任意的 k,前 k 个元素中 -1 的个数小于等于 +1 的个数的序列计数。我们可以不停地变换形式,比如将 -1 看成右括号,+1 看成左括号,就变成了合法括号表达式的个数。比如 2 个左括号和 2 个右括号组成的合法表达式有 2 种,是 ()() 和 (())。
- 矩阵连乘顺序:n+1 个数连乘,乘法顺序有 $C_n$ 种。比如三个数连乘 abc,那么等于在式子上加括号,有 2 种乘法顺序,分别是 (ab)c 和 a(bc)。对应关系比较模糊,我们取 n 为 3 来看看,n 为 3 的时候就是 4 个数相乘了,那么我们设为 abcd,最初的标号定在 a 上,我们对于 n 为 3 得到合法的括号序列有 5 个,分别是:((())),()(()),()()(),(())() 和 (()()),那么我们将一个左括号看成是当前操作数指针往右移动一个位置,一个右括号看成是当前操作数和左边最近的一块操作数相乘起来,那么对应的五个表达式就是:a(b(cd)),(ab)(cd),((ab)c)d,(a(bc))d 和 a((bc)d),他们之间是一一对应关系。
- 二叉树形态:n 个节点的二叉树的所有可能形态数为 $C_n$。这一点很容易证明,我们考虑随便取一个节点作为根,那么他左边和右边的儿子节点个数就确定了。假定根节点标号为 x,那么左子树的标号就从 1 到 x-1,共 x-1 个,右子树的标号就从 x+1 到 n,共 n-x 个,那么我们的 x 从 1 取到 n,就获得了所有的情况数 $\sum_{x=1}^{n} C_{x-1} C_{n-x} = C_n$。这个式子就是我们性质 3 的式子。
- 满二叉树形态:n 个非叶节点的满二叉树的形态数(对称后得到的二叉树除非自己本身对称,否则算是不同)。这里要求满二叉树,实际上就是在上一点的每个子节点的空儿子上都加上叶子,就形成了我们的图了,那么我们要求的结果就是 Catalan 数。
- 网格路径:对于一个 n*n 的正方形网格,每次我们能向右或者向上移动一格,那么从左下角到右上角的所有在副对角线右下方的路径总数为 $C_n$。我们将一条水平边记为 +1,垂直边记为 -1,那么就组成了一个 n 个 +1 和 n 个 -1 的序列,我们所要保证的就是前 k 步中水平边的个数不小于垂直边的个数,换句话说前 k 个元素的和非负,就是我们关于 Catalan 数的定义。
- 多边形三角剖分:凸 n+2 边形进行三角形分割(只连接顶点对形成 n 个三角形)数为 $C_n$。


