Catalan 数列及其应用

卡特兰数（Catalan number）是组合数学中一个重要的计数数列，在很多看似毫不相关地方都能见到它的身影

这篇文章介绍卡特兰数的几个应用以及它的推导过程，从组合推理和生成函数两个方面来推导出 Catalan 数的公式

带限制条件的路径总数

首先我们来看一个问题：

在一个平面直角坐标系中，只能往右或往上走一个单位长度，问有多少种不同的路径可以从左下角 $(1, 1)$ 走到右上角 $(n, n)$，并且要求路径不能经过直线 $y = x$ 上方的点，下图中的路径都是合法的（图片来源 Wikipedia）

如果没有限制条件，那么从左下角走到右上角一共有 $2n$ 步，有 $n$ 步是往右，另外 $n$ 步是往上，那么路径方案数就是 $2n$ 步中选择 $n$ 步往右，一共有 ${2n} \choose {n}$ （即 $C_{2n}^n$）种方案

那么我们考虑一下这里面有多少种方案是不合法的

首先对于每一种不合法的方案，它的路径一定与 $y = x + 1$ 有交。我们找到它与 $y = x + 1$ 的第一个交点，然后将这个点后面部分的路径关于 $y = x + 1$ 做一个对称。由于原来路径到达 $(n, n)$，新的对称之后的路径就会到达 $(n - 1, n + 1)$。这样我们把每一种不合法方案都对应到了一条从 $(1, 1)$ 到 $(n - 1, n + 1)$ 的路径，现在再来看是否每一条这样的路径都能对应到一种不合法方案，如果是，那么这就建立了一个一一映射的关系，也就是它们的方案总数相同。这是肯定的，因为每一条这样的路径必定与 $y = x + 1$ 有交，那么对称回去，就得到一条不合法方案

由于从 $(1, 1)$ 到 $(n - 1, n + 1)$ 的路径有 ${n - 1 + n + 1} \choose {n - 1}$ 条，那么合法的方案就是

\[C_n = { {2n} \choose {n} } - { {2n} \choose {n - 1} } = \frac{1}{n + 1} { {2n} \choose {n} }\]

我们把这个方案数记为 $C_n$，这就是著名的 Catalan 数

我们来看看它的前几项（$n$ 从 $0$ 开始）

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190

括号序列计数

再来看一个问题：有多少种不同的长度为 $n$ 的括号序列？

首先一个括号序列是指 (), ()(), (())() 这样的由括号组成的序列，并且没有左右括号无法匹配的情况

我们可以将长度为 $2n$ 的括号序列映射成刚刚所说的路径：首先对于左括号，那么就向右走一个单位长度，对于右括号，那么就向上走一个单位长度，由于括号序列合法，那么每次向右走的次数不会少于向上的次数，也就是这条路径不会在 $y = x$ 之上。再考虑每一条这样的路径，也能够对应到一种合法的括号序列，因此，长度为 $2n$ 的括号序列的方案数就是 $C_n$

出栈顺序

现在来考虑你有 $n$ 个元素（元素之间是没有区别的）和一个栈，每次可以将一个元素入栈，或者将栈顶元素弹出，问有多少种可能的操作序列，这可以将问题对应成括号序列，入栈为左括号，出栈为右括号，因此方案数也是 $C_n$

排队问题

现在有 $2n$ 个人，他们身高互不相同，他们要成两排，每一排有 $n$ 个人，并且满足每一排必须是从矮到高，且后一排的人要比前一排对应的人要高，问有多少种排法

我们考虑先把这些人从矮到高排成一排，那么现在来分配哪个人在前，哪个人在后，例如有 $6$ 个人，身高是 1, 2, 3, 4, 5, 6

那么我们用 1 表示这个人应该在后排，0 表示这个人应该在前排，例如说 100110 表示两排分别是 2, 3, 6 和 1, 4, 5 这是不合法的

那么合法方案应该是怎么样的呢？后排要比前排对应的人高，也就是说 0 的出现次数在每一个地方都不应该小于 1，这恰恰又是一个括号序列，因此，方案仍然是 Catalan 数

二叉树计数

现在你需要统计有多少种不同的 $n$ 个结点的二叉树

图上的是 $3$ 个结点的二叉树，一共有 $5$ 种方案

