卡特兰数

Catalan 数列

以下问题属于 Catalan 数列:

  1. 个人排成一行进入剧场。入场费 5 元。其中只有 个人有一张 5 元钞票,另外 人只有 10 元钞票,剧院无其它钞票,问有多少种方法使得只要有 10 元的人买票,售票处就有 5 元的钞票找零?
  2. 一位大城市的律师在她住所以北 个街区和以东 个街区处工作。每天她走 个街区去上班。如果他从不穿越(但可以碰到)从家到办公室的对角线,那么有多少条可能的道路?
  3. 在圆上选择 个点,将这些点成对连接起来使得所得到的 条线段不相交的方法数?
  4. 对角线不相交的情况下,将一个凸多边形区域分成三角形区域的方法数?
  5. 一个栈(无穷大)的进栈序列为 有多少个不同的出栈序列?
  6. 个结点可构造多少个不同的二叉树?
  7. 构成 ,其部分和满足 对与 该数列为?

其对应的序列为:

...
1 1 2 5 14 42 132 ...

(Catalan 数列)

递推式

该递推关系的解为:

关于 Catalan 数的常见公式:

例题洛谷 P1044 栈

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
// C++ Version
#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;
}
1
2
3
4
5
6
7
8
# Python Version
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. 的除端点外不穿过直线 的非降路径数:

    用类似的方法可以得到:


评论