斯特林数

第一类斯特林数

将 $1 \sim n$ 划分为 $k$ 个圆排列的方案数，记作 $s(n,k)$ 或 $\begin{bmatrix} n\ k\end{bmatrix}$

求法：

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

即将第 $n$ 个数单独作为一个圆排列和放到原有的圆排列的方案数之和。第二种放法相当于先枚举每个排列，放到每个排列的每个数之后的方案数，也就是所有点数的总和，因此为 $n-1$ 。

性质：

$\begin{bmatrix} 0\ 0\end{bmatrix}=1$
$\begin{bmatrix} n\ 0\end{bmatrix}=0$
$\begin{bmatrix} n\ n\end{bmatrix}=1$
$\begin{bmatrix} n\ 1\end{bmatrix}=(n-1)!$，即 $1\sim n$ 的圆排列数
$\begin{bmatrix} n\ n-1\end{bmatrix}=C_n^2$，即从 $n$ 个数里选出两个数组成一个圆排列，其余的数单独为圆排列
$\begin{bmatrix} n\ 2\end{bmatrix}=(n-1)!\cdot \sum_{i=1}^{n-1}\frac 1 i$

相当于将 $n$ 个点划分为大小为 $i$ 和 $n-i$ 的两个圆排列，方案数为 $C_n^i$，两个圆排列内部的方案数为 $(i-1)!$ 和 $(n-i-1)!$，由于两个圆交换方案相同，但会被算两次。由于每个圆的点数不为零，因此 $i$ 从 $1$ 循环到 $n-1$ ，所以方案数就为 $\sum_{i=1}^{n-1}\frac 1 2 C_n^i (i-1)!(n-i-1)!$
$$
\begin{array}{l}
\sum_{i=1}^{n-1} \frac 1 2 C_n^i (i-1)!(n-i-1)!\
= \frac 1 2\sum_{i=1}^{n-1} \frac{n!}{(n-i)!i!} (i-1)!(n-i-1)!\
=\frac 1 2 \sum_{i-1}^{n-1} \frac {n!} {(n-i)i}\
=\frac 1 2 \sum_{i=1}^{n-1} (n-1)! \frac {n}{i(n-i)}\
=\frac 1 2 (n-1)! \sum_{i=1}^{n-1} (\frac 1 i +\frac 1 {n-i})
\end{array}
$$
由于从 $1$ 到 $n-1$ ，$\frac 1 i$ 和 $\frac 1 {n-i}$ 都会出现 $1 \sim \frac 1 {n-1}$ ，因此
$$
\begin{array}{l}
\sum_{i=1}^{n-1} \frac 1 2 C_n^i (i-1)!(n-i-1)!\
=\frac 1 2 (n-1)! \sum_{i=1}^{n-1} (\frac 1 i +\frac 1 {n-i})\
=\frac 1 2 (n-1)! \cdot 2\sum_{i=1}^{n-1} \frac 1 i\
=(n-1)! \sum_{i-1}^{n-1}\frac 1 i
\end{array}
$$
$\begin{bmatrix} n\ n-2\end{bmatrix}=2\cdot C_n^3+3\cdot C_n^4$

相当于将 $n$ 个点划分成 $n-3$ 个 1 个点的圆排列和 1 个 3 个点的圆排列或将 $n$ 个点划分成 $n-4$ 个 1 个点的圆排列和 2 个 2 个点的圆排列的方案数之和，即 $C_n^3 \cdot 2!+ C_n^2 \cdot C_{n-2}^2$
$$
\begin{array}{l}
C_n^3 \cdot 2!+ C_n^2 \cdot C_{n-2}^2\
=2\cdot C_n^3+\frac{n!}{(n-2)! 2!}\cdot \frac{(n-2)!}{(n-4)!2!}\
=2\cdot C_n^3+\frac{n!}{4\cdot(n-4)!}\
=2\cdot C_n^3+3\cdot \frac{n!}{(n-4)!4!}\
=2\cdot C_n^3+3\cdot C_n^4
\end{array}
$$

$\sum_{k=0}^n \begin{bmatrix} n\ k\end{bmatrix}=n!$