朴素的想法是由于二叉树是递归定义的，可以考虑使用递推方法

我们可以用 $f_n$ 表示有 $n$ 个结点的二叉树的方案数（空树算一种，即 $f_0 = 0$），那么枚举子树大小可以得到方程

\[f_n = \sum_{i = 0}^{n - 1} f_if_{n - i - 1}\]

如果直接计算，你需要 $\mathcal O(n^2)$ 的时间

现在我们换一个角度来想，对这棵二叉树进行遍历，并且考虑一个括号序列，当第一次遇到这个结点的时候，在括号序列末尾添加一个左括号，在从左子树回到这个结点的时候，在括号序列中添加一个右括号，这样，将每一种不同的二叉树都对应到了一种不同的括号序列，同样对于每一种不同的括号序列都可以找到对应的一种不同的二叉树，因此，有 $n$ 个结点的二叉树的数量也是 $C_n$

生成函数的证明

我们可以定义序列 $C_n$ 的生成函数为 $C(z)$，再根据上面的递推式，可以列出方程

\[C(z) = zC^2(z) + 1\]

解方程可以得到

\[C(z) = \frac{1 \pm \sqrt{1 - 4z} }{2z}\]

因为 $C(0) = C_0 = 1$，因此对上式求极限

\[\begin{eqnarray*} \lim_{z \rightarrow 0^+} \frac{1 + \sqrt{1 - 4z} }{2z} &=& +\infty \\ \lim_{z \rightarrow 0^+} \frac{1 - \sqrt{1 - 4z} }{2z} &=& 1 \end{eqnarray*}\]

因此取负号，$C(z) = \frac{1 - \sqrt{1 - 4z} }{2z}$

根据广义二项式定理展开 $\sqrt{1 - 4z}$

\[\sqrt{1-4z} = \left (1-4z \right )^{\frac{1}{2} } = \sum_{i=0}^{\infty}{\frac{1}{2} \choose i}(-4z)^i\]

然后考虑第 $n$ 项系数

\[\begin{eqnarray*} & &(-4)^n { \frac{1}{2} \choose n }\\ &=& (-4)^n \frac{\frac{1}{2}\cdot \left( \frac{1}{2} -1 \right)\cdot \left( \frac{1}{2} -2 \right)\cdots \left( \frac{1}{2} - n + 1 \right)}{1\cdot2\cdot3\cdots n}\\ &=& (-2)^n \frac{1\cdot (1-2)\cdot (1-4)\cdots (1 - 2n + 2)}{1\cdot2\cdot3\cdots n}\\ &=& (-2)^n \frac{1\cdot (1-2)\cdot (1-4)\cdots (1 - 2n + 2)}{1\cdot2\cdot3\cdots n}\\ &=& -\frac{1\cdot 3\cdot 5\cdots (2n - 3)}{1\cdot2\cdot3\cdots n}\cdot \frac{1\cdot 2\cdot 4\cdots 2n}{1\cdot 2 \cdot 3 \cdots n}\\ &=& -\frac{(2n)!}{(2n-1)(n!)^2}\\ &=& -\frac{1}{2n-1}{ {2n} \choose n} \end{eqnarray*}\]

因此可以得到

\[\begin{eqnarray*} C(z) &=& \frac{1-\sqrt{1-4z} }{2z}\\ &=&\frac{1+\sum_{i=0}^{\infty}\frac{1}{2i-1}{ {2i} \choose i} z^i}{2z}\\ &=&\frac{\sum_{i=1}^{\infty}\frac{1}{2i-1}{ {2i} \choose i} z^{i-1} }{2}\\ &=&\sum_{i=0}^{\infty}\frac{2}{2i+1}{ {2i+2} \choose {i+1} } z^i\\ &=&\sum_{i=0}^{\infty}\frac{1}{2}\cdot\frac{1}{2i+1}\cdot\frac{(2i+1)(2i+2)}{(i+1)^2}{ {2i} \choose i} z^i\\ &=&\sum_{i=0}^{\infty}\frac{1}{n+1}{ {2i} \choose i} z^i\\ \end{eqnarray*}\]

同样得到 $C_n = \frac{1}{n+1}{ {2n} \choose n}$