Catalan 数

Catalan 数

真的不知道怎么开头。

学习 Catalan 数先从其定义入手。

\(f_i\) 是卡特兰数第 \(i\) 项，令 \(f_0 = 1\)

递归式： \(f_i = \sum_{j = 0}^{i - 1} f_j \times f_{i - j - 1}\)

递推式：$f_{i+1} = f_i \times \frac{2 \times (2i + 1)}{i+2} $

化简可以得到：\(f_i = C_{2i}^{i} - C_{2i}^{n - 1}\)

根据递归式，可以知道卡特兰数在描述：当我们可以对一个问题进行划分，得到两个子问题， 并且两个子问题互不影响。

经典例题：凸多边形的三角划分

我们用若干条线连接 \(n\) 边形的两个顶点，线和线之间不可以相交，最后划分成若干个三角形，问划分方案的数量。

我们在初中就学习了这个东西。但本质上就是划分，先来一刀，划分成两个小的凸多边形。枚举划分后左边有多少个顶点，再把两个小凸多边形的方案数乘起来。

得到递归式：\(f_i = \sum_{j = 0}^{i - 1} f_j \times f_{i - j - 1}\)

一模一样。

二叉树的方案数

\(n\) 个点的二叉树有多少种。区分左儿子和右儿子，即把左右儿子直接交换也算新的。

二叉树也是非常经典的划分成两块的问题。所有还是枚举左儿子节点数，直接列出递归式。

\(f_i = \sum_{j = 0}^{i - 1} f_j \times f_{i - j - 1}\)

一模一样。

上述问题都是根据递归式来的。我们接下来讲一下：\(f_i = C_{2i}^{i} - C_{2i}^{i - 1}\)

二维平面路径问题

在一个二维平面坐标系上从 \((0,0)\) 到 \((n,n)\)，每次只可以先上走一步，或向右走一步，问有多少条路线。有唯一要求，走过的点必须在直线 \(y =x\) 下，即在任意时刻向上走的次数必须小于等于向右走的次数。

去掉唯一条件，就是用 \(n\) 个向上，\(n\) 个向右，问这 \(2n\) 个操作的所有排列。我们易得，在全是向上走的序列中，选 \(n\) 个出来变成向右。

考虑不合法路径，对任意一个不合法路径沿着直线 \(y = x + 1\) 镜像，所有不和法路径都到了这条线，且只有不和法路径到了这条线。镜像后终点变成了 \((n - 1,n+1)\) ，我们可以将不合法路径按上述方法一一映射成从 \((0,0)\) 到 \((n - 1,n + 1)\) 的路径，一共还是有 \(2n\) 个操作，只不过是选 \(n - 1\) 个当向右。

最后得到式子：\(f_i = C_{2i}^{i} - C_{2i}^{i - 1}\)

不相交弦问题

一个圆周上有 \(2n\) 个点，用弦将任意两个链接起来，使得任意两条线不相交。

我们将线改写成一个起点，一个终点。钦定起点和顺时针遇到的第一个终点连成一条线。我们可以做到一个一一映射。

还是从可以相交的角度考虑，易得共有 \(C_{2i}^{i}\) 种方案。

不合法的情况一定是一个终点没得连，就是前面的起点全被匹配了，所以还是和上述的 二维平面路径问题 一样，即任意时刻起点的数量一定大于终点的数量。

最后得到：\(f_i = C_{2i}^{i} - C_{2i}^{i - 1}\)

More

卡特兰数在到处都存在：括号序列的数量，进栈出栈，312 排列…理解到其本质就是对问题的划分，选取发生事件方案进行一一映射。其实就很简单了。