斯特林数入门

Arahc 11.0
  2022-02-09 08:00 2022-02-09 08:00 创建   2023-03-19 09:11:02 2023-03-19 09:11:02 更新      6.3k 字  32 分钟  

本博客包含：

  • 第一类斯特林数。
  • 第二类斯特林数。
  • 斯特林反演。

组合数、二项式定理之类的东西不会在本文科普。因为比较基础。

第一类斯特林数

基础

定义：nn 个数组成 kk 个圆排列的方案数，为 n,kn,k 的第一类斯特林数。记作 [nk]n\brack k。

第一类斯特林数的递推式：

[nk]=[n−1k−1]+[n−1k](n−1){n\brack k} = {n-1\brack k-1} + {n-1\brack k}(n-1)

意义为：第 nn 个数可以单独形成一个圆排列，也可以选择前 n−1n-1 个数的任意一个并放到它后面。

还有另一个递推式：

[nk]=∑i=1n[n−ik−1](n−1i−1)(i−1)!{n\brack k} = \sum_{i=1}^n {n-i\brack k-1}\binom{n-1}{i-1} (i-1)!

意义为：枚举 11 所在的圆排列大小 ii，剩下的数字组成圆排列方案数为 [n−1k−1]n-1\brack k-1，选择除了 11 之外的其他数到 11 所在圆排列的方案数为 (n−1i−1)\binom{n-1}{i-1}，这些数字组成圆排列的方案数为 (i−1)!(i-1)!。

当然有的时候也需要把斯特林数拆开，那么这个递推式是经常反过来用的。

根据斯特林数的定义，显然，同一行所有斯特林数的和为 n!n!。证明则考虑枚举长度为 nn 的排列的循环数即可。

Luogu4609 建筑师

nn 个楼排成一行，高度是 nn 的排列。求有多少种方案满足从左看恰好能看到 aa 个楼，从右看恰好能看到 bb 个楼。

多组数据，T≤2×105,n≤5×104,a,b≤100T\leq 2\times10^5,n\leq 5\times10^4,a,b\leq 100。

题解

最高的建筑无论左右都一定能被看到，且挡住了后面所有的视线，以此为契机。

考虑把所有的建筑分为 a+b−1a+b-1 个“建筑群”，每个建筑群中选出最高的建筑为代表，放在这个建筑群的最左边，挡住建筑群中其它的建筑。

如果大小为 kk 的建筑群代表已经确定了，剩下的建筑怎么放无所谓。有 (k−1)!(k-1)! 种放的方案数值上等于一个圆排列。

除去最高的建筑后，从左边看有 a−1a-1 个代表，从右有 b−1b-1 个。一个代表为一个群。于是变成了将 n−1n-1 个建筑划分为 a+b−2a+b-2 个建筑群，然后选择其中 a−1a-1 个放在左边：

ans=(a+b−2a−1)[n−1a+b−2]ans = \binom{a+b-2}{a-1} {n-1\brack a+b-2}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int max_n=50004,max_m=202,mod=1000000007;
inline int read(){
    int x=0;bool w=0;char c=getchar();
    while(c<'0' || c>'9') w|=c=='-',c=getchar();
    while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return w?-x:x;
}
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10^48);
}

const int N=50000,M=200;
int n,a,b,C[max_m][max_m],S[max_n][max_m];

signed main(){
    C[0][0]=S[0][0]=1;
    for(register int i=1;i<=M;++i){
        C[i][0]=C[i][i]=1;
        for(register int j=1;j<i;++j)
            C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
    }
    for(register int i=1;i<=N;++i)
        for(register int j=1;j<=M;++j)
            S[i][j]=(S[i-1][j-1]+S[i-1][j]*(i-1))%mod;
    for(register int T=read();T>0;--T){
        n=read(),a=read(),b=read();
        write(C[a+b-2][a-1]*S[n-1][a+b-2]%mod),putchar('\n');
    }
    return 0;
}

