斐波那契数，卡特兰数，斯特林数等，TODO

组合数学中的特殊数列

斐波那契数列

卡特兰数

先不说卡特兰数是什么，我们先来看它的几个具象：

• 有$n$个不同的数和一个容量足够大的栈，这些数需要按照顺序压栈，并且只要当前栈不为空就可以选择出栈，问最后有多少种不同的出栈序列。
• 一个人在$(0,0)$点，他想去$(n,n)$点，要求只能每次向上或者向右走一个单位，且任何时候不能使得横坐标大于纵坐标，则有多少种走法。
• 有$2n$个人排成一行进入剧场。入场费 5 元。其中只有$n$个人有一张 5 元钞票，另外$n$人只有 10 元钞票，剧院无其它钞票，问有多少中方法使得只要有 10 元的人买票，售票处就有 5 元的钞票找零？
• $n$个结点的二叉树有多少种形态（假设结点是相同的）？
• 有一个矩阵列$a_1,a_2,...a_n$ ，将其做链乘，可以在其中加括号改变计算顺序，那么乘法存在多少种不同的计算顺序？
• ...

上面提到的几个问题，思考一下会发现问题有两类特点：

• 对前三个问题来说，容易发现问题中隐含了“元素序列中每个前缀中$x$元素都不能多于$y$元素”的特点。
• 对于第四和第五个问题以及很多其他问题来说，在统计答案的时候如果要计算$n$规模的答案，会发现其答案由$1$和$n-1$规模，$2$和$n-2$规模....$n-2$和$2$规模，$n-1$和$1$规模的答案组合而成。

如果发现某个问题具有上面的两个特点中的任意一个，那么这个问题很有可能和卡特兰数有关系，但答案可能和我们下面定义的卡特兰数稍有偏差。

那么卡特兰数究竟是什么呢？卡特兰数就是上面那些问题抽象出来的一个计数数列。

有些教科书上引入卡特兰数时上来便给出了其通项公式，个人感觉这种天降定义不是我这种阳间弱鸡能接受的。

我们可以计算一下这个数或者说数列的通项是多少，分别从上面提到的两类特点去出发：

• 我们考虑第一类特点的问题，将问题抽象成一个数学问题就是求这样一个序列$\{a_n\}$的个数：其有$2n$个元素，其中有$n$个$1$和$n$个$-1$，我们希望序列的前缀和总是不小于$0$。

  容易想到，不考虑任何限制，这些元素能组成$\tbinom{2n}{n}$ 个不同的序列，其中满足上面提到性质的假设有$A_n$个，不满足的有$U_n$个，则$A_n + U_n = \tbinom{2n}{n}$。

  下面计数$U_n$ 。考虑任意一个不合法序列$\{b_n\}$，考虑其第一个小于$0$的前缀和，将这个前缀的所有$1$变成$-1$，$-1$变成$1$，剩下的数都保持原状，则这样整个序列就存在$n+1 $个$1$和$n - 1$个$-1$，这一步是唯一的。反过来，给我们一个有$n+1$个$1$和$n-1$个$-1$组成的序列，找到其第一个前缀和大于$0$的前缀，取反，就得到了一个不合法的序列。综上，这两类序列是一一对应的，所以计数不合法序列，只需要计数$n+1$个$1$和$n-1$个$-1$组成的序列，其答案是$\tbinom{2n}{n+1}$，所以合法序列就是$\tbinom{2n}{n} - \tbinom{2n}{n + 1} = \frac{1}{n+1}\binom{2n}{n}$ ，这就是卡特兰数通项公式。

• 那么有第二个特点的问题和有第一个特点的问题算出来的是同一个通项吗？是，但不完全是，有时候会发现似乎“平移”了一项。遇到这种特点的问题的时候，建议先手算一下前几项，看看和标准的卡特兰数是否有偏移，然后就可以$O(1)$计算了。如果不用公式，可以考虑设$f(n)$是$n$规模的答案，计算第一项，然后求和$f(n) = \sum\limits_{i = 1}^{n - 1}f(i)f(n - i)$ ，也能得到答案，这样求出来的结果一定是对的，只不过看起来似乎和卡特兰数没关系了。

容易发现，这个数列增长得非常快，所以很多时候我们会有求高精度组合数的需求。下面偏一下题，介绍一下求高精度组合数的方法：

计算高精度组合数，一个思路是这样的：考虑到组合数就是阶乘除以阶乘，所以我们可以先对分子和分母上的阶乘做质因数分解，统计它们每个质因数的次数，然后做减法，最后不断调用低精度乘高精度的乘法函数把质因数乘起来，就是结果了。

