Catalan 数列及其应用

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

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

带限制条件的路径总数

首先我们来看一个问题:

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

450px-Catalan_number_4x4_grid_example.svg

如果没有限制条件,那么从左下角走到右上角一共有 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 数

(more…)

Read More