第一类斯特林数 行

如何快速求出一行的第一类斯特林数呢？显然，n2n^2 求第一类斯特林数还是有些慢的。我们需要找到其更多的性质。

xn‾=∑i=0n[ni]xix^{\overline n} = \sum_{i=0}^n {n\brack i} x^i

证明

设生成函数 Fn(x)=∑i{ni}xiF_n(x) = \sum_i {n\brace i} x^i，由递推式得到 Fn=xFn−1+(n−1)Fn−1=(x+n−1)Fn−1F_n = xF_{n-1} + (n-1)F_{n-1} = (x+n-1)F_{n-1}。

下面考虑如何求 xn‾x^{\overline n}，考虑倍增，已知 xn‾x^{\overline n} 求 x2n‾=xn‾(x+n)n‾x^{\overline{2n}} = x^{\overline n}(x+n)^{\overline n}。换句话说，给定 f(x)f(x)，求 f(x+n)f(x+n)：

f(x+n)=∑i=0nfi(x+n)if(x+n) = \sum_{i=0}^n f_i (x+n)^i

二项式定理：

∑i=1nfi∑j=1ixjni−j(ij)\sum_{i=1}^n f_i \sum_{j=1}^i x^jn^{i-j}\binom{i}{j}

交换 sigma，拆组合数：

∑j=1nxkj∑i=jni!fini−j(i−j)!\sum_{j=1}^n \frac{x^k}{j}\sum_{i=j}^n i!f_i\frac{n^{i-j}}{(i-j)!}

这是一个卷积形式，NTT 即可。复杂度 nlog⁡nn\log n。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
inline void sol(int len){ // 调用 sol(n) 求第 n 行斯特林数并存入 f[] 数组
    if(len==1){
        f[1]=1;
        return;
    }
    sol(len>>1); // 倍增
    int n=len>>1,tmp=1;
    while(tmp<=n+n)
        tmp<<=1;
    for(register int i=0;i<=n;++i)
        a[i]=f[i]*fac[i]%mod;
    for(register int i=0,base=1;i<=n;++i,base=base*n%mod)
        b[i]=inv[i]*base%mod;
    for(register int i=0,j=n;i<j;++i,--j) // 注意要反过来
        swap(b[i],b[j]);
    for(register int i=n+1;i<tmp;++i)
        a[i]=b[i]=0;
    DXS::Mul(a,b,n,n);

    for(register int i=0;i<=n;++i) // 整体左移 n 位
        a[i]=a[i+n]*inv[i]%mod;
    for(register int i=n+1;i<=n*2;++i)
        a[i]=0;
    DXS::Mul(f,a,n,n);
    
    if(len&1){ // 遇到奇数的情况暴力求一下即可
        for(register int i=n*2+1;i>=1;--i)
            f[i]=(f[i-1]+(len-1)*f[i]%mod)%mod;
        f[0]=f[0]*(len-1)%mod;
    }
}

CF960G Bandit Blues

求有多少种大小为 nn 的排列，满足其恰好有 aa 个前缀最大值和 bb 个后缀最大值。

a,b,n≤105a,b,n\leq 10^5。对 998244353998244353 取模。

多组数据，T≤2×105,n≤5×104,a,b≤100T\leq 2\times10^5,n\leq 5\times10^4,a,b\leq 100。

题解

如果一个数比它左边一个数小，它就不会是前缀最大值。也就是说一个数是前缀最大值当且仅当它左边没有数比它大。

这和上一道例题“从左边看到这个建筑”的要求是同理的。因此这个题的做法和上一个题一模一样：

ans=(a+b−2a−1)[n−1a+b−2]ans = \binom{a+b-2}{a-1} {n-1\brack a+b-2}

注意到数据范围变了，需要用 NTT 求出第 nn 行斯特林数。