放一个题130. 火车进出栈问题 - AcWing题库 ，放一下自己算高精度卡特兰数的代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2e5;
const int mod = 100000000; // 压位高精度

int prime[N], cnt;
int primeidx[N];
bool isprime[N];
int n;

void get_prime() {
    for (int i = 2; i < N; i++) {
        isprime[i] = true;
    }
    
    for (ll i = 2; i < N; i++) {
        if (isprime[i]) {
            prime[cnt++] = i;
        }
        for (int j = 0; j < cnt && i * prime[j] < N; j++) {
            isprime[i * prime[j]] = false;
            if (i % prime[j] == 0) {
                break;
            }
        }
    }
}

void split(int n, int flag) {
    for (int i = 0; i < cnt; i++) {
        int p = prime[i];
        while (p <= n) {
            primeidx[i] += (flag * (n / p));
            p = p * prime[i];
        }
    }
}

vector<ll> mult(vector<ll> a, int b) {
    vector<ll> c;
    ll t = 0;
    for (int i = 0; i < a.size(); i++ ){
        t += a[i] * b;
        c.push_back(t % mod);
        t /= mod;
    }
    
    while (t) {
        c.push_back(t % mod);
        t /= mod;
    }
    
    return c;
}

int main() {
    cin >> n;
    
    get_prime();
    
    split(2 * n, 1);
    split(n, -1);
    split(n, -1);
    
    int up = sqrt(n + 1);
    int value = n + 1;
    for (int i = 0; prime[i] <= up; i++) {
        while (value % prime[i] == 0) {
            primeidx[i]--;
            value /= prime[i];
        } 
    }
    if (value > 1) {
        int pos = lower_bound(prime, prime + cnt, value) - prime;
        primeidx[pos]--;
    }
    
    vector<ll> res;
    res.push_back(1);
    for (int i = 0; i < cnt; i++) {
        for (int j = 0; j < primeidx[i]; j++) {
            res = mult(res, prime[i]);
        }
    }
    
    printf("%d", res[res.size() - 1]);
    for (int i = res.size() - 2; i >= 0; i--) {
        printf("%08d", res[i]);
    }
    return 0;
}

这个题比较坑，要计算的卡特兰数非常的大，裸的高精度会超时，需要压位高精度乘法才能过。

这个题也是Y总出道早期直播翻车的一道题，疯狂TLE

斯特林数

第二类斯特林数

将含有$n$件物品的集合划分为$k$个非空子集的方案数为第二类斯特林数，记作

$\begin{Bmatrix} n\\ k \end{Bmatrix}$

考虑递推关系：

$\begin{Bmatrix} n\\ k \end{Bmatrix} = \begin{Bmatrix} n - 1\\ k - 1 \end{Bmatrix} + k\begin{Bmatrix} n - 1\\ k \end{Bmatrix}$

等号右侧第一项代表将第一个元素单独划分为一组，第二项代表将第一个元素划分到剩余的$k$个元素所换分成的某个组中。

第二类斯特林数的通项公式：

$\begin{Bmatrix} n\\ k \end{Bmatrix} = \frac{1}{k!}\sum_{i = 0}^k {(-1)^i}\tbinom{k}{i}(k - i)^n$

推导思路是，先考虑$n$个球放到$k$个可区分的盒子里，不可以有空盒子，则答案是第二类斯特林数乘以$k!$，然后枚举空盒数量使用容斥原理计数，得到的结果就是上面那个式子。

事实上，$k!\begin{Bmatrix}n\\k\end{Bmatrix}$也是一个比较常用的数，可以发现这就是$n$元素集合放到$k$个非空且可区分的盒子中的方案数。

Bell数

Bell数的意义是将$n$个元素划分为非空且不可区分的盒子的划分数。通过枚举盒子数，可以发现其就是第二类斯特林数组成的斯特林三角的一行的和。

第一类斯特林数

将$n$元素集划分成$k$个非空且不可区分的圆排列（或者轮换）的方案数，记作：

$\begin{bmatrix} n\\k \end{bmatrix}$

易得递推关系：

$\begin{bmatrix} n\\k \end{bmatrix} = \begin{bmatrix} n - 1\\k - 1 \end{bmatrix} + (n - 1)\begin{bmatrix} n - 1\\k \end{bmatrix}$

其中，右侧第一项表示第一个元素单独成为一个圆排列，第二项代表把第一个元素插入到某个数的前边。