记升阶函数 $x^{n\uparrow}=x(x+1)\cdots (x+n-1)$，则其展开式的 $x^k$ 项系数 $a_k$ 为 $\begin{bmatrix} n\ k\end{bmatrix}$，下面用数学归纳法证明

$k=1,a_1=1\cdot 2\cdots(n-1)=(n-1)!=\begin{bmatrix} n\ 1\end{bmatrix}$

设 $k=t$ 时，$a_t=\begin{bmatrix} n\ t\end{bmatrix}$

则 $t+1$ 时，$a_{t+1}=\begin{bmatrix} n\ t+1\end{bmatrix}=\begin{bmatrix} n-1\ k-1\end{bmatrix}+(n-1)\begin{bmatrix} n-1\ k\end{bmatrix}$

综上，归纳假设成立，命题得证。

取 $x=1$ ，则得到 $1^{n\uparrow}=1\cdot 2\cdots n=n!=\begin{bmatrix} n\ 0\end{bmatrix}+\begin{bmatrix} n\ 1\end{bmatrix}+\begin{bmatrix} n\ 2\end{bmatrix}+\cdots+\begin{bmatrix} n\ n\end{bmatrix}$

求第一类斯特林数 AcWing 3165. 第一类斯特林数

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N=1005,mod=1e9+7;

int n,m;
int f[N][N];

int main(){
    cin >> n >> m;
    f[0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            f[i][j]=(f[i-1][j-1]+1ll*(i-1)*f[i-1][j])%mod;
        }
    }
    cout << f[n][m];
    return 0;
}

第二类斯特林数

将 $1\sim n $ 划分成 $k$ 个子集的方案数，记作 $S(n,k)$ 或 $\begin{Bmatrix} n \ k\end{Bmatrix}$

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

即第 $n$ 个数单独放到一个子集里或第 $n$ 个数放到前面的子集中的一个里的方案数之和

性质：

$\begin{Bmatrix} n \ 0\end{Bmatrix}=0^n$ （$n=0$ 时 $0^0=1$，$n>0$ 时 $0^n =0$ ）
$\begin{Bmatrix} n \ 1\end{Bmatrix}=1$
$\begin{Bmatrix} n \ n\end{Bmatrix}=1$
$\begin{Bmatrix} n \ 2\end{Bmatrix}=2^{n-1}-1$

$n$ 个数每个数可以划分到第一个子集或第二个子集，因此方案数为 $2^n$，每个子集不能为空，减去 $2$ 个存在子集为空的方案数，集合之间没有顺序，减去重复的，即方案数除以 $2$ ，因此方案数为 $\frac {2^n-2} 2=2^{n-1}-1$
$\begin{Bmatrix} n \ n-1\end{Bmatrix}=C_n^2$

只有一种划分方案，即有 $n-2$ 个集合为 1 个数，1 个集合为 2 个数，因此方案数就是从 $n$ 个数里选两个，即 $C_n^2$
$\begin{Bmatrix} n \ n-2\end{Bmatrix}=C_n^3+3\cdot C_n^4$

共两种方案，即有 $n-3$ 个集合为 1 个数，1 个集合为 3 个数和有 $n-4$ 个集合为 1 个数，2 个集合为 2 个数，方案数为 $C_n^3+C_n^2\cdot C_{n-2}^2=C_n^3+2\cdot C_n^4$（推导过程同第一类斯特林数性质7）
$\begin{Bmatrix} n \ 3 \end{Bmatrix}=\frac 1 2(3^{n-1}+1)-2^{n-1}$
$\begin{Bmatrix} n \ n-3\end{Bmatrix}=C_n^4+10\cdot C_n^5+15\cdot C_n^6$
$\sum_{k=0}^n \begin{Bmatrix} n \ k\end{Bmatrix}=B_n$，其中 $B_n$ 是贝尔数，$B_{n+1}=\sum_{k=0}^n C_n^k B_k$，$B_n=\frac 1 e \sum_{k=0}^{\infty} \frac{k^n}{k!}$

通项公式：$\begin{Bmatrix} n \ m\end{Bmatrix}=\frac 1 {m!} \sum_{k=0}^m (-1)^k C_m^k(m-k)^n $

$m^n=\sum_{i=0}^m \matrix{}\begin{Bmatrix} n \ i\end{Bmatrix} m^{\underline i}$