多项式板子的代码会省略。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
const int N=200000;
int n,A,B,fac[max_n],inv[max_n];

inline int C(int n,int m){
    if(n<m || n<0 || m<0) return 0;
    return fac[n]*inv[m]%mod*inv[n-m]%mod;
}

int f[max_n*8],a[max_n*8],b[max_n*8];

inline void sol(int len){
    if(len==1){
        f[1]=1;
        return;
    }
    sol(len>>1);
    int n=len>>1,tmp=1;
    while(tmp<=n+n)
        tmp<<=1;
    for(register int i=0;i<=n;++i)
        a[i]=f[i]*fac[i]%mod;
    for(register int i=0,base=1;i<=n;++i,base=base*n%mod)
        b[i]=inv[i]*base%mod;
    for(register int i=0,j=n;i<j;++i,--j)
        swap(b[i],b[j]);
    for(register int i=n+1;i<tmp;++i)
        a[i]=b[i]=0;
    DXS::Mul(a,b,n,n);

    for(register int i=0;i<=n;++i)
        a[i]=a[i+n]*inv[i]%mod;
    for(register int i=n+1;i<=n*2;++i)
        a[i]=0;
    DXS::Mul(f,a,n,n);
    
    if(len&1){
        for(register int i=n*2+1;i>=1;--i)
            f[i]=(f[i-1]+(len-1)*f[i]%mod)%mod;
        f[0]=f[0]*(len-1)%mod;
    }
}

signed main(){
    n=read(),A=read(),B=read(),fac[0]=inv[0]=1;
    if(n==1){
        if(A+B==2) write(1);
        else write(0);
        return 0;
    }
    for(register int i=1;i<=N;++i)
        fac[i]=fac[i-1]*i%mod;
    inv[N]=mi(fac[N]);
    for(register int i=N-1;i>0;--i)
        inv[i]=inv[i+1]*(i+1)%mod;
    int tmp=1;
    while(tmp<=n) tmp<<=1;
    DXS::init(tmp);
    sol(n-1);
    write(C(A+B-2,A-1)*f[A+B-2]%mod);
    return 0;
}

第一类斯特林数 列

首先我们需要知道上升幂到下降幂的转化：

xn‾=(−1)n(−x)n‾x^{\overline n} = (-1)^n (-x)^{\underline n}

根据第一类斯特林数的性质：

xn‾=∑i=0n[ni]xix^{\overline n} = \sum_{i=0}^n {n\brack i} x^i

把 xx 用 −x-x 代进去：

(−1)nxn‾=∑i=0n[ni](−x)i(-1)^n x^{\underline n} = \sum_{i=0}^n {n\brack i} (-x)^i

因此有：

xn‾=∑i=0n[ni](−1)n−ixix^{\underline n} = \sum_{i=0}^n {n\brack i}(-1)^{n-i} x^i

下面考虑一个式子 (x+1)t(x+1)^t，将其用二项式定理拆开，然后展开组合数：

(x+1)t=∑i=0ti‾i!xi(x+1)^t = \sum_{i=0} \frac{t^{\underline i}}{i!} x^i

上面有一个下降幂，转化成斯特林数，然后交换 ∑\sum：

∑j=0tj∑i=j(−1)i−j[ij]xii!\sum_{j=0} t^j \sum_{i=j} (-1)^{i-j} {i\brack j} \frac{x^i}{i!}

这个式子先放着，把原来的 (x+1)t(x+1)^t 换一种方式展开：

(x+1)t=exp⁡[tln⁡(x+1)](x+1)^t = \exp[t\ln(x+1)]

然后泰勒：

∑i=0tiln⁡i(x+1)i!\sum_{i=0} t^i \frac{\ln^i(x+1)}{i!}

两个式子放在一起：

∑j=0tj∑i=j(−1)i−j[ij]xii!=∑i=0tiln⁡i(x+1)i!\sum_{j=0} t^j \sum_{i=j} (-1)^{i-j} {i\brack j} \frac{x^i}{i!} = \sum_{i=0} t^i \frac{\ln^i(x+1)}{i!}

