卡特兰数折线法.pptm

一个通用的问题：

一个由 $n$ 个 1 和 $n$ 个 -1 组成的字符串，要求对于任意 k，前 k 个数的和均不小于 0。求符合条件的不同的字符串的总数。

1 和 -1 可以映射成二维坐标系中的两个操作：

• 往右上角 $45^{\circ }$ 走一个单位(长度为 $\sqrt{2}$)，记为第一种操作。
• 往右下角 $45^{\circ }$ 走一个单位(长度为 $\sqrt{2}$)，记为第二种操作。

那么，我们只需要保证，在从 (0, 0) 抵达 (2n ,0) 之间的任意一个中间点。都要满足往右上走的次数大于等于往右下走的次数。

这在坐标轴中表现为：走出来的折线不能跨越 x 轴。

首先，我们可以得出：

• 如果我们不考虑跨越 x 轴的限制，折线的种数将为 $C(2n, n)$

然后，现在只需要减去跨越了 x 轴的种数，就可以得到所有的合法的折线的种数。

那么，跨越了 x 轴的不合法的折线的种数是多少呢？

考虑到一旦跨越了 x 轴，折线必然经过 y = -1 这条线。也就是说，对于任意跨越 x 轴的情况，折线必然与 y = -1 相交。找出第一个与 y = -1 相交的点 k，将 k 点以右的折线根据 y = -1 进行对称，对称后终点将会从 (2n, 0) 来到 (2n, -2)，由于对称总是可以进行的，并且是可逆的，由此，不合法的折线的种数就可以转化为：从 (0, 0) 到 (2n, -2) 的折线种数。可以发现，从 (0, 0) 到 (2n, -2) 的折线包含了 n - 1 个第一种操作以及 n + 1 个第二种操作，因为这样才能保证终点的 y 坐标是 -2。于是，可以得出：

• 跨越 x 轴的折线的种数为 $C(2n, n - 1)$

因此，卡特兰数的结果为：

$$ C(2n,n) - C(2n, n-1) = C(2n,n) / (n+1) $$

参考：