Catalan 数

简介

卡特兰数(Catalan Number)，又称明安图数，是组合数学中一种常出现于各种计数问题中的数列。以比利时数学家欧仁·查理·卡特兰的名字命名。1730年，清代蒙古族数学家明安图在对三角函数幂级数的推导过程中首次发现，1774年被发表在《割圜密率捷法》。
若记 $h (n)$ 为卡特兰数的第 $n$ 项，且令 $h (0) = 1$ ，则有：

h (n) = \sum_{i = 0}^{n - 1} h (i) \cdot h (n - 1 - i)

卡特兰数的第0到第15项： $h (0) = 1$ , $h (1) = 1$ , $h (2) = 2$ , $h (3) = 5$ , $h (4) = 14$ , $h (5) = 42$ , $h (6) = 132$ , $h (7) = 429$ , $h (8) = 1430$ , $h (9) = 4862$ , $h (10) = 16796$ , $h (11) = 58786$ , $h (12) = 208012$ , $h (13) = 742900$ , $h (14) = 2674440$ , $h (15) = 9694845$ 。

Catalan数的递推关系

Catalan数的递推关系为：

h (n) = \sum_{i = 0}^{n - 1} h (i) \cdot h (n - 1 - i)

(n - 3) h (n) = \frac{n}{2} \sum_{i = 3}^{n - 1} h (i) \cdot h (n + 2 - i)

h (n) = h (n - 1) \cdot \frac{4 n - 2}{n + 1}

Catalan数的递推关系的解（Lobb公式）：

h (n) = \frac{1}{n + 1} (\binom{2 n}{n}) = \frac{(2 n)!}{n! (n + 1)!}

h (n) = (\binom{2 n}{n}) - (\binom{2 n}{n + 1})

Catalan公式的推导

卡特兰数的递推式为

H_{n} = \sum_{i = 0}^{n - 1} H_{i} H_{n - i - 1} (n \geq 2)

其中 $H_{0} = 1, H_{1} = 1$ 。设它的普通生成函数为 $H (x)$ 。

我们发现卡特兰数的递推式与卷积的形式很相似，因此我们用卷积来构造关于 $H (x)$ 的方程：

\begin{aligned} H (x) & = \sum_{n \geq 0} H_{n} x^{n} \\ = 1 + \sum_{n \geq 1} \sum_{i = 0}^{n - 1} H_{i} x^{i} H_{n - i - 1} x^{n - i - 1} x \\ = 1 + x \sum_{i \geq 0} H_{i} x^{i} \sum_{n \geq 0} H_{n} x^{n} \\ = 1 + x H^{2} (x) \end{aligned}

解得

H (x) = \frac{1 \pm \sqrt{1 - 4 x}}{2 x}

那么这就产生了一个问题：我们应该取哪一个根呢？我们将其分子有理化：

H (x) = \frac{2}{1 \mp \sqrt{1 - 4 x}}

代入 $x = 0$ ，我们得到的是 $H (x)$ 的常数项，也就是 $H_{0}$ 。当 $H (x) = \frac{2}{1 + \sqrt{1 - 4 x}}$ 的时候有 $H (0) = 1$ ，满足要求。而另一个解会出现分母为 $0$ 的情况（不收敛），舍弃。

因此我们得到了卡特兰数生成函数的封闭形式：

H (x) = \frac{1 - \sqrt{1 - 4 x}}{2 x}

接下来我们要将其展开。但注意到它的分母不是斐波那契数列那样的多项式形式，因此不方便套用等比数列的展开形式。在这里我们需要使用牛顿二项式定理。我们来先展开 $\sqrt{1 - 4 x}$ ：

\begin{aligned} (1 - 4 x)^{\frac{1}{2}} & = \sum_{n \geq 0} (\binom{\frac{1}{2}}{n}) (- 4 x)^{n} \\ = 1 + \sum_{n \geq 1} \frac{{(\frac{1}{2})}^{\underset{―}{n}}}{n!} (- 4 x)^{n} \end{aligned}

注意到

\begin{aligned} {(\frac{1}{2})}^{\underset{―}{n}} & = \frac{1}{2} \frac{- 1}{2} \frac{- 3}{2} \dots \frac{- (2 n - 3)}{2} \\ = \frac{(- 1)^{n - 1} (2 n - 3)!!}{2^{n}} \\ = \frac{(- 1)^{n - 1} (2 n - 2)!}{2^{n} (2 n - 2)!!} \\ = \frac{(- 1)^{n - 1} (2 n - 2)!}{2^{2 n - 1} (n - 1)!} \end{aligned}

