小花生

study & life record.

卡特兰数

发表于 分类于 ，

卡特兰数的求法及其常见应用。

以 Catalan 数列为结果的等价问题

  • 给定 n 个 0 和 n 个 1，它们将按照某种顺序排成长度为 2n 的序列，求它们能排列成的所有序列中，能够满足任意前缀序列中 0 的个数都不少于 1 的个数的序列有多少个。

  • 有 2n 个人排成一行进入剧场。入场费 5 元。其中只有 n 个人有一张 5 元钞票，另外 n 人只有 10 元钞票，剧院无其它钞票，问有多少种方法使得只要有 10 元的人买票，售票处就有 5 元的钞票找零。

  • 有一个大小为 n * n 的方格图左下角为 (0, 0) 右上角为 (n, n)，从左下角开始每次都只能向右或者向上走一单位，不走到对角线 y = x 上方（但可以触碰) 的情况下到达右上角有多少可能的路径。

  • 在圆上选择 2n 个点，将这些点成对连接起来使得所得到的 n 条线段不相交的方法数。

  • 对角线不相交的情况下，将一个凸多边形区域分成三角形区域的方法数。

  • 一个栈（无穷大）的进栈序列为 1, 2, 3, … , n 有多少个不同的出栈序列？

求法

Catalan 数列 通项为 $\displaystyle \frac{C_{2n}^n}{n+1}$.

组合数求法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<bits/stdc++.h>
#define int long long
using namespace std;

const int mod = 1e9 + 7;

int qmi(int a, int k, int p){
    int res = 1;
    while(k){
        if(k & 1) res = res * a % p;
        k >>= 1;
        a = a * a % p;
    }
    return res;
}

signed main(){
    int n; cin >> n;
    
    int res = 1;
    for(int i = 2 * n; i > n; i--) res = res * i % mod;
    for(int i = 1; i <= n; i++) res = res * qmi(i, mod - 2, mod) % mod;
    
    cout << res * qmi(n + 1, mod - 2, mod) % mod;
    
    return 0;
}