其中 $m^{\underline n}=\Pi_{i=m-n+1}^{m}=\frac {m!}{(m-n)!}=C_m^n\cdot n!$

第一类斯特林数和第二类斯特林数满足：$\sum_{k=0}^n \begin{bmatrix} n \ k\end{bmatrix} \begin{Bmatrix} k \ m\end{Bmatrix}=\sum_{k=0}^n \begin{Bmatrix} n \ k\end{Bmatrix}\begin{bmatrix} k \ m\end{bmatrix}$

求第二类斯特林数 AcWing 3166. 第二类斯特林数

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N=1005,mod=1e9+7;

int n,m;
int f[N][N];

int main(){
    cin >> n >> m;
    f[0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            f[i][j]=(f[i-1][j-1]+1ll*j*f[i-1][j])%mod;
        }
    }
    cout << f[n][m];
    return 0;
}

例题：洛谷 P4609 [FJOI2016] 建筑师/AcWing 3020. 建筑师

小 $ Z $ 是一个很有名的建筑师，有一天他接到了一个很奇怪的任务：在数轴上建 $ n $ 个建筑，每个建筑的高度是 $ 1 $ 到 $ n $ 之间的一个整数。

小 $ Z $ 有很严重的强迫症，他不喜欢有两个建筑的高度相同。

另外小 $ Z $ 觉得如果从最左边（所有建筑都在右边）看能看到 $ A $ 个建筑，从最右边（所有建筑都在左边）看能看到 $ B $ 个建筑，这样的建筑群有着独特的美感。

现在，小 $ Z $ 想知道满足上述所有条件的建筑方案有多少种？

如果建筑 $ i $ 的左(右)边没有任何建造比它高，则建筑 $ i $ 可以从左(右)边看到。

两种方案不同，当且仅当存在某个建筑在两种方案下的高度不同。

输入格式
第一行一个整数 $ T $，代表 $ T $ 组数据。

接下来 $ T $ 行，每行三个整数 $ n,A,B $。

输出格式
对于每组数据输出一行答案 $ \bmod 10^9+7 $。

数据范围
$ 1 \le n \le 50000 $,
$ 1 \le A,B \le 100 $,
$ 1 \le T \le 200000 $

输入样例：
1
2
3
2
3 2 2
3 1 2
输出样例：
1
2
2
1

分析：

用高度为 $n$ 的建筑物将序列分为两半，则从左看一定看不到右边，从右看一定看不到左边，两边完全独立。

然后题目转化为左半部分可以看到 $A-1$ 个建筑，右半部分可以看到 $B-1$ 个建筑

将每个建筑物和被它挡住的建筑物作为一个整体，则要求左边有 $A-1$ 个部分，右边有 $B-1 $ 个部分，因此将 $1\sim n-1$ 划分成 $A+B-2$ 个部分，并考虑每一部分的排列数（设这个部分有 $k$ 个数，则第一个数必须是最大的，其余数可以随便选，方案数为 $(k-1)!$ ）其实也就是将 $1\sim n-1$ 划分成 $A+B-2$ 个圆排列的方案数，所以就是第一类斯特林数，方案数为 $\begin{bmatrix} n-1\ A+B-2\end{bmatrix}$

接下来将这些圆排列划分到两边，即 $C_{A+B-2}^{A-1}$ 中方案

最后，将左右两边排序，只有 1 中排法

因此，总共的方案数就是 $\begin{bmatrix} n-1\ A+B-2\end{bmatrix} \cdot C_{A+B-2}^{A-1}$

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N=50005,M=205,mod=1e9+7;

int n,A,B;
int f[N][M];
int c[M][M];

int main(){
    f[0][0]=1;
    for(int i=1;i<N;i++){
        for(int j=1;j<M;j++){
            f[i][j]=(f[i-1][j-1]+1ll*(i-1)*f[i-1][j])%mod;
        }
    }
    
    for(int i=0;i<M;i++){
        c[i][0]=1;
        for(int j=1;j<=i;j++){
            c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
        }
    }
    
    int T;
    cin >> T;
    while(T--){
        cin >> n >> A >> B;
        cout << 1ll*f[n-1][A+B-2]*c[A+B-2][A-1]%mod << endl;
    }
    return 0;
}

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。