卡特兰数(Catalan number)的原理

问题引入

  在一个平面直角坐标系中，只能往右或往上走一个单位长度。问有多少种不同的路径可以从左下角 \((0,0)\) 走到右上角 \((n,n)\)，并且要求路径不能经过直线 \(y=x\) 上方的点。

  总方案数为\(\binom{2n}{n}\)，考虑不合法方案数，不合法路径必然经过\(y=x+1\)，找到该路径与\(y=x+1\)的第一个交点，将后面的路径关于\(y=x+1\)对称，每一条不合法方案对应一条 \((0,0)\) 到 \((n-1,n+1)\) 的路径，故不合法方案数为\(\binom{2n}{n-1}\)。

  卡特兰数即为： \[C_n=\binom{2n}{n}-\binom{2n}{n-1}=\frac{1}{n+1}\binom{2n}{n}\] 它的前几项为：\(1,1,2,5,14,42,132,429,1430,4862,16796,58786\cdots\)

  若终点为\((m,n)\)，同理有方案数为 \[\binom{m+n}{n}-\binom{m+n}{n-1}\]

其他形式

括号序列

求由\(n\)对括号形成的合法括号表达式？

  将长度为\(2n\)的括号序列映射为路径：左括号向右，右括号向上，那么合法的括号序列不会在 \(y=x\) 上方，因此长度为\(2n\)的括号序列个数为\(C_n\)。

出栈顺序

有 \(n\) 个元素（无区别）和一个栈，每次可以将一个元素入栈，或者将栈顶元素弹出，问有多少种不同的操作序列。

  进栈看作左括号，出栈看作右括号，方案数为\(C_n\)。

二叉树计数

有多少种不同的 \(n\) 个节点的二叉树？\(n=3\)时如图所示。

  定义\(f_n\)表示有\(n\)个节点的二叉树，那么枚举子树大小可得方程： \[f_n=\sum_{i=0}^{n-1}f_if_{n-i-1}\quad(f_0=1)\]

  直接计算时间为\(O(n^2)\)，对二叉树进行遍历，当第一次遇到节点表示加一个左括号，从左子树返回在序列加一个右括号，对应为括号序列问题，故 \(n\) 个节点的二叉树种数为 \(C_n\)。

凸多边形剖分

求 \(n+2\) 条边的凸多边形的三角剖分方案数？下图为 \(n=4\) 的情况。

  设\(f_n\)为\(n\)边的方案数，取多边形一条边，从剩余顶点选一个，多边形分成三部分，则

\[f_n=\sum_{i=2}^{n-1}f_if_{n-i+1}\quad(f_2=1)\]

故\(n+2\)条边的凸多边形三角剖分方案数为 \(C_n\)。

\(n\)阶梯状图填充

求用\(n\)个长方形去填充一个高度为\(n\)的阶梯图形的方法数。下图为 \(n=4\) 的情况。

  方案数为\(f_n\)，取包含左上角的矩形，同理得递推可得其为卡特兰数。

\[f_n=\sum_{i=0}^{n-1}f_if_{n-i-1}\quad(f_0=1)\]

性质

  1. \(C_n=\frac{1}{n+1}\binom{2n}{n}=\binom{2n}{n}-\binom{2n}{n-1}\)
  2. \(C_n=\frac{1}{n+1}\sum\limits_{i=0}^n\binom{n}{i}^2\)
  3. \(C_{n+1}=\frac{2(2n+1)}{n+2}C_n\)，且\(C_0=1\)
  4. \(C_{n+1}=\sum\limits_{i=0}^nC_iC_{n-i}\)，且\(C_0=1\)
  5. 渐近增长 \(C_n\sim\frac{4^n}{n^{3/2}\sqrt{\pi}}\)
  6. \((n-3)C_n=\frac{n}{2}(C_3C_{n-1}+C_4C_{n-2}+\cdots+C_{n-1}C_3)\)

数学推导

由于\(C_2=C_3=1\)

