卡特兰数为什么是这样的

卡特兰数第 $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$ 的定义就是这个。

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

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

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

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

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

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

简单解释一下为什么：

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

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

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

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

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

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

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

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

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

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

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

例如这一串： $（（（（（）））））））（（$

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

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

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

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

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

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

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

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

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

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

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

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

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

没错！这是卡特兰数列！

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

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