zcmimi's blog

第一类斯特林数

定义

  • s(n,m)表示将n个元素分成m个圆排列的方案数

  • 记作\begin{bmatrix}n\\m\end{bmatrix}

递推式

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

(当前元素可以建一个新环或放在已有的任意元素前面)

性质

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

证明: 每个排列实际上对应着一个置换

考虑s(n,i)分成的i个环,实际上就是对应着循环节个数为i的一种置换,一一对应过去就是所有置换方案就是全排列了

阶乘幂

上升阶乘幂:

\begin{aligned}x^{\overline{n}}&=x(x+1)(x+2)\cdots(x+n-1)\\&=\frac{(x+n-1)!}{(x-1)!}\end{aligned}

下降阶乘幂:

\begin{aligned}x^{\underline{n}}&=x(x-1)(x-2)\cdots(x-n+1)\\&=\frac{x!}{(x-n)!}\end{aligned}

  • 上升阶乘幂

    \displaystyle x^{\overline n}=\sum_{i=0}^n \begin{bmatrix}n\\i\end{bmatrix}x^i

    证明:

    \begin{aligned} x^{\overline{n+1}} &=(x+n)\sum_{i=0}^n \begin{bmatrix}n\\i\end{bmatrix}x^i\\ &=\sum_{i=0}^{n+1}\begin{bmatrix}n\\i-1\end{bmatrix}x^i+n\sum_{i=0}^{n+1}\begin{bmatrix}n\\i\end{bmatrix}x^i\\ &=\sum_{i=0}^{n+1}\left( \begin{bmatrix}n\\i-1\end{bmatrix}+n\begin{bmatrix}n\\i\end{bmatrix}\right)x^i\\ &=\sum_{i=0}^{n+1}\begin{bmatrix}n+1\\i\end{bmatrix}x^i \end{aligned}

  • 下降阶乘幂

    \displaystyle x^{\underline{n}}=\sum_{i=0}^n \begin{bmatrix}n\\i\end{bmatrix}(-1)^{n-i}x^i

    证明(数学归纳法):

    n=1时,成立

    n>1时:

    \begin{aligned} x^{\underline{n+1}} &=(x-n)x^{\underline{n}}\\ &=(x-n)\sum_{i=0}^n \begin{bmatrix}n\\i\end{bmatrix}(-1)^{n-i}x^i\\ &=\sum_{i=0}^{n+1} \begin{bmatrix}n\\i-1\end{bmatrix}(-1)^{n-i-1}x^i +n\sum_{i=0}^{n+1} \begin{bmatrix}n\\i\end{bmatrix}(-1)^{n-i+1}x^i\\ &=\sum_{i=0}^{n+1}\left( \begin{bmatrix}n\\i-1\end{bmatrix} + n\begin{bmatrix}n\\i\end{bmatrix}\right)(-1)^{n-i+1}x^i\\ &=\sum_{i=0}^{n+1}\begin{bmatrix}n+1\\i\end{bmatrix}(-1)^{n+1-i}x^i \end{aligned}

快速计算

构造第一类斯特林数生成函数:

\displaystyle \sum_{i=0}^n \begin{bmatrix}n\\i\end{bmatrix} x^i =\prod_{i=0}^{n-1} (x+i)

倍增:

\displaystyle F_n(x)=\prod_{i=0}^{n-1} (x+i)

那么F_{2n}=F_n(x)F_n(x+n)

可以递归求解F_n(x)

考虑快速计算F_n(x+n):

a_i=[x_i]F_n(x)=\begin{bmatrix}n\\i\end{bmatrix},(也就是上一次计算出的结果)

\displaystyle \begin{aligned} F_n(x+n) &=\sum_{i=0}^{n-1} a_i (x+n)^i\\ &=\sum_{i=0}^{n-1} a_i \sum_{j=0}^i {i\choose j} n^{i-j}x^j\\ &=\sum_{i=0}^{n-1}x^i \sum_{j=i}^n {j\choose i} n^{j-i} a_j\\ &=\sum_{i=0}^{n-1}\frac{x^i}{i!} \sum_{j=i}^n (a_j j!)\frac{n^{j-i}}{(j-i)!} \end{aligned}

A(i)=a_i i!,B(i)=\frac{x^i}{i!},那么:

\displaystyle \begin{aligned} F_n(x+n) &=\sum_{i=0}^{n-1}\frac{x^i}{i!} \sum_{j=i}^n A(j)B(j-i)\\ &=\sum_{i=0}^{n-1}\frac{x^i}{i!} \sum_{j=0}^{n-i} A(i+j)B(j)\\ &=\sum_{i=0}^{n-1}\frac{x^i}{i!} \sum_{j=0}^{n-i} A'(n-i-j)B(j)\\ &=\sum_{i=0}^{n-1}\frac{x^i}{i!} \sum_{x+y=n-i} A'(x)B(y) \end{aligned}

可以发现后面是卷积的形式

模板:

LG 5408 第一类斯特林数·行

