卡特兰数为什么是这样的

· · 算法·理论

背景

卡特兰数第 n 项记为 H_n，根据学过的知识，H_n = C_{2n} ^ n - C_{2n} ^ {n - 1}。

可是这是怎么推出来的呢？

思考

一个二维表（如下），从 (0, 0) 点，每一步只能向上或向右走一格，走到 (n, n) 点的方案数是多少？

对于本蒟蒻来说，首先想到的就是动态规划了。

具体来说，dp_{i, j} 表示从 (0, 0) 到 (i, j) 的方案数是多少。

对于每一 (i, j) 来说，它要么是从下面走过来的，要么是从左边走过来的。所以状态转移方程：dp_{i, j} \gets dp_{i - 1, j} + dp_{i, j - 1}。

那很明显了，初始化所有 dp_{i, 0} 和 dp_{0, j} 和 dp_{0, 0}。

显然，dp_{0, 0} = 1，因为刚开始就在 (0, 0) 点。

同样，dp_{i, 0} = 1 且 dp_{0, j} = 1。

好的，我们现在换一种思路：

从 (0, 0) 开始，每次操作可以抽象为向右 \rightarrow 和向上 \uparrow 操作。

那么，从 (0, 0) 走到 (n, n)，就需要有 n 个 \rightarrow 操作和 n 个 \uparrow 操作。

那么，这个问题就抽象为，2n 个位置，选出其中 n 个 \rightarrow 和 n 个 \uparrow 的方案数。

这个问题的答案明显就是 C_{2n} ^ n。因为 C_{2n} ^ n 的定义就是这个。

好的，恭喜你成功的看到了这里，打败了 50\% 的人，扣个 1。

现在这个问题变了一下，从 (n, n) 到 (0, 0) 拉一条直线，这条直线一下的区域（不包括这条线上的点）是危险区域（红色区域，如下图），不可以去那里玩。请问这样有多少种路径从 (0, 0) 到 (n, n) 呢？

组合数学，正难则反。先不考虑有红色区域，方案数就是 C_{2n} ^ n。

那涉足红色区域的方案数又有多少呢？

当某个路径第一次涉足红色区域时，一定是从某个点 (k, k) 向右走到的点。换言之，这个点是从左边走来，不可能是从下面走来。

我们把这个点之后的所有操作全部取反（\rightarrow 变 \uparrow，\uparrow 变 \rightarrow）。

如上图，J 点是第一次涉足的位置，蓝线是原本的路径，绿色线是取反后的路径。

一定的，取反后的路径的目的地是 (n - 1, n + 1)。

简单解释一下为什么：

第一次涉足下方的点一定是第一次出现 \rightarrow 比 \uparrow 的点多一个的位置，所以原本路径后面的 \rightarrow 会比 \uparrow 少一。所以取反之后，整个路径里 \rightarrow 会比 \uparrow 多二，所以会出现高度减一而长度加一的情况。

而每一个涉足下面区域的路径，都一定对应一个取反后的路径到达 (n + 1, n - 1) 的路径。

所以所有涉足下面区域的路径，方案数为 C_{2n} ^ {n - 1}。

所以所有合法的方案数就是 C_{2n} ^ n - C_{2n} ^ {n - 1}。

并且这个问题是卡特兰数的一个经典问题。

好的，短暂的回顾一下上面的推导过程。

拓展

好的，恭喜你成功的看到了这里，打败了 75\% 的人，扣个 2。

卡特兰数还有其他的应用，例如下面这个经典问题：

你有 n 个 “（” 和 n 个 “）”，你能组成多少种合法的括号序列？

（合法：指任意前缀中，左括号的数量都不少于右括号的数量，并且最终左右括号数量相等）。

先别管“合法”，先考虑 n 个 “（” 和 n 个 “）”有多少种方案。

答案很明显了，C_{2n} ^ n。

好的，现在考虑不合法的。

例如这一串：

（（（（（）））））））（（

第一次出现问题的地方是第十一个字符，其 1 \sim 11 的序“）”比“（”多一个。

从第十二个字符开始，每一个括号反转（同格点图，“（”变“）”，“）”变“）”）。

序列变为：（（（（（））））））\color{red}（））。

其中，反转之后，“）”就会有 n + 1 个，比“（”多两个。

而每一个不合法序列都可以对应一个 n + 1 个 “）”，n - 1 个“（”的序列，所以合法的序列有 C_{2n} ^ n - C_{2n} ^ {n - 1} 个。

好的，恭喜你成功的看到了这里，打败了 83\% 的人，扣个 5。

你可能会疑惑，1、2 之后为什么是 5？

来，总结一下它俩都有什么共同点？

没错，都是抽象操作后去找零界点然后反转。

那相信聪明的你也知道了这个问题：

假设有一个无穷大的栈，我们进行 n 次入栈（Push）操作和 n 次出栈（Pop）操作。

问题是：有多少种不同的操作顺序，使得在操作的任何时刻，都不会因为试图从一个空栈中弹出元素而导致操作失败？

这种合法的操作序列的数量，就是第 n 个卡特兰数 H_n。

提示：把入栈相乘 \rightarrow，出栈想成 \uparrow，其中每次操作变成一个序列。

每个前缀里，\rightarrow 不能少于 \uparrow，否则就像涉足了格点图里的红色区域，这样的序列需要扣除，具体方法就是括号匹配问题了。

好的，恭喜你成功的看到了这里，打败了 90\% 的人，扣个 14。

没错！这是卡特兰数列！

总结

今天突然想到了这个东西，写下来记录一下，也顺便给一些不懂的人提一下卡特兰数的推导。

其实卡特兰数还有二叉树的序列问题，时间关系，后面再讲。