浅谈斯特林数及斯特林反演
y2823774827y
2019-04-14 09:52:25
## **更好的阅读体验$\Longrightarrow$[My Blog](https://www.cnblogs.com/y2823774827y/p/10700231.html)**
## $\color{SpringGreen}\text{历史小芝士}$
在组合数学中，斯特林$(Stirling)$数可指两类数，第一类斯特林数和第二类斯特林数
这些均由$18$世纪数学家$James Stirling$提出的，并在著作《$Methodous Differentialis$》中首次使用
自此，斯特林数及反演成为又一广泛运用到处理组合问题的一大利器
## $\color{SpringGreen}\text{第一类斯特林数}$
## 定义
$\begin{bmatrix}n\\m \end{bmatrix}$表示$n$个元素分成$m$个环的方案数
显然：
$$\displaystyle \begin{bmatrix}n\\m \end{bmatrix}=\begin{bmatrix}n-1\\m-1 \end{bmatrix}+(n-1)*\begin{bmatrix}n-1\\m \end{bmatrix}$$
理解：考虑从$n-1$个元素推过来，如果两个空环肯定是不符合的
$~~~~~~~~~~$空一个环则单独成环，如果$n-1$的时候就没有空环就任意放在一个元素前
## 性质
- $\displaystyle n!=\sum\limits_{i=0}^n \begin{bmatrix}n\\i \end{bmatrix}$
理解：其实本质就是置换，一个环则为一组轮换，每种排列都会对应着唯一 一种置换
- $\displaystyle x^{\underline n}=\sum\limits_{i=0}^n \begin{bmatrix}n\\i \end{bmatrix}(-1)^{n-i}x^i$
归纳法：
$\displaystyle x^{\underline{n+1}}=(x-n)x^{\underline n}$
$~~~~~~~~=\displaystyle (x-n)\sum\limits_{i=0}^n \begin{bmatrix}n\\i \end{bmatrix}(-1)^{n-i}x^i$
$~~~~~~~~=\displaystyle x\sum\limits_{i=0}^{n} \begin{bmatrix}n\\i \end{bmatrix}(-1)^{n-i}x^{i}-n\sum\limits_{i=0}^n \begin{bmatrix}n\\i \end{bmatrix}(-1)^{n-i} x^i$
$~~~~~~~~=\displaystyle \sum\limits_{i=0}^{n} \begin{bmatrix}n\\i \end{bmatrix}(-1)^{n-i}x^{i+1}-n\sum\limits_{i=0}^{n+1} \begin{bmatrix}n\\i \end{bmatrix}(-1)^{n-i} x^i$
$~~~~~~~~=\displaystyle \sum\limits_{i=1}^{n+1} \begin{bmatrix}n\\i-1 \end{bmatrix}(-1)^{n-i+1}x^{i}+n\sum\limits_{i=0}^{n+1} \begin{bmatrix}n\\i \end{bmatrix}(-1)^{n-i+1} x^i$
$~~~~~~~~=\displaystyle \sum\limits_{i=1}^{n+1} ( \begin{bmatrix}n\\i-1 \end{bmatrix} +n*\begin{bmatrix}n\\i \end{bmatrix})(-1)^{n-i+1}x^{i}$
$~~~~~~~~=\displaystyle \sum\limits_{i=1}^{n+1} \begin{bmatrix}n+1\\i \end{bmatrix}(-1)^{n-i+1}x^{i}$
$~~~~~~~~=\displaystyle \sum\limits_{i=0}^{(n+1)} \begin{bmatrix}n+1\\i \end{bmatrix}(-1)^{(n+1)-i}x^{i}$
- $\displaystyle x^{\overline n}=\sum_{i=0}^n \begin{bmatrix}n\\i \end{bmatrix}x^i$
证明类上，不再赘述
## 求第一类斯特林数
- $\displaystyle \sum_{i=0}^n \begin{bmatrix}n\\i \end{bmatrix}x^i=\prod_{i=0}^{n-1}(x+i)$
$\begin{array}{c c c}~&0&1&2&3&4\\0&0&0&0&0&0\\1&0&1&0&0&0\\2&0&1&1&0&0\\3&0&2&3&1&0\\4&0&6&11&6&1\end{array}$
其实把表刷出来就差不多了，可以理解为根据$\begin{bmatrix}n\\m \end{bmatrix}=\begin{bmatrix}n-1\\m-1 \end{bmatrix}+(n-1)*\begin{bmatrix}n-1\\m \end{bmatrix}$逐渐转移
至此，我们可以通过分治$FFTO(nlog^2n)$求出一行的第一类斯特林数
- 还有一种类似于多项式求逆模式$O(nlogn)$的方法
$$F(x)^n=\prod\limits_{i=0}^{n-1}(x+i),F(x)^{2n}=F(x)^nF(x+n)^n$$
考虑当我们求出$F(x)^n=\displaystyle \sum\limits_{i=0}^{n}a_ix^i$：
$F(x+n)^{n}=\displaystyle \sum\limits_{i=0}^{n}a_i(x+n)^i$
$~~~~~~~~~~~~=\displaystyle \sum\limits_{i=0}^na_i\sum\limits_{j=0}^i{i\choose j}n^{i-j}x^j$
$~~~~~~~~~~~~=\displaystyle \sum\limits_{i=0}^n(\sum\limits_{j=i}^n {j\choose i}n^{j-i}a_j)x^i$
$~~~~~~~~~~~~=\displaystyle \sum\limits_{i=0}^n(\sum\limits_{j=i}^n \frac{j!}{i!(j-i)!}n^{j-i}a_j)x^i$
$~~~~~~~~~~~~=\displaystyle \sum\limits_{i=0}^n (i!)^{-1}x^i (\sum\limits_{j=i}^n (\frac{n^{j-i}}{(j-i)!})\cdot (j!a_j))$
我们通过左半部分系数能得到右半部分系数，再相乘一下就得到了总体的系数
代码运用到了下方例题，故在这里不重复放了
## $\color{SpringGreen}\text{第二类斯特林数}$
## 定义
$\begin{Bmatrix}n\\m\end{Bmatrix}$表示$n$个有区别的小球丢进$m$个无区别的盒子，无空盒子的方案数
显然：
$$\begin{Bmatrix}n\\m\end{Bmatrix}=\begin{Bmatrix}n-1\\m-1\end{Bmatrix}+m*\begin{Bmatrix}n-1\\m\end{Bmatrix}$$
理解：考虑从$n-1$个小球推过来，如果两个空盒子肯定是不符合的
$~~~~~~~~~~$空一个盒子则只能放到那个空盒子里面了，如果$n-1$的时候就没有空箱子就随便放
## 性质
$$\displaystyle m^n=\sum_{i=0}^{m}\begin{Bmatrix}n\\i\end{Bmatrix}*i!*C(m,i)$$
当然也可以写成：
$$m^n=\displaystyle \sum\limits_{i=0}^m \begin{Bmatrix}n\\i\end{Bmatrix}*m^{\underline i}$$
到后面反演时我们会这样写：
$$m^n=\sum\limits_{i=0}^n \begin{Bmatrix}n\\i\end{Bmatrix}*m^{\underline i}$$
看看后面的$m^{\underline i}$就懂了
理解：$m^n$为$n$个有区别的小球丢进$m$个有区别的盒子，允许空盒子
$~~~~~~~~~~$枚举有效盒子的个数，再从$m$个盒子选$i$个盒子，然后$n$个小球丢进$i$个盒子
## 转换到组合表示
第二类斯特林数显然是和排列组合有关系的，转换过来：
$$\displaystyle \begin{Bmatrix}n\\m\end{Bmatrix}=\frac{1}{m!}\sum\limits_{k=0}^m(-1)^kC(m,k)(m-k)^n$$
理解：如果空箱子的情况我们也算进去，答案显然是$\frac{m^n}{m!}$
$~~~~~~~~~~$反过来求第二类斯特林数，又得减掉这种情况：
$~~~~~~~~~~$选$k$个空盒子，然后小球放到其他的盒子里
$~~~~~~~~~~$但最后我们求出来的答案为有区别的盒子，转换过来要$×\frac{1}{m!}$
## 求第二类斯特林数
大概都能猜到是卷积形式了吧，随手展开一下：
$\displaystyle \begin{Bmatrix}n\\m\end{Bmatrix}=\frac{1}{m!}\sum\limits_{k=0}^m(-1)^k\frac{m!}{k!(m-k)!}(m-k)^n$
$~~~~~~~~~=\displaystyle \sum\limits_{k=0}^m\frac{(-1)^k(m-k)^n}{k!(m-k)!}$
至此，我们能实现$O(nlogn)$求出$S(n)$这一行的第二类斯特林
## 第二类斯特林数与自然数幂的关系
$Sum(n)=\displaystyle \sum\limits_{i=0}^n i^k$
$~~~~~~~~~~~~~~=\displaystyle \sum\limits_{i=0}^n\sum\limits_{j=0}^k\begin{Bmatrix}k\\j \end{Bmatrix}i^{\underline j}$
$~~~~~~~~~~~~~~=\displaystyle \sum\limits_{j=0}^k\begin{Bmatrix}k\\j \end{Bmatrix}\sum\limits_{i=0}^n i^{\underline j}$
$~~~~~~~~~~~~~~=\displaystyle \sum\limits_{j=0}^k \begin{Bmatrix}k\\j \end{Bmatrix}j!\sum\limits_{i=0}^nC_i^j$
$~~~~~~~~~~~~~~=\displaystyle \sum\limits_{j=0}^k \begin{Bmatrix}k\\j \end{Bmatrix}j!C_{n+1}^{j+1}$
$~~~~~~~~~~~~~~=\displaystyle \sum\limits_{j=0}^k \begin{Bmatrix}k\\j \end{Bmatrix} \frac{(n+1)^{\underline {j+1}}}{j+1}$
关于$\displaystyle \sum\limits_{i=0}^nC_i^j=C_{n+1}^{j+1}$的理解：枚举$j+1$的右端点$i+1$，则相当于从$i$个点中选$j$个点
## $\color{SpringGreen}\text{斯特林反演}$
## 定义
斯特林反演：$\displaystyle f(n)=\sum\limits_{k=0}^n \begin{Bmatrix}n\\k \end{Bmatrix}g(k)\Longleftrightarrow g(n)=\sum\limits_{k=0}^n(-1)^{n-k}\begin {bmatrix} n\\k \end{bmatrix}f(k)$
## 总结上面我们所推倒的性质
- $x^{\underline n}=\displaystyle \sum\limits_{i=0}^n \begin{bmatrix}n\\i \end{bmatrix}(-1)^{n-i}x^i,x^{\overline n}=\sum_{i=0}^n \begin{bmatrix}n\\i \end{bmatrix}x^i$
- $m^n=\displaystyle \sum\limits_{i=0}^n \begin{Bmatrix}n\\i\end{Bmatrix}*m^{\underline i}$
## 补充
$$x^{\underline n}=(-1)^n (-x)^{\overline n},x^{\overline n}=(-1)^n (-x)^{\underline n}$$
## 前置
我们先证这个**反转公式**
$\displaystyle \sum\limits_{k=m}^n (-1)^{n-k}\begin{bmatrix}n\\k\end{bmatrix} \begin{Bmatrix}k\\m\end{Bmatrix}=[m=n]$
$\displaystyle \sum\limits_{k=m}^n (-1)^{n-k}\begin{Bmatrix}n\\k\end{Bmatrix} \begin{bmatrix}k\\m\end{bmatrix}=[m=n]$
反转公式**1**：
$m^{\underline n}=\displaystyle \sum\limits_{i=0}^n \begin{bmatrix}n\\i\end{bmatrix}(-1)^{n-i}m^i$
$~~~~~~=\displaystyle \sum\limits_{i=0}^n \begin{bmatrix}n\\i\end{bmatrix}(-1)^{n-i}\displaystyle \sum\limits_{j=0}^i \begin{Bmatrix}i\\j\end{Bmatrix}m^{\underline j}$
$~~~~~~=\displaystyle \sum\limits_{i=0}^n m^{\underline i}\sum\limits_{j=i}^n (-1)^{n-j} \begin{bmatrix}n\\j\end{bmatrix} \begin{Bmatrix}j\\i\end{Bmatrix}$
反转公式**2**：
$m^n=\displaystyle \sum\limits_{i=0}^n\begin{Bmatrix}n\\i\end{Bmatrix}m^{\underline i}$
$~~~~~~=\displaystyle \sum\limits_{i=0}^n\begin{Bmatrix}n\\i\end{Bmatrix}(-1)^i(-m)^{\overline i}$
$~~~~~~=\displaystyle \sum\limits_{i=0}^n\begin{Bmatrix}n\\i\end{Bmatrix}(-1)^i\sum\limits_{j=0}^i \begin{bmatrix}i\\j\end{bmatrix}(-m)^j$
$~~~~~~=\displaystyle \sum\limits_{i=0}^n m^i\sum\limits_{j=i}^n(-1)^{i-j} \begin{Bmatrix}n\\j\end{Bmatrix}\begin{bmatrix}j\\i\end{bmatrix}$
## 证明斯特林反演
已知：$g(n)=\displaystyle \sum\limits_{k=0}^n(-1)^{n-k}\begin {bmatrix} n\\k \end{bmatrix}f(k)$
$f(n)=\displaystyle \sum\limits_{k=0}^n [k=n]f(k)$
$~~~~~~~~=\displaystyle \sum\limits_{k=0}^n\sum\limits_{j=k}^n \begin {Bmatrix} n\\j \end{Bmatrix}\begin {bmatrix} j\\k \end{bmatrix}(-1)^{j-k}f(k)$
$~~~~~~~~=\displaystyle \sum\limits_{k=0}^n \begin {Bmatrix} n\\k \end{Bmatrix}\sum\limits_{j=0}^k (-1)^{k-j}\begin {bmatrix} k\\j \end{bmatrix}f(j)$
$~~~~~~~~=\displaystyle \sum\limits_{k=0}^n \begin {Bmatrix} n\\k \end{Bmatrix}g(k)$
## $\color{SpringGreen}\text{斯特林数及斯特林反演的应用}$
## 例题一
[CF960G](https://www.luogu.org/problemnew/show/CF960G)
## 题意
>定义排列有最大值前缀个数$val1$及最大值后缀个数$val2$，
如$i$为一个最大值前缀则$0<j<i$：$a_j<a_i$，后缀同理，对于给定的$n,x,y$，求$1$~$n$有多少种排列满足$val1=a,val2=b$
## 做法
设$f(i,j)$为$i$个数的序列，有$j$个前缀最大值的方案数
我们考虑每次添一个最小数，则有：$f(i,j)=f(i-1,j)+(i-1)*f(i-1,j-1)$，显然这是第一类斯特林数
从而我们得到一个朴素的答案：
$$\displaystyle Ans=\sum\limits_{i=1}^{n}f_{i,a-1}×f_{n-1-i,b-1}×C_{n-1}^i$$
理解：枚举$i+1$为最大值添的位置，则已限制了前缀最值个数及后缀最值个数，然后再乘上前半部分所填的数
观察$f_{i,a-1}×f_{n-1-i,b-1}$，发现第一维和唯一：
$$\displaystyle Ans=\begin{bmatrix}n-1\\a+b-2\end{bmatrix}C_{a+b-2}^{a-1}$$
可能会有点难理解：等同于分类成$a+b-2$个环，而环是不考虑顺序的，所以我们选择不考虑打乱顺序地选择环
至此，我们唯一需要的就是快速求出第一类斯特林数$\begin{bmatrix}n-1\\a+b-2\end{bmatrix}$
即使是单个数也无法有特殊的公式快速得出，所以我们用与求整行第一类斯特林数的方法求出
就是上方提到的$O(nlogn)$做法，单独求第一类斯特林数的代码$\Longrightarrow$[点这里(有少量注释)](https://www.cnblogs.com/y2823774827y/p/10700231.html)
## Code
```cpp
#include<bits/stdc++.h>
typedef int LL;
const LL mod=998244353,g=3,_g=332748118,maxn=2e5+9;
inline LL Pow(LL base,LL b){
LL ret(1);
while(b){
if(b&1) ret=1ll*ret*base%mod; base=1ll*base*base%mod; b>>=1;
}return ret;
}
LL r[maxn],W[maxn];
inline LL Fir(LL n){
LL limit(1),len(0),up(n<<1);
while(limit<up){
limit<<=1; ++len;
}
for(LL i=0;i<limit;++i) r[i]=(r[i>>1]>>1)|((i&1)<<len-1);
return limit;
}
inline void NTT(LL *a,LL n,LL type){
for(LL i=0;i<n;++i) if(i<r[i]) std::swap(a[i],a[r[i]]);
for(LL mid=1;mid<n;mid<<=1){
LL wn(Pow(type?g:_g,(mod-1)/(mid<<1)));
W[0]=1; for(LL i=1;i<mid;++i) W[i]=1ll*W[i-1]*wn%mod;
for(LL R=mid<<1,j=0;j<n;j+=R)
for(LL k=0;k<mid;++k){
LL x(a[j+k]),y(1ll*W[k]*a[j+mid+k]%mod);
a[j+k]=1ll*(x+y)%mod; a[j+mid+k]=1ll*(x-y+mod)%mod;
}
}
}
LL T[maxn],F[maxn],H[maxn],fac[maxn],fav[maxn],tmp[maxn],sum[maxn],B[maxn];
inline LL Mul(LL n,LL *a,LL *b,LL *ans){
LL limit(Fir(n));
NTT(a,limit,1); NTT(b,limit,1);
for(LL i=0;i<limit;++i) ans[i]=1ll*a[i]*b[i]%mod;
NTT(ans,limit,0);
for(LL i=((n-1)<<1)+1;i<limit;++i) a[i]=b[i]=0;
return Pow(limit,mod-2);
}
inline void Solve(LL n,LL *a){
if(!n){ a[0]=1; return; }
if(n==1){ a[1]=1; return; }
LL len(n/2);
Solve(len,a);
for(LL i=0;i<=len;++i){
F[i]=1ll*Pow(len,i)*fav[i]%mod;
H[i]=1ll*fac[i]*a[i]%mod;
}
std::reverse(H,H+len+1);
LL limit(Fir(len+1));
NTT(F,limit,1); NTT(H,limit,1);
for(LL i=0;i<limit;++i) F[i]=1ll*F[i]*H[i]%mod;
NTT(F,limit,0);
LL ty(Pow(limit,mod-2));
for(LL i=0;i<=len;++i) tmp[i]=1ll*F[len-i]*ty%mod*Pow(fac[i],mod-2)%mod;
for(LL i=(len<<1);i<=limit;++i) F[i]=H[i]=0;
LL val(Mul(len+1,a,tmp,B));
for(LL i=0;i<=(len<<1);++i) a[i]=1ll*B[i]*val%mod;
if(n&1)
for(LL i=n;i>=1;--i) a[i]=1ll*(a[i-1]+1ll*(n-1)*a[i]%mod)%mod;
}
LL n,a,b,m;
LL ans[maxn];
int main(){
scanf("%d%d%d",&n,&a,&b);
LL val;
val=fac[0]=fac[1]=1;
for(LL i=2;i<=n;++i) val=fac[i]=1ll*val*i%mod;
val=fav[n]=Pow(fac[n],mod-2);
for(LL i=n;i>=1;--i) val=fav[i-1]=1ll*val*i%mod;
Solve(n-1,ans);
n=a+b-2; m=a-1;
printf("%d\n",1ll*ans[n]*fac[n]%mod*fav[m]%mod*fav[n-m]%mod%mod);
}
```
## 例题二
[【BZOJ4671】异或图](https://www.lydsy.com/JudgeOnline/problem.php?id=4671)
## 题意
> 给多个图，求异或边后所有点联通的方案数
## 做法
直接处理显然很难，我们考虑范围扩大以求容斥或反演这类的帮助
$f_i$表示至少有$i$个联通块的方案，形如设立$i$个联通块轮廓，联通块内连边随意，联通块与联通块之间无连边
$g_i$表示恰好有$i$个联通块的方案，形如设立$i$个联通块轮廓，在保证内部联通的情况下，外部块与块间无连边
显然：
$$\displaystyle f_x=\sum\limits_{i=x}^n\begin{Bmatrix}i\\x\end{Bmatrix}g_i$$
根据斯特林反演：
$$\displaystyle g_x=\sum\limits_{i=x}^n (-1)^{i-x}\begin{bmatrix}i\\x\end{bmatrix}f_i$$
故$\displaystyle g_1=\sum\limits_{i=1}^n (-1)^{i-1}\begin{bmatrix}i\\1\end{bmatrix}f_i$
而$\begin{bmatrix}i\\1\end{bmatrix}$是阶乘形式：$\begin{bmatrix}i\\1\end{bmatrix}=(i-1)!$
化简答案为：$\displaystyle g_1=\sum\limits_{i=1}^n (-1)^{i-1}(i-1)!f_i$
考虑$f_i$如何求出：状压点所属联通块状态，则我们要选择图集使块与块之间无边，考虑枚举每个图的$S$表示点与点之间的连边(不属同一联通块)，我们压到线性基里去，$ele$表示线性基元素，这些元素是不能选择的(相异)，故答案为$2^{N-ele}$
## Code
```cpp
#include<bits/stdc++.h>
typedef int LL;
const LL maxn=109;
LL N,n;
LL G[maxn][maxn][maxn],a[maxn];
char s[maxn];
long long ans,p[maxn],S,fac[15];
void Dfs(LL x,LL up){
if(x==n+1){
memset(p,0,sizeof(p)); LL ele(0);
for(LL i=1;i<=N;++i){
S=0; LL tot(0);
for(LL j=1;j<=n;++j)
for(LL k=j+1;k<=n;++k)
if(a[k]!=a[j]){
S|=(1ll<<tot)*G[i][j][k];
++tot;
}
for(LL j=0;j<tot;++j){
if(S&(1ll<<j)){
if(!p[j]){
p[j]=S;
++ele;
break;
}else
S^=p[j];
}
}
}
ans+=1ll*((up&1)?1:-1)*fac[up-1]*(1ll<<N-ele);
return;
}
for(LL i=1;i<=up+1;++i){
a[x]=i;
Dfs(x+1,std::max(up,i));
}
}
int main(){
scanf("%d",&N);
for(LL i=1;i<=N;++i){
scanf(" %s",s+1);
LL len(strlen(s+1));
if(!n){
n=1;
for(;n*(n-1)/2!=len;++n);
}
LL now(0);
for(LL j=1;j<=n;++j) for(LL k=j+1;k<=n;++k) G[i][j][k]=s[++now]-'0';
}
fac[0]=fac[1]=1; for(LL i=2;i<=n;++i) fac[i]=fac[i-1]*i;
Dfs(1,0);
printf("%lld",ans);
return 0;
}
```
## 例题三
[CF932E Team Work](https://www.luogu.org/problemnew/show/CF932E)
## 题意
>$\displaystyle \sum\limits_{i=1}^n C_n^ii^k (n≤10^9,k≤5000)$
## 做法
$\displaystyle \sum\limits_{i=1}^n C_n^ii^k$
$\displaystyle =\sum\limits_{i=1}^nC_n^i\sum\limits_{j=0}^iC_i^j\begin{Bmatrix}k\\j\end{Bmatrix}j!$
$=\displaystyle \sum\limits_{i=1}^n \frac{n!}{(n-i)!}\sum\limits_{j=0}^i\frac{\begin{Bmatrix}k\\j\end{Bmatrix}}{(i-j)!}$
$=\displaystyle \sum\limits_{j=0}^{min(n,k)}\begin{Bmatrix}k\\j\end{Bmatrix}\sum\limits_{i=j}^n\frac{n!}{(n-i)!}\frac{1}{(i-j)!}$
$=\displaystyle \displaystyle \sum\limits_{j=0}^{min(n,k)}\begin{Bmatrix}k\\j\end{Bmatrix}\sum\limits_{i=j}^n\frac{n!}{(n-j)!}\frac{(n-j)!}{(n-i)!(i-j)!}$
$=\displaystyle \sum\limits_{j=0}^{min(n,k)}\begin{Bmatrix}k\\j\end{Bmatrix}\frac{n!}{(n-j)!}\sum\limits_{i=j}^nC_{n-j}^{i-j}$
$=\displaystyle \sum\limits_{j=0}^{min(n,k)}\begin{Bmatrix}k\\j\end{Bmatrix}\frac{n!}{(n-j)!}2^{n-j}$
## 更多例题及总结
[点这里](https://www.cnblogs.com/y2823774827y/p/10704018.html)