跳转至

卡特兰数

Catalan 数列

Catalan 数列 可以应用于以下问题：

  1. 有 个人排成一行进入剧场。入场费 5 元。其中只有 个人有一张 5 元钞票，另外 人只有 10 元钞票，剧院无其它钞票，问有多少种方法使得只要有 10 元的人买票，售票处就有 5 元的钞票找零？
  2. 有一个大小为 的方格图左下角为 右上角为 ，从左下角开始每次都只能向右或者向上走一单位，不走到对角线 上方（但可以触碰）的情况下到达右上角有多少可能的路径？
  3. 在圆上选择 个点，将这些点成对连接起来使得所得到的 条线段不相交的方法数？
  4. 对角线不相交的情况下，将一个凸多边形区域分成三角形区域的方法数？
  5. 一个栈（无穷大）的进栈序列为 有多少个不同的出栈序列？
  6. 个结点可构造多少个不同的二叉树？
  7. 由 个 和 个 组成的 个数 ，其部分和满足 ，有多少个满足条件的数列？

其对应的序列为：

…
1 1 2 5 14 42 132 …

递推式

该递推关系的解为：

关于 Catalan 数的常见公式：

例题 洛谷 P1044 栈

题目大意：入栈顺序为 ，求所有可能的出栈顺序的总数。

#include <iostream>
using namespace std;
int n;
long long f[25];

int main() {
  f[0] = 1;
  cin >> n;
  for (int i = 1; i <= n; i++) f[i] = f[i - 1] * (4 * i - 2) / (i + 1);
  // 这里用的是常见公式2
  cout << f[n] << endl;
  return 0;
}

f = [0] * 25
f[0] = 1
n = int(input())
for i in range(1, n + 1):
    f[i] = int(f[i - 1] * (4 * i - 2) // (i + 1))
    # 这里用的是常见公式2
print(f[n])

封闭形式

卡特兰数的递推式为

其中 。设它的普通生成函数为 。

我们发现卡特兰数的递推式与卷积的形式很相似，因此我们用卷积来构造关于 的方程：

解得

那么这就产生了一个问题：我们应该取哪一个根呢？我们将其分子有理化：

代入 ，我们得到的是 的常数项，也就是 。当 的时候有 ，满足要求。而另一个解会出现分母为 的情况（不收敛），舍弃。

因此我们得到了卡特兰数生成函数的封闭形式：

接下来我们要将其展开。但注意到它的分母不是斐波那契数列那样的多项式形式，因此不方便套用等比数列的展开形式。在这里我们需要使用牛顿二项式定理。我们来先展开 ：

注意到

这里使用了双阶乘的化简技巧。那么带回 得到

带回原式得到

这样我们就得到了卡特兰数的通项公式。

路径计数问题

非降路径是指只能向上或向右走的路径。

  1. 从 到 的非降路径数等于 个 和 个 的排列数，即 。

  2. 从 到 的除端点外不接触直线 的非降路径数：

    先考虑 下方的路径，都是从 出发，经过 及 到 ，可以看做是 到 不接触 的非降路径数。

    所有的的非降路径有 条。对于这里面任意一条接触了 的路径，可以把它最后离开这条线的点到 之间的部分关于 对称变换，就得到从 到 的一条非降路径。反之也成立。从而 下方的非降路径数是 。根据对称性可知所求答案为 。

  3. 从 到 的除端点外不穿过直线 的非降路径数：

    用类似的方法可以得到：

最后更新: 2023年12月14日
创建日期: 2018年7月11日
回到页面顶部