这里使用了双阶乘的化简技巧。那么带回 $(1)$ 得到

\begin{aligned} (1 - 4 x)^{\frac{1}{2}} & = 1 + \sum_{n \geq 1} \frac{(- 1)^{n - 1} (2 n - 2)!}{2^{2 n - 1} (n - 1)! n!} (- 4 x)^{n} \\ = 1 - \sum_{n \geq 1} \frac{(2 n - 2)!}{(n - 1)! n!} 2 x^{n} \\ = 1 - \sum_{n \geq 1} (\binom{2 n - 1}{n}) \frac{1}{(2 n - 1)} 2 x^{n} \end{aligned}

带回原式得到

\begin{aligned} H (x) & = \frac{1 - \sqrt{1 - 4 x}}{2 x} \\ = \frac{1}{2 x} \sum_{n \geq 1} (\binom{2 n - 1}{n}) \frac{1}{(2 n - 1)} 2 x^{n} \\ = \sum_{n \geq 1} (\binom{2 n - 1}{n}) \frac{1}{(2 n - 1)} x^{n - 1} \\ = \sum_{n \geq 0} (\binom{2 n + 1}{n + 1}) \frac{1}{(2 n + 1)} x^{n} \\ = \sum_{n \geq 0} (\binom{2 n}{n}) \frac{1}{n + 1} x^{n} \end{aligned}

这样我们就得到了卡特兰数的通项公式。

Catalan数的应用

括号匹配问题：给定 $n$ 对括号，求出所有合法的括号序列的个数。

思路： $n$ 对括号相当于有 $2 n$ 个符号， $n$ 个左括号、 $n$ 个右括号，可以设问题的解为 $f (2 n)$ 。第0个符号肯定为左括号，与之匹配的右括号必须为第 $2 i + 1$ 字符。（因为如果是第2i个字符，那么第0个字符与第2i个字符间包含奇数个字符，而奇数个字符是无法构成匹配的。）
通过简单分析， $f (2 n)$ 可以转化如下的递推式：
$f (2 n) = f (0) \cdot f (2 n - 2) + f (2) \cdot f (2 n - 4) + \dots + f (2 n - 4) \cdot f (2) + f (2 n - 2) \cdot f (0)$
$f (0) \cdot f (2 n - 2)$ 表示第0个字符与第1个字符匹配，同时剩余字符分成两个部分，一部分为0个字符，另一部分为 $2 n - 2$ 个字符，然后对这两部分求解。 $f (2) \cdot f (2 n - 4)$ 表示第0个字符与第3个字符匹配，同时剩余字符分成两个部分，一部分为2个字符，另一部分为 $2 n - 4$ 个字符。依次类推。
假设f(0) = 1，则有 $f (2 n) = h (n)$ 。

（变种）买票找零问题：有 $2 n$ 个人排成一行进入剧场。入场费5元。其中只有 $n$ 个人有一张5元钞票，另外 $n$ 人只有10元钞票，剧院无其它钞票，问有多少中方法使得只要有10元的人买票，售票处就有5元的钞票找零？

思路：令拿较小钞票的人代表上题中的左括号，而拿较大钞票的人代表上题中的右括号。记此时的情况有 $M$ 种，则有 $M = h (n)$ 。（题目限制售票员一定能够找开零钱，故不能反过来写）

（变种）栈的进出栈序列问题：给定 $n$ 个元素的进栈（出栈）序列，求出所有可能的进栈（出栈）序列的个数。

思路：令进栈操作代表第一题中的左括号，出栈操作代表第一题中的右括号。（不能再栈已空的时候继续出栈。）记此时的情况有 $M$ 种，则有 $M = h (n)$ 。

（变种）圆桌握手问题：在圆上选择 $2 n$ 个点，将其两两连接，求出所有不相交的弦的方案数。

思路：以其中一个点为基点，编号为0，然后按顺时针方向将其他点依次编号。那么与编号为0相连点的编号一定是奇数，否则，这两个编号间含有奇数个点，势必会有个点被孤立，即在一条线段的两侧分别有一个孤立点，从而导致两线段相交。设选中的基点为A，与它连接的点为B，那么A和B将所有点分成两个部分，一部分位于A、B的左边，另一部分位于A、B的右边。然后分别对这两部分求解即可。
设问题的解为 $f (n)$ ，则有
$f (n) = \sum_{i = 0}^{n - 1} f (i) \cdot f (n - 1 - i)$
其中， $f (i) \cdot f (n - i - 1)$ 表示编号0的点与编号1的点相连，此时位于它们右边的点的个数为0(可以连成0条线段)，而位于它们左边的点为2n-2（可以连成n-1条线段）。
若令 $f (0) = 1, f (1) = 1, f (2) = 2$ ，则 $f (n) = h (n)$ 。

