数论——特殊数列_斯特林数，贝尔数

第一类斯特林数：
表示的是将n个不同元素构成m个圆排序的数目

公式：

边界：
S1(n，m)=1(n>=0)：有n个人和n个圆
S1(n,0)=0

代码实现：

const int mod=1e9+7;//取模
LL s[N][N];//存放要求的第一类Stirling数
void init(){
    memset(s,0,sizeof(s));
    s[1][1]=1;
    for(int i=2;i<=N-1;i++){
        for(int j=1;j<=i;j++){
            s[i][j]=s[i-1][j-1]+(i-1)*s[i-1][j];
            if(s[i][j]>=mod)
                s[i][j]%=mod;
        }
    }
}

第二类斯特林数：
把n个不同元素划分到m个集合的方案数

公式：

边界：
S2(n,m)=1,n>=0
S2(n,0)=0,n>=1

代码：

const int mod=1e9+7;//取模
LL s[N][N];//存放要求的Stirling数
void init(){
    memset(s,0,sizeof(s));
    s[1][1]=1;
    for(int i=2;i<=N-1;i++){
        for(int j=1;j<=i;j++){
            s[i][j]=s[i-1][j-1]+j*s[i-1][j];
            if(s[i][j]>=mod)
                s[i][j]%=mod;
        }
    }
}

贝尔数：
一：定理：Bell数B(p)是将p元素集合分到非空且不可区分盒子的划分个数（没有说分到几个盒子里面）。 *B(p)=S(p,0)+S(p,1)+.....+S(p,k) *所以要求Bell数就要先求出第二类Stiring数。

二：公式：

三：代码(定义法)

/*
 *  n元集合分划为k类的方案数记为S(n, k),称为第二类Stirling数。
 *  如{A,B,C}可以划分{{A}, {B}, {C}}, {{A, B}, {C}}, {{B, C}, {A}}, {{A, C}, {B}}, {{A, B, C}}。
 *  即一个集合可以划分为不同集合(1...n个)的种类数
 *  CALL: compute(N); 每当输入一个n,输出B[n]
 */
const int N = 2001;
int data[N][N], B[N];

void NGetM(int m, int n)    // m 个数 n 个集合
{
    //  data[i][j]: i个数分成j个集合
    int min, i, j;
    data[0][0] = 1;
    for (i = 1; i <= m; i++)
    {
        data[i][0] = 0;
    }
    for (i = 0; i <= m; i++)
    {
        data[i][i + 1] = 0;
    }
    for (i = 1; i <= m; i++)
    {
        if (i < n)
        {
            min = i;
        }
        else
        {
            min = n;
        }
        for (j = 1; j <= min; j++)
        {
                data[i][j] = (j * data[i - 1][j] + data[i - 1][j - 1]);
        }
    }
    return ;
}

void compute(int m)
{
    //  b[i]: Bell数
    NGetM(m, m);
    memset(B, 0, sizeof(B));
    int i, j;
    for (i=1; i <= m; i++)
    {
        for (j = 0; j <= i; j++)
        {
            B[i] += data[i][j];
        }
    }
    return ;
}

引用参考：
斯特林数的应用
斯特林数
郑州集训笔记