跳转至

斯特林数

约 595 个字 56 行代码 预计阅读时间 3 分钟

第一类斯特林数

n个不同元素构成m个圆排列的方案数，记为 s(n,m)，或 \begin{bmatrix}n\\ m\end{bmatrix}

分为无符号 s_u(n,m) 和有符号 s_s(n,m) ，关系是 S_s(n,m)=(-1)^{n-m}s_u(n,m)

O(n^2)求第一类斯特林数

1-n的一个排列，划分为m个圆排列，第n个数，要么放在一个新的圆，要么放在旧的圆

\begin{bmatrix}n\\ m\end{bmatrix}=\begin{bmatrix}n-1\\ m-1\end{bmatrix}+(n-1)\times\begin{bmatrix}n-1\\ m\end{bmatrix}

边界情况： \begin{bmatrix}n\\ n \end{bmatrix}=1(n\ge 0) ， \begin{bmatrix}n\\ 0 \end{bmatrix}=0 (n\ge 1) 

const int N=5e3+3;
ll s[N][N];
void cal()
{
    s[0][0]=1;
    for(int i=1;i<N;++i)
    {
        for(int j=1;j<=i;++j)
            s[i][j]=s[i-1][j-1]+(ll)(i-1)*s[i-1][j];
    }
}

无符号第一类斯特林数性质

  1. s_u(n,1)=(n-1)!
  2. s_u(n,2)=(n-1)!\sum\limits_{i=1}^{n-1}\frac 1i
  3. s_u(n,n-1)=\dbinom n2
  4. s_u(n,n-2)=2\dbinom n3+3\dbinom n4
  5. \sum\limits_{i=0}^ns_u(n,i)=n!

第二类斯特林数

n个不同元素构成m个互不区分的非空子集的方案数，记为 S(n,m)，或 \begin{Bmatrix}n\\ m\end{Bmatrix}

O(n^2)求第二类斯特林数

1-n的一个排列，划分为m个互不区分的非空子集，第n个数，要么放在一个新的集合，要么放在旧的集合

\begin{Bmatrix}n\\ m\end{Bmatrix}=\begin{Bmatrix}n-1\\ m-1\end{Bmatrix}+m\times\begin{Bmatrix}n-1\\ m\end{Bmatrix}

边界情况： \begin{Bmatrix}n\\ n \end{Bmatrix}=1(n\ge 0) ， \begin{Bmatrix}n\\ 0 \end{Bmatrix}=0 (n\ge 1) 

const int N=5e3+3;
ll S[N][N];
void cal()
{
    S[0][0]=1;
    for(int i=1;i<N;++i)
    {
        for(int j=1;j<=i;++j)
            S[i][j]=S[i-1][j-1]+(ll)j*S[i-1][j];
    }
}

O(n)求第二类斯特林数

\begin{Bmatrix}n\\ m\end{Bmatrix}=\sum\limits_{i=0}^m\frac{(-1)^{m-i}i^n}{i!(m-i)!} 

const int N=2e5+3;
ll v[N];
int p[N>>2],n;
void seive()
{
    int cnt=0;
    v[1]=1;//!!
    for(int i=2;i<N;++i)
    {
        if(!v[i])
        {
            p[cnt++]=i;
            v[i]=fast_power(i,n);
        }
        for(int j=0;j<cnt && i*p[j]<N;++j)
        {
            v[i*p[j]]=v[i]*v[p[j]]%mod;
            if(i%p[j]==0)
                break;
        }
    }
}
ll cal(int m)
{
    ll res=0;
    for(int i=0;i<=m;++i)
    {
        if((m-i)&1)
            res=(res-v[i]*inv[i]%mod*inv[m-i]%mod+mod)%mod;
        else
            res=(res+v[i]*inv[i]%mod*inv[m-i]%mod)%mod;
    }
    return res;
}

第二类斯特林数性质

  1. S(n,1)=1
  2. S(n,2)=2^{n-1}-1
  3. S(n,3)=\frac 12(3^{n-1}+1)-2^{n-1}
  4. S(n,n-1)=\dbinom n2
  5. S(n,n-2)=\dbinom n3+3\dbinom n4
  6. S(n,n-3)=\dbinom n4+10\dbinom n5+15\dbinom n6
  7. \sum\limits_{i=0}^nS(n,i)=B_n ，B_n 是贝尔数
  8. \sum\limits_{i=0}^n(-1)^i\dbinom ni(n-i)^n=n!
  9. n^k=\sum\limits_{i=0}^kS(k,i)(i!)\dbinom ni

上升幂和下降幂

普通幂：x^n

上升幂：x^{\overline n}=\prod\limits_{i=0}^{n-1}(x+i)

上升幂和普通幂转换：

x^{\overline n}=\sum\limits_{i=0}^n\begin{bmatrix}n\\ i\end{bmatrix}x^i
x^n=\sum\limits_{i=0}^n\begin{Bmatrix}n\\ i\end{Bmatrix}(-1)^{n-i}x^{\overline i}

下降幂：x^{\underline n}=\prod\limits_{i=0}^{n-1}(x-i)

下降幂和普通幂转换：

x^{\underline n}=\sum\limits_{i=0}^n\begin{bmatrix}n\\ i\end{bmatrix}(-1)^{n-i}x^i
x^n=\sum\limits_{i=0}^n\begin{Bmatrix}n\\ i\end{Bmatrix}x^{\underline i}

普通幂转下降幂是常用套路，注意恒等式 \dbinom nii^{\underline j}=\dbinom{n-j}{i-j}n^{\underline j}