#include<bits/stdc++.h>
const int N=1200000,P=167772161,G=3,Gi=55924054;
int L,l,r[N],fac[N],inv[N];
void swap(int&x,int&y){int t=x;x=y;y=t;}
int pw(int x,int b){
    int res=1;
    while(b){
        if(b&1)res=1ll*res*x%P;
        b>>=1,x=1ll*x*x%P;
    }
    return res;
}
void getL(int n){
    for(L=1;L<n;L<<=1,++l);
    for(int i=0;i<L;++i)
        r[i]=(r[i>>1]>>1)|((i&1)?(L>>1):0);
}
void ntt(int*A,int typ){
    for(int i=0;i<L;++i)
        if(i<r[i])swap(A[i],A[r[i]]);
    for(int len=1;len<L;len<<=1){
        int Wn=pw(~typ?G:Gi,(P-1)/(len<<1));
        for(int i=0;i<L;i+=len<<1){
            int w=1;
            for(int k=0;k<len;++k){
                int t=1ll*w*A[i+k+len]%P;
                A[i+k+len]=(A[i+k]-t+P)%P;
                A[i+k]=(A[i+k]+t)%P;
                w=1ll*w*Wn%P;
            }
        }
    }
    if(~typ)return;
    for(int i=0,iL=pw(L,P-2);i<L;++i)
        A[i]=1ll*A[i]*iL%P;
}
int s[N],a[N],b[N],g[N];
void mul(int*f,int*g){
    ntt(f,1),ntt(g,1);
    for(int i=0;i<L;++i)f[i]=1ll*f[i]*g[i]%P;
    ntt(f,-1);
}
void solve(int n){
    if(n==1){s[1]=1;return;}
    if(n&1){
        solve(n-1);
        for(int i=n;i;--i)
            s[i]=(s[i-1]+1ll*s[i]*(n-1)%P)%P;
        s[0]=1ll*s[0]*(n-1)%P;
        return;
    }
    int m=n>>1,res=1;
    solve(m);
    for(int i=0;i<=m;++i)
        a[i]=1ll*s[i]*fac[i]%P,
        b[i]=1ll*res*inv[i]%P,
        res=1ll*res*m%P;;
    std::reverse(a,a+m+1);
    getL((m+1)*2);
    mul(a,b);
    for(int i=0;i<=m;++i)
        g[i]=1ll*inv[i]*a[m-i]%P;
    mul(s,g);
    for(int i=m+1;i<L;++i)a[i]=b[i]=g[i]=0;
    for(int i=n+1;i<L;++i)s[i]=0;
}
void init(int n){
    fac[0]=1;
    for(int i=1;i<=n;++i)fac[i]=1ll*fac[i-1]*i%P;
    inv[n]=pw(fac[n],P-2);
    for(int i=n-1;i>=0;--i)inv[i]=1ll*inv[i+1]*(i+1)%P;
}
int main(){
    int n;
    scanf("%d",&n);
    init(n+n);
    solve(n);
    for(int i=0;i<=n;++i)
        printf("%d ",s[i]);
}

LG 5409 第一类斯特林数·列

自然数幂和

\displaystyle S_k(n)=\sum_{i=1}^n i^k

\begin{aligned} S_k(n) &=\sum_{i=1}^n i^k\\ &=\sum_{i=1}^n \left( i^{\underline{k}} - \sum_{j=0}^{k-1} \begin{bmatrix}k\\j\end{bmatrix}(-1)^{k-j}i^j\right)\\ &=\sum_{i=1}^n i^{\underline{k}} - \sum_{j=0}^{k-1}(-1)^{k-j}\left( \sum_{x=1}^n x^j \right)\\ &=\frac{(n+1)^{\underline{k+1}}}{k+1} - \sum_{j=0}^{k-1} \begin{bmatrix}k\\j\end{bmatrix}(-1)^{k-j}S_j(n) \end{aligned}

\begin{aligned} S_k(n) &=\sum_{i=1}^n i^k\\ &=\sum_{i=1}^n \left( i^{\overline{k}} - \sum_{j=0}^{k-1} \begin{bmatrix}k\\j\end{bmatrix}i^j\right)\\ &=\sum_{i=1}^n i^{\overline{k}} - \sum_{j=0}^{k-1}\left( \sum_{x=1}^n x^j \right)\\ &=\frac{(n+1)^{\overline{k+1}}}{k+1} - \sum_{j=0}^{k-1}\begin{bmatrix}k\\j\end{bmatrix}S_j(n) \end{aligned}

复杂度O(k^2)

第二类斯特林数

定义

S(n,m)表示把n个元素划分成m个子集的方案数

记作\begin{Bmatrix}n\\m\end{Bmatrix}

递推式

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

(分到一个新的子集或者插入到已有的子集中)

性质

\displaystyle \begin{aligned} \begin{Bmatrix}n\\m\end{Bmatrix} &=\frac 1{m!} \sum_{i=0}^m(-1)^i {m\choose i}(m-i)^n\\ &=\sum_{i=0}^m \frac{(-1)^i}{i!}\cdot \frac{(m-i)^n}{(m-i)!} \end{aligned}

(可以看做进行容斥, 枚举多少个集合是空的, 其余的集合随便放置, 最后每一种情况会统计m!次)

可以卷积求解

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

证明:

\displaystyle \begin{aligned} m^n &=\sum_{i=0}^m \begin{Bmatrix} n\\i \end{Bmatrix} {m\choose i} i!\\ &=\sum_{i=0}^m \begin{Bmatrix} n\\i \end{Bmatrix} m^{\underline{i}} \end{aligned}

(可以看作将n个求放到m个带标号的盒子内,枚举哪些盒子不为空)

参考资料:

斯特林数
comment评论
Search
search