设\(G(x)=C_2+C_3x+C_4x^2+\cdots\) \[x^2:C_4=C_2C_3+C_3C_2\\ x^3:C_5=C_2C_4+C_3C_3+C_4C_2\\ x^4:C_6=C_2C_5+C_3C_4+C_4C_3+C_5C_2\\ \vdots\] \[\begin{array}{l} G(x)-x-1&=&C_2(C_3x^2+C_4x^3+\cdots)\\ &&+C_3x(C_2x+C_3x^2+\cdots)\\ &&+C_4x^2(C_2x+C_3x^2+\cdots)+\cdots\\ &=&-x+C_2(C_2x+C_3x^2+\cdots)\\ &&+C_3x(C_2x+C_3x^2+\cdots)+\cdots \end{array}\]

\[\Longrightarrow\quad\quad \begin{array}{l} G(x)-1&=&(C_2+C_3x+C_4x^2+\cdots)(C_2x+C_3x^2+\cdots)\\ &=&x[G(x)]2 \end{array}\]

\[xG^2(x)-G(x)+1=0\\ G(x)=\frac{1-\sqrt{1-4x}}{2x}\]

  而\(\displaystyle(1-4x)^{\frac{1}{2}}=1+\frac{1}{2}(-4x)-\frac{\displaystyle\frac{1}{2}(\frac{1}{2}-1)}{2!}(-4x)^2+\frac{\displaystyle\frac{1}{2}(\frac{1}{2}-1)(\frac{1}{2}-2)}{3!}(-4x)^3+\cdots\)

所以\((1-4x)^{\frac{1}{2}}\)中\(x^{n+1}\)项的系数为 \[\begin{array}{l} &&\displaystyle\frac{1}{(n+1)!}\frac{1}{2}\left(\frac{1}{2}-1\right)\left(\frac{1}{2}-2\right)\cdots\left(\frac{1}{2}-n\right)(-4)^{n+1}\\ &=&\displaystyle\frac{(-1)^{2n+1}}{(n+1)!}\frac{1\cdot3\cdot\cdots\cdot(2n-1)}{2^{n+1}}2^{2n+2}\\ &=&\displaystyle\frac{-2}{n+1}\frac{(2n)!}{(n!)^2}=\frac{-2}{n+1}\begin{pmatrix}2n\\n\end{pmatrix} \end{array}\]

故\(\displaystyle G(x)=\frac{1-\sqrt{1-4x}}{2x}\)且 \[C_{n+1}=\frac{1}{n}\begin{pmatrix}2n-2\\n-1\end{pmatrix}\]

由递推关系 \[nC_{n+1}=(4n-6)C_n\] \[G(x)=C_2x+C_3x^2+C_4x^3+\cdots\\ x:2C_3=4\cdot2C_2-6C_2\\ x^2:3C_4=4\cdot3C_3-6C_3\\ \vdots\] \[G'(x)-1=4[xG(x)]'-6G(x)\] \[G(x)=C\sqrt{1-4x}+\frac{1}{2}\] 由\(G(0)=0,\)有\(\displaystyle C=-\frac{1}{2},\)即\(\displaystyle G(x)=\frac{1-\sqrt{1-4x}}{2}\)

应用

[BZOJ1485][HNOI2009]有趣的数列

  从小到大添加每个数，放在奇数项视为进栈，偶数项视为出栈，问题转化为求卡特兰数，答案即\(C_n=\frac{1}{n+1}\binom{2n}{n}=\frac{\prod_{i=n+2}^{2n}i}{\prod_{i=1}^ni}\)。

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int N = 2e6 + 5, INF = 2e9;

int n, p, cnt;
int pri[N/10], v[N], c[N], id[N];

void getpri() {
    for (int i = 2; i <= 2 * n; ++i) {
        if (!v[i]) { pri[++cnt] = i; id[i] = cnt; }
        for (int j = 1; j <= cnt && i * pri[j] <= 2 * n; ++j) {
            v[i*pri[j]] = 1;
            id[i*pri[j]] = j;
            if (i % pri[j] == 0) break;
        }
    }
}

void add(int x, int t) {
    while (x != 1) {
        c[id[x]] += t;
        x /= pri[id[x]];
    }
}

int main() 
{
    scanf("%d%d", &n, &p);
    getpri();
    for (int i = 2 * n; i > n; --i) add(i, 1);
    for (int i = 1; i <= n; ++i) add(i, -1);
    add(n + 1, -1);
    ll ans = 1;
    for (int i = 1; i <= cnt; ++i) {
        while (c[i]--)
            ans = (ll)ans * pri[i] % p;
    }
    printf("%lld\n", ans);
    return 0;
}