然后你会发现……

∑i=m(−1)i−m[im]xii!=ln⁡m(x+1)m!\sum_{i=m} (-1)^{i-m} {i\brack m} \frac{x^i}{i!} = \frac{\ln^m(x+1)}{m!}

多项式 ln⁡\ln 和快速幂做到 nlog⁡nn\log n。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
int n,k,fac[max_n],inv[max_n];
int f[max_n*8],g[max_n*8];

inline void sol(){
    int tmp=1;
    while(tmp<=n) tmp<<=1;
    DXS::init(tmp);

    g[0]=g[1]=1;
    DXS::Ln(g,f,tmp),
    DXS::Pow(f,g,n,k);

    for(register int i=0;i<=n;++i)
        f[i]=g[i]*inv[k]%mod*fac[i]%mod*((i-k)&1?mod-1:1)%mod;
}

signed main(){
    n=read(),k=read(),N=n;
    if(n<k){
        for(register int i=0;i<=n;++i)
            write(0),putchar(' ');
        return 0;
    }
    fac[0]=inv[0]=1;
    for(register int i=1;i<=n;++i)
        fac[i]=fac[i-1]*i%mod;
    inv[n]=mi(fac[n]);
    for(register int i=n-1;i>0;--i)
        inv[i]=inv[i+1]*(i+1)%mod;
    sol();
    for(register int i=0;i<=n;++i)
        write(f[i]),putchar(' ');
    return 0;
}

第二类斯特林数

基础

定义：把 nn 个不同的球放到 mm 个相同的盒子里，盒子不能为空的方案数。记为 {nm}{n\brace m}。

根据定义有第二类斯特林数的递推式：

{nm}={n−1m−1}+m{n−1m}{n\brace m} = {n-1\brace m-1} + m{n-1\brace m}

意义为：考虑第 nn 个球怎么放，要么放在一个已有的盒子里，要么新开一个。

有通项公式：

{nm}=1m!∑i=0m(−1)i(mi)(m−i)n{n\brace m} = \frac{1}{m!} \sum_{i=0}^m (-1)^i\binom{m}{i} (m-i)^n

证明考虑容斥，枚举至少多少盒子为空，在 mm 里选出 ii 个盒子为空，剩下的 nn 个球随意分配。注意到这样计算会认为盒子之间是不同的，因此最后要除掉一个 m!m!。

第二类斯特林数还有一个奇妙的性质：

xn=∑i=0n(xi){ni}i!=∑i=0x{ni}xi‾x^n = \sum_{i=0}^n \binom{x}{i} {n\brace i} i! = \sum_{i=0}^x {n\brace i} x^{\underline i}

证明

第二个等式显然（把组合数拆开，然后把阶乘约掉），考虑第一个等式。求其组合意义：nn 个不同的球放入 mm 个不同的个盒子的方案数，看作枚举有多少个盒子非空，然后把 nn 个球放入的方案数的和，因为第二类斯特林数的盒子是相同的，所以还要乘上 i!i!。

CF961G Partitions

给定 nn 个物品，每个物品有权值 wiw_i，定义一个集合 SS 的权值为 W(S)=∣S∣∑x∈SwxW(S) = \left|S\right| \sum_{x\in S} w_x。

定义一个划分的权值为其划分出的所有集合权值的和。

求把 nn 个物品划分为 kk 个集合的所有方案的权值和，对 109+710^9+7 取模。

n≤2×105n\leq 2\times 10^5。

题解

考虑计算集合贡献时 ∣S∣\left|S\right| 表示啥，其实就是每个物品会对系数产生 11 的贡献。而划分好集合后，每个点都对当前点有 wiw_i 的贡献。

