跳转至

斯特林数

第一类斯特林数

概述

求将n个互不相同的球分成k个圆排列的方案数

思路

\(s[i][j]\)表示将\(i\)个球分成\(j\)个圆排列的方案数，当放入第\(i\)个球时，可以将其额外新增一个原排列，此时方案数位\(s[i-1][j-1]\)，也可以将其插入到前\(i-1\)个数的空隙中，由于是圆排列，\(x\)个球就有\(x\)个空，于是新增了\((i-1)*s[i-1][j]\)种方案。

代码模板

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>  
using namespace std;  
#define int long long  
int k,n;  
const int N=1005;  
int s[N][N];  
const int mod=1e9+7;  
signed main()  
{  
    cin>>n>>k;  
    s[0][0]=1;  
    for(int i=1;i<=n;i++)  
    {  
        for(int j=1;j<=k;j++)  
        {  
            s[i][j]=s[i-1][j-1]+(i-1)*s[i-1][j];  
            s[i][j]%=mod;  
        }  
    }  
    cout<<s[n][k]<<endl;  
}

第二类斯特林数

概述

求将n个不同的球分成k组的方案数

思路

\(S[i][j]\)表示将\(i\)个球分成\(j\)组的方案数，当放入第\(i\)个球时，同第一类斯特林数，可以选择额外生成一个原排列，则方案数为\(S[i-1][j-1]\)，也可以将其插入到前\(j\)组中，方案数为\(j*S[i-1][j]\)。

代码模板

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>  
using namespace std;  
#define int long long  
const int N=1005;  
int S[N][N];  
int n,k;  
const int mod=1e9+7;  
signed main()  
{  
    cin>>n>>k;  
    S[0][0]=1;  
    for(int i=1;i<=n;i++)  
    {  
        for(int j=1;j<=k;j++)  
        {  
            S[i][j]=S[i-1][j-1]+j*S[i-1][j];  
            S[i][j]%=mod;  
        }  
    }  
    cout<<S[n][k]<<endl;  
    return 0;  
}