参考资料

卡特兰数递推公式证明及应用 CSDN博客

卡特兰数 - OI Wiki

定义

构造一个由n个0和n个1的数列，使得任何一个前缀0的个数不少于1的个数的方案数$H_n$即为卡特兰数。

其对应的序列为：

公式

$$ H_n = \begin{cases} \sum_{i = 1}^{n}H_{i - 1}H_{n - i} &n \geq2 \\ 1 &n = 0,1 \\ \end{cases} \\ H_n = \binom{2n}{n} - \binom{2n}{n - 1} \\ H_n = \frac{\binom{2n}{n}}{n + 1}(n \geq 2) \\ H_n = \frac{H_{n - 1}(4n - 2)}{n + 1} $$

证明

公式1证明

• 通过括号匹配来证明。构造一个长度为$2n$的合法括号集，观察最后一个括号，它必为右括号而且可以和第$2n - 1, 2n - 3, \dots, 2i - 1,\dots, 1$个括号匹配，通过$2i - 1$个括号可以将括号集分为两个合法括号集，它们的方案数分别为$H_{i - 1}$和$H_{n - i}$，方案数为$H_{i - 1}H_{n - i}$，所以总的方案数为所有分类之和即$H_n = \sum_{i = 1}^{n}H_{i - 1}H_{n - i}$。

公式2证明

• 设$g(x)$为前$x$个括号左括号总数和右括号的总数的差。在不考虑合法的情况下，所有的方案数即为在$2n$个位置中插入$n$个左括号，即$\binom{2n}{n}$。
• 然后再排除非法方案数。对于一个非法括号集，必然存在$g(i) = -1$，此时将后面所有的左括号改为右括号，右括号改为左括号，最终右括号总数会比左括号多两个即$g(2n) = -2$，所以所有非法方案都可以转化为构造一个$2n - 2$个左括号和$2n + 2$个右括号的括号序列，即$\binom{2n}{n - 1}$。
• 综上所述，方案数为$\binom{2n}{n} - \binom{2n}{n - 1}$。

公式3证明

• 可由公式2推导而得。

$$ \begin{align*} \binom{2n}{n} - \binom{2n}{n - 1} &= \frac{(2n)!}{n! \cdot (2n - n)!} - \frac{(2n)!}{(n - 1)! \cdot (2n - (n - 1))!} \\ &= \frac{(2n)!}{n! \cdot n!} - \frac{(2n)!}{(n - 1)! \cdot (n + 1)!} \\ &= \frac{(2n)!}{n! \cdot n!} - \frac{(2n)!}{n! \cdot n!} \cdot \frac{n}{n + 1} \\ &= \frac{\binom{2n}{n}}{n + 1} \end{align*} $$

公式4证明

• 可由公式3推导而得。

$$ \begin{align*} \frac{\binom{2n}{n}}{n + 1} &= \frac{\binom{2n - 2}{n - 1} \cdot \frac{4n - 2}{n}}{n + 1} \\ &= \frac{\binom{2n - 2}{n - 1}}{n} \cdot \frac{4n - 2}{n + 1} \\ &= \frac{H_{n - 1} \cdot (4n - 2)}{n + 1} \end{align*} $$

例题

P1722 矩阵 II - 洛谷

矩阵 II
描述
众所周知，在中国古代算筹中，红为正，黑为负……

给定一个 $1\times 2n$ 的矩阵（usqwedf：这不是一个 $2n$ 的队列么），现让你自由地放入红色算筹和黑色算筹，使矩阵平衡[即 $\forall i \in[1, 2n]$，$1\sim i$ 格中红色算筹个数大于等于黑色算筹]。

问有多少种方案满足矩阵平衡（注意红色算筹和黑色算筹的数量必须相等）。

输入格式

正整数 $n$。

输出格式

方案数 $t$ 对 $100$ 取模后的结果。

样例输入

2

样例输出

2

数据范围：

$1\le n\le 100$

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef __int128 i128;
typedef long long ll;
typedef double db;

const db PI = acos(-1);
typedef array<ll, 2> PII; // vector<PII> a(n + 1);
const ll inf = 2e18 + 10;
// const int mod = 998244353;
const int maxn = 2e5 + 10;
bool multi = 0;

const int mod = 100;

void Solve() {
    ll n; cin >> n;
    vector<ll> cat(110);
    cat[0] = 1; cat[1] = 1;
    for(ll i = 2; i <= n; i ++ ) {
        for(ll j = 1; j <= i; j ++ ) {
            cat[i] += cat[j - 1] * cat[i - j];
            cat[i] %= 100;
        }
    }
    cout << cat[n] << '\n';
}


signed main() {
    // freopen("test.in","r",stdin);  
    // freopen("code.out","w",stdout);    
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    ll T = 1;
    if(multi) cin >> T;
    while(T -- ) {
        Solve();
    }
    return 0;
}