钦定一个点，则每个点对自己的贡献是 {nm}n\brace m，而一个点对其他点的贡献是：把其他点划分好集合，则这个点对 ii 的贡献是把自己和 ii 放在一个集合里，也就是 {n−1k}n-1 \brace k。因此：

ans=[{nk}+(n−1){n−1k}]∑wians = \left[{n\brace k} + (n-1){n-1 \brace k}\right] \sum w_i

1
2
3
4
5
6
7
8
9
10
11
12
13
namespace sol1{
    inline int S(int n,int m){
        int res=0;
        for(register int i=0;i<=m;++i){
            res+=C(m,i)*mi(m-i,n)%mod*(i&1?-1:1),
            res=(res+mod)%mod;
        }
        return res*inv[m]%mod;
    }
    inline void sol(){
        write((S(n,k)+(n-1)*S(n-1,k)%mod)%mod*sumw%mod);
    }
}

第二类斯特林数 行

由通项公式：

{nm}=1m!∑i=0m(−1)i(mi)(m−i)n{n\brace m} = \frac{1}{m!} \sum_{i=0}^m (-1)^i\binom{m}{i} (m-i)^n

把组合数拆开，约掉 m!m!：

∑i=0m(−1)ii!⋅(m−i)n(m−i)!\sum_{i=0}^m \frac{(-1)^i}{i!}\cdot \frac{(m-i)^n}{(m-i)!}

这就是很明显的卷积形式了，NTT 即可。复杂度 nlog⁡nn\log n。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int fac[max_n],inv[max_n];
int f[max_n*8],g[max_n*8];

signed main(){
    n=read(),fac[0]=inv[0]=1;
    for(register int i=1;i<=n;++i)
        fac[i]=fac[i-1]*i%mod;
    inv[n]=mi(fac[n]);
    for(register int i=n-1;i>0;--i)
        inv[i]=inv[i+1]*(i+1)%mod;
    int tmp=1;
    while(tmp<=n) tmp<<=1;
    DXS::init(tmp);
    for(register int i=0;i<=n;++i){
        f[i]=mi(i,n)*inv[i]%mod,
        g[i]=(i&1?mod-inv[i]:inv[i]);
    }
    DXS::Mul(f,g,n+1,n+1);
    for(register int i=0;i<=n;++i)
        write(f[i]),putchar(' ');
    return 0;
}

BZOJ5093 图的价值

给定 n,kn,k，求所有 nn 个点的带标号简单无向图的价值和对 998244353998244353 取模的结果。一个图的价值为每个点度数的 kk 次方和。

n≤109,k≤2×105n\leq 10^9,k\leq 2\times 10^5。

题解

枚举一个点的度：

ans=n∑i=0n−1ik⋅2(n−1)(n−2)2(n−1i)ans = n\sum_{i=0}^{n-1} i^k \cdot 2^{\frac{(n-1)(n-2)}{2}}\binom{n-1}{i}

即，这个度的贡献为 iki^k，达到这个度需要在 n−1n-1 条可行的边里选 ii 条链出去。剩下的边随意。

把 22 的幂提出去，只考虑里面的部分，用第二类斯特林数把 iki^k 拆开：

∑i=0n−1(n−1i)∑j=0min⁡(i,k)(ij){kj}j!\sum_{i=0}^{n-1} \binom{n-1}{i} \sum_{j=0}^{\min(i,k)} \binom{i}{j} {k\brace j} j!

交换 sigma：

∑j=0min⁡(n−1,k){kj}j!∑i=jn−1(ij)(n−1i)\sum_{j=0}^{\min(n-1,k)} {k\brace j} j! \sum_{i=j}^{n-1} \binom{i}{j} \binom{n-1}{i}

组合恒等式：

∑j=0min⁡(n−1,k){kj}j!∑i=jn−1(n−j−1i−j)\sum_{j=0}^{\min(n-1,k)} {k\brace j} j! \sum_{i=j}^{n-1} \binom{n-j-1}{i-j}