凸多边形三角划分问题：给定 $n$ 边凸多边形，求出所有不相交的三角形的划分方案数。

思路：以凸多边形的一边为基，设这条边的2个顶点为 $A, B$ 。从剩余顶点中选1个，可以将凸多边形分成三个部分，中间是一个三角形，左右两边分别是两个凸多边形，然后求解左右两个凸多边形。
设问题的解为 $f (n)$ ，其中 $n$ 表示顶点数，那么有
$f (n) = f (2) \cdot f (n - 1) + f (3) \cdot f (n - 2) + \dots + f (n - 2) \cdot f (3) + f (n - 1) \cdot f (2)$
其中， $f (i) \cdot f (n + 1 - i)$ 表示三个相邻的顶点构成一个三角形，那么另外两个部分的顶点数分别为 $i, n + 1 - i$ 。
若 $f (2) = 1$ ，则有 $f (n) = h (n - 2)$ 。

路径计数问题：从 (0,0) 到 (n,n) 的除端点外不穿过（不接触）直线 $y = x$ 的非降路径数。

思路：非降路径是指只能向上或向右走的路径。
从 $(0, 0)$ 到 $(m, n)$ 的非降路径数等于 $m$ 个 $x$ 和 $n$ 个 $y$ 的排列数，即 $(\binom{n + m}{m})$ 。
从 $(0, 0)$ 到 $(n, n)$ 的除端点外不接触直线 $y = x$ 的非降路径数：
先考虑 $y = x$ 下方的路径，都是从 $(0, 0)$ 出发，经过 $(1, 0)$ 及 $(n, n - 1)$ 到 $(n, n)$ ，可以看做是 $(1, 0)$ 到 $(n, n - 1)$ 不接触 $y = x$ 的非降路径数。
所有的的非降路径有 $(\binom{2 n - 2}{n - 1})$ 条。对于这里面任意一条接触了 $y = x$ 的路径，可以把它最后离开这条线的点到 $(1, 0)$ 之间的部分关于 $y = x$ 对称变换，就得到从 $(0, 1)$ 到 $(n, n - 1)$ 的一条非降路径。反之也成立。从而 $y = x$ 下方的非降路径数是 $(\binom{2 n - 2}{n - 1}) - (\binom{2 n - 2}{n})$ 。根据对称性可知所求答案为 $2 (\binom{2 n - 2}{n - 1}) - 2 (\binom{2 n - 2}{n})$ 。
从 $(0, 0)$ 到 $(n, n)$ 的除端点外不穿过直线 $y = x$ 的非降路径数：（这里是分为左上和右下两部分，所以答案要乘以2）
用类似的方法可以得到： $\frac{2}{n + 1} (\binom{2 n}{n})$

二叉树的计数问题：给定 $n$ 个节点，求出所有不同的二叉树的个数

推导：将n个互异节点组成的二分查找树的总数记为 $T (n)$ 。尽管由同一组节点组成的二叉搜索树不尽相同，但它们的中序遍历序列却必然相同，不妨记作：
$[x_{0}, x_{1}, \dots, x_{k - 1}], x_{k}, [x_{k + 1}, \dots, x_{n - 1}]$
根据所取的树根节点不同，所有的搜索树可以分为 $n$ 类。如果以 $x_{k}$ 为根节点，则其左右子树见上。
对应的递推关系如下：
$T (0) = T (1) = 1, T (n) = \sum_{k = 0}^{n - 1} T (k) \cdot T (n - k - 1)$
（边界条件很好理解，而递推式可以以减治的方式进行理解：对于某一棵BST，其由左、右两个子树和根节点组成。因为中序序列确定，所以它们三者的排序方式不会改变，即依然是左子树——根节点——右子树组成。于是，问题转化成求 $T (L), T (R)$ ，其中， $L, R$ 分别是构成这两棵子树的元素总个数，且 $n = L + R + 1$ 。同时，根据乘法原理，可以推出递推式。）
这是典型的Catalan数式递推关系，解之即得题中结论。

Catalan 数 ​

简介 ​

Catalan数的递推关系 ​

Catalan公式的推导 ​

Catalan数的应用 ​

参考资料 ​

Catalan 数

简介

Catalan数的递推关系

Catalan公式的推导

Catalan数的应用

参考资料