什么是 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$。