后面的东西显然是 2n−j−12^{n-j-1}。因此答案为：

ans=2(n−1)(n−2)2n∑i=0min⁡(n−1,k)i!{ki}(n−1i)2n−i−1ans = 2^{\frac{(n-1)(n-2)}{2}}n \sum_{i=0}^{\min(n-1,k)}i!{k\brace i}\binom{n-1}{i} 2^{n-i-1}

求第 kk 行的第二类斯特林数即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
int n,k,N,fac[max_n],inv[max_n];
int f[max_n*8],g[max_n*8],ans,c[max_n];

inline int C(int n,int m){
    if(n<m || n<0 || m<0) return 0;
    return fac[n]*inv[m]%mod*inv[n-m]%mod;
}

inline void sol(){
    int tmp=1;
    while(tmp<=k) tmp<<=1;
    DXS::init(tmp);
    for(register int i=0;i<=k;++i){
        f[i]=mi(i,k)*inv[i]%mod,
        g[i]=(i&1?mod-inv[i]:inv[i]);
    }
    DXS::Mul(f,g,k+1,k+1);
}

signed main(){
    n=read(),k=read(),N=min(n-1,k),fac[0]=inv[0]=1;
    for(register int i=1;i<=k;++i)
        fac[i]=fac[i-1]*i%mod;
    inv[k]=mi(fac[k]);
    for(register int i=k-1;i>0;--i)
        inv[i]=inv[i+1]*(i+1)%mod;
    c[0]=mi(2,n-1);
    for(register int i=1;i<=N;++i)
        c[i]=c[i-1]*inv[2]%mod*(n-i)%mod;
    sol();

    for(register int i=0;i<=N;++i){
        ans+=f[i]%mod*c[i]%mod,
        ans%=mod;
    }
    write(ans*n%mod*mi(2,((n-1)*(n-2)/2)%(mod-1))%mod);
    return 0;
}

第二类斯特林数 列

考虑第二类斯特林数的组合意义，如果把“相同的盒子”换成“不同的盒子”，只要让它乘上 m!m! 即可，因此考虑让 nn 个不同小球放入 kk 个不同盒子的方案数。

直接 EGF，设方案数的 EGF 为 FF，单个盒子的 EGF 为 GG，则 F=Gk,G=∑i=1nxii!F=G^k,G = \sum_{i=1}^n \frac{x^i}{i!}。

因此有：

k!∑i=0{ik}xii!=Fk! \sum_{i=0}{i\brace k}\frac{x^i}{i!} = F

多项式快速幂即可，复杂度 nlog⁡nn\log n。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
int n,k,fac[max_n],inv[max_n];
int f[max_n*8],g[max_n*8];

inline void sol(){
    int tmp=1;
    while(tmp<=n) tmp<<=1;
    DXS::init(tmp);
    for(register int i=1;i<=n;++i)
        g[i]=inv[i];
    DXS::Pow(g,f,n,k);
    for(register int i=0;i<=n;++i)
        f[i]=f[i]*fac[i]%mod*inv[k]%mod;
}

signed main(){
    n=N=read(),k=read();
    if(n<k){
        for(register int i=0;i<=n;++i)
            write(0),putchar(' ');
        return 0;
    }
    fac[0]=inv[0]=1;
    for(register int i=1;i<=n;++i)
        fac[i]=fac[i-1]*i%mod;
    inv[n]=mi(fac[n]);
    for(register int i=n-1;i>0;--i)
        inv[i]=inv[i+1]*(i+1)%mod;
    sol();
    for(register int i=0;i<=n;++i)
        write(f[i]),putchar(' ');
    return 0;
}

斯特林反演

求一列第一类斯特林数，我们用上升幂到下降幂的转化，结合第一类斯特林数的性质，得到了这样的式子：

xn‾=∑i=0n[ni](−1)n−ixix^{\underline n} = \sum_{i=0}^n {n\brack i}(-1)^{n-i} x^i

第二类斯特林数里有这样的性质：

xn=∑i=0x{ni}xi‾x^n = \sum_{i=0}^x {n\brace i} x^{\underline i}

根据下降幂转上升幂 xn‾=(−1)n(−x)n‾x^{\underline n} = (-1)^n(-x)^{\overline n}：

xn=∑i=0n{ni}(−1)n−ixi‾x^n = \sum_{i=0}^n {n\brace i} (-1)^{n-i} x^{\overline i}

结合第一类斯特林数的另一个性质联立：

{xn=∑i=0n{ni}xi‾xn‾=∑i=0n[ni]xixn=∑i=0n{ni}(−1)n−ixi‾xn‾=∑i=0n[ni](−1)n−ixi\begin{cases} x^n = \sum_{i=0}^n {n\brace i} x^{\underline i} \\ x^{\overline n} = \sum_{i=0}^n {n\brack i} x^i \\ x^n = \sum_{i=0}^n {n\brace i} (-1)^{n-i} x^{\overline i} \\ x^{\underline n} = \sum_{i=0}^n {n\brack i}(-1)^{n-i} x^i \end{cases}

把第二个套进第三个：

xn=∑i=0n{ni}(−1)n−i∑j=0i[ij]xjx^n = \sum_{i=0}^n {n\brace i} (-1)^{n-i} \sum_{j=0}^i {i\brack j} x^j

交换 ∑\sum，分离出 j=nj=n 的一项：

xn=xn+∑j=0n−1xj∑i=jn(−1)n−i{ni}[ij]x^n = x^n + \sum_{j=0}^{n-1} x^j \sum_{i=j}^n (-1)^{n-i} {n\brace i}{i\brack j}

因此：

∑i=jn(−1)n−i{ni}[ij]=0\sum_{i=j}^n (-1)^{n-i} {n\brace i}{i\brack j} =0

类似地，有：

∑i=mn(−1)m+i or n+i{ni}[im]=[n=m]\sum_{i=m}^n (-1)^{m+i \text{ or } n+i} {n\brace i}{i\brack m} = [n=m]

∑i=mn(−1)m+i or n+i[ni]{im}=[n=m]\sum_{i=m}^n (-1)^{m+i \text{ or } n+i} {n\brack i}{i\brace m} = [n=m]

这两个公式被称为反转公式。而斯特林反演的一个常用公式，就是取 m=1m=1 的特例：

∑i=1n(−1)i+1{ni}(i−1)!=[n=1]\sum_{i=1}^n (-1)^{i+1} {n\brace i} (i-1)! = [n=1]

当然还有另一种形式，设 f(n)=∑i=0n{ni}g(i)f(n) = \sum_{i=0}^n {n\brace i}g(i)，则：

g(n)=∑i=0n(−1)n−i[ni]f(i)g(n) = \sum_{i=0}^n (-1)^{n-i} {n\brack i} f(i)

证明为直接代入，然后发现和反转公式的推倒步骤类似。

BZOJ4671 异或图

定义两个点数相同的图的异或为一个新的图，其中在原来两个图中出现次数和为 11 的边在新图中，其它边不在新图中。

给定 ss 个点数均为 nn 的图，求有多少种选择若干个图的方案，使得这些图的异或是一个连通图。

2≤n≤10,s≤602\leq n\leq 10,s\leq 60。

题解

直接考虑连通这个条件不太好作，考虑连通块个数。nn 很小，直接枚举点的子集划分。将其加入到 mm 个子集内，强制不同点集的点不连边，相同点集的随意连。设按这种方法划分的方案数为 fmf_m，最后恰好形成 mm 个连通块的方案数为 gmg_m。则 fmf_m 相当于在 gk(k≥m)g_k(k\geq m) 种选择 mm 个集合合并：

fm=∑i=mn{im}gif_m = \sum_{i=m}^n {i\brace m} g_i

斯特林反演：

gm=∑i=mn(−1)i−m[im]fig_m = \sum_{i=m}^n (-1)^{i-m} {i\brack m} f_i

整个连通图连通的方案数为 g1g_1：

ans=∑i=1n(−1)i−1(i−1)!fians = \sum_{i=1}^n (-1)^{i-1} (i-1)! f_i

nn 很小，复杂度不成问题，考虑怎么求 ff。

仍然枚举子集划分，考虑一个图的选择情况（选或不选）对应了一个未知数（00 或 11）。那么对于每一条确定有或者没有的边，我们都可以列出一个异或方程，形成异或方程组。而对于一个未知数 xx 如果 xx 为主元，则必须在或不在子集里，若 xx 为自由元，则在或不在都可以。

设 cntcnt 为自由元数量，则这种子集划分产生的贡献为 2cnt2^{cnt}。因为是异或方程组，求自由元数量可以线性基解决。复杂度 O(n2sBn)\mathcal O(n^2sB_n)，BB 为贝尔数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int max_n=66;
inline int read(){
    int x=0;bool w=0;char c=getchar();
    while(c<'0' || c>'9') w|=c=='-',c=getchar();
    while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return w?-x:x;
}
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10^48);
}

struct LB{
    int p[max_n],n,cnt;
    inline void init(int x){
        n=x,cnt=0;
        memset(p,0,sizeof(p));
    }
    inline void insert(int x){
        for(register int i=n;i>=0;--i)
            if(x&(1LL<<i)){
                if(!p[i]){
                    ++cnt,p[i]=x;
                    return;
                }
                x^=p[i];
            }
    }
    inline int askcan(){
        return (1LL<<cnt);
    }
    inline int askcant(){
        return (1LL<<(n-cnt));
    }
}lb;

int n,s,ans,fac[max_n];

int col[max_n],f[max_n];
bool e[max_n][max_n][max_n];

inline void dfs(int l,int m){
    if(l>n){
        lb.init(s);
        for(register int i=1;i<=n;++i)
            for(register int j=i+1;j<=n;++j){
                if(col[i]==col[j])
                    continue;
                int x=0;
                for(register int k=0;k<s;++k)
                    if(e[k][i][j])
                        x|=(1LL<<k);
                lb.insert(x);
            }
        f[m]+=lb.askcant();
        return;
    }
    for(register int i=1;i<=m;++i){
        col[l]=i;
        dfs(l+1,m);
    }
    col[l]=m+1;
    dfs(l+1,m+1);
}

signed main(){
    s=read();
    for(register int id=0;id<s;++id){
        string p;
        cin>>p;int tmp=p.size();
        for(register int i=2;i<=10;++i)
            if(i*(i-1)/2==tmp){
                n=i;
                break;
            }
        for(register int i=1,k=0;i<=n;++i)
            for(register int j=i+1;j<=n;++j,++k)
                if(p[k]=='1')
                    e[id][i][j]=1;
    }
    fac[0]=1;
    for(register int i=1;i<=n;++i)
        fac[i]=fac[i-1]*i;
    dfs(1,0);
    for(register int i=1;i<=n;++i){
        ans+=f[i]*fac[i-1]*(i&1?1:-1);
    }
    write(ans);
    return 0;
}
  • 标题: 斯特林数入门
  • 作者: Arahc
  • 创建于 : 2022-02-09 08:00:00
  • 更新于 : 2023-03-19 09:11:02
  • 链接: https://arahc.github.io/2022/02/09/【笔记】斯特林数入门/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
目录
斯特林数入门
  1. 第一类斯特林数
    1. 基础
    2. 第一类斯特林数 行
    3. 第一类斯特林数 列
  2. 第二类斯特林数
    1. 基础
    2. 第二类斯特林数 行
    3. 第二类斯特林数 列
  3. 斯特林反演