斯特林数学习笔记

斯特林数常用于各类计数问题中。

第一类斯特林数

记为$s(n,k)$，表示把$n$个数分成$k$个圆排列的方案数，有两个递推式：

$$\begin{aligned} s(n,k)&=s(n-1,k-1)+s(n-1,k)(n-1)\\ s(n,k)&=\sum_{i=1}^n \binom{n-1}{i-1}(i-1)!s(n-i,k-1) \end{aligned}$$

第一个递推式的组合意义是枚举最后一个元素的选择；第二个递推式的组合意义是枚举第一个所在排列的状态。

生成函数

设$G_n(x)=\sum_{i}s(n,i)x^i$，那么根据$s(n,k)$的递推式有

$$G_n=xG_{n-1}+(n-1)G_{n-1}=(x+n-1)G_{n-1}$$

因此可以得到

$$G_{n}(x)=\prod_{i=0}^{n-1}(x+i)=x^{\overline{n}}$$

那么我们可以分治多项式乘法求出$G_n$。

第二类斯特林数

记为$S(n,k)$，表示把$n$个数分成$k$个集合的方案数：

$$\begin{aligned} S(n,k)&=\sum_{i=1}^nS(n-i,k-1)\binom{n-1}{i-1}\\ S(n,k)&=S(n-1,k-1)+S(n-1,k)k \end{aligned}$$

相似地，可以从两个角度理解两个递推式。关于$S(n,k)$有一个恒等式：

$$m^n=\sum_{i=0}^mS(n,i)m^{\underline{i}}=\sum_{i=0}^nS(n,i)m^{\underline{i}}$$

组合意义：$n$个不同的物品放到$m$个不同的箱子里：

• 左边：正常数法为$m^n$。
• 中间：枚举有多少个非空盒子，那么我们先把$n$个不同的球分成$i$个非空集合，方案数为$S(n,i)$，然后再枚举这$i$个盒子的位置。
• 右边：和中间等价。

对上式使用二项式反演：

$$F(n)=\sum_{i=0}^nG(i)\binom{n}{i}\iff G(n)=\sum_{i=0}^nF(i)(-1)^{n-i}\binom{n}{i}$$

可以得到：

$$m^n=\sum_{i=0}^nS(n,i)\binom{m}{i}i! \iff S(n,m)=\frac{1}{m!}\sum_{i=0}^m(-1)^{m-i}\binom{m}{i}i^n$$

这个式子也可以用容斥理解。结合$S(n,m)$的组合意义，我们先假设集合有序。然后我们枚举有多少个空的集合，然后我们可以在剩下的集合中随遍填数。最后再除一个$m!$即可。

继续转化可以得到

$$S(n,m)=\sum_{i=0}^m\frac{(-1)^i}{i!}\cdot\frac{(m-i)^n}{(m-i)!}$$

这样可以使用多项式乘法计算$S(n,i),i\in[0,n]$。注意这个恒等式在$n<m$的时候也成立（这时$S(n,m)=0$）。

代码

斯特林反演

首先，根据第一列斯特林数的生成函数有

$$x^{\overline{n}}=\sum_{i=0}^ns(n,i)x^i \tag{1}$$

根据第二类斯特林数的恒等式有

$$x^n=\sum_{i=0}^nS(n,i)x^{\underline{i}} \tag{2}$$

由于$x^{\underline{n}}(-1)^n=(-x)^{\overline{n}}$，那么$(1)$，$(2)$同时代入$-x$并化简可以得到

$$\begin{aligned} x^{\underline{n}}&=\sum_{i=0}^ns(n,i)(-1)^{n-i}x^i & (3)\\ x^{n}&=\sum_{i=0}^nS(n,i)(-1)^{n-i}x^{\overline{i}} & (4) \end{aligned}$$

结合$(2)$，$(3)$可以得到

$$\begin{aligned} x^n &=\sum_{i=0}^nS(n,i)\sum_{m=0}^is(i,m)(-1)^{i-m}x^m\\ &=\sum_{m=0}^n x^m\sum_{i=m}^nS(n,i)s(i,m)(-1)^{i-m} \end{aligned}$$

当然，结合$(1)$，$(4)$同样可以得到

$$\begin{aligned} x^n &=\sum_{m=0}^n x^m\sum_{i=m}^nS(n,i)s(i,m)(-1)^{n-i} \end{aligned}$$

把结合的方式交换一下又是另一个关于上升幂或者下降幂的多项式，也对应了反演公式。综上：

$$\begin{aligned} \sum_{i=m}^nS(n,i)s(i,m)(-1)^{i-m}&=[m=n]\\ \sum_{i=m}^ns(n,i)S(i,m)(-1)^{i-m}&=[m=n] \end{aligned}$$

如何应用斯特林反演？假设固定$m$是常量，我们要求的是$f(m)$。那么等价于求$[m=n]f(n)$。设

$$g(i)=\sum_{n}f(n)S(n,i)$$

那么答案就是$\sum_{i=m}^n g(i)s(i,m)(-1)^{i-m}$。而$g$则需要通过其他的转化或者组合意义来求。

例题

Count the Buildings

求有多少个$n$的排列满足前缀最大值的个数是$F$，后缀最大值的个数是$B$。

$n,F,B\le 2000$。

除掉高度为$n$的那个房子，剩下的我们可以把看得到的房子之间的部分与这些看得到的房子理解为一个圆排列。相当于这个组内的房子可以任意排列，但最高的那个一定要放在左边 / 右边，因此这是一个圆排列。于是容易想到第一类斯特林数。

具体地，我们把$n-1$个房子分成$F+B-2$个圆排列后，相当于要选择$F-1$个放左边。因此总方案数为$\dbinom{F+B-2}{F-1}s(n-1,F+B-2)$。

代码

TJOI2016 求和

求

$$f(n)=\sum_{i=0}^n\sum_{j=0}^iS(i,j)2^jj!$$

$n\le 10^5$。

算法一

直接推。类似求第二类斯特林数的的公式，使用二项式反演展开，并整理成卷积的形式：

$$\begin{aligned} &\sum_{i=0}^n\sum_{j=0}^iS(i,j)2^jj!\\ =&\sum_{i=0}^n\sum_{j=0}^nS(i,j)2^jj!\\ =&\sum_{i=0}^n\sum_{j=0}^n\frac{1}{j!}\sum_{k=0}^j\binom{j}{k}(-1)^k(j-k)^i2^jj!\\ =&\sum_{j=0}^n2^j\sum_{k=0}^j\binom{j}{k}(-1)^k\sum_{i=0}^n(j-k)^i\\ =&\sum_{j=0}^n2^jj!\sum_{k=0}^j\frac{(-1)^k}{k!}\cdot \frac{(j-k)^{n+1}-1}{(j-k)!(j-k-1)}\\ \end{aligned}$$

这样可以直接 FFT 了，复杂度$O(n\log_2n)$。

算法二

这个式子长得很奇怪。设

$$g(i)=\sum_{j=0}^iS(i,j)2^jj!$$

考虑其组合意义，相当于把$i$个元素分成若干个集合，集合之间有序，并且每个集合有两种状态，问总方案数。考虑递推，枚举最后一个集合的状态，可以得到

$$g(i)=\sum_{j=1}^i2\binom{i}{j}g(i-j)$$

稍作变换可以得到

$$\frac{g(i)}{i!}=\sum_{j=0}^{i-1}\frac{2}{(i-j)!}\frac{g(j)}{j!}$$

这样就可以分治 FFT 了。时间复杂度$O(n\log_2^2n)$。

代码

算法三

by Entropy Increaser (origin)

仍然是推式子：

$$\begin{aligned} &\sum_{i=0}^n\sum_{j=0}^iS(i,j)2^jj!\\ =&\sum_{i=0}^n\sum_{j=0}^nS(i,j)2^jj!\\ =&\sum_{i=0}^n\sum_{j=0}^n2^j\sum_{k=0}^j(-1)^{j-k}\binom{j}{k}k^i\\ =&\sum_{j=0}^n2^j\sum_{k=0}^j(-1)^{j-k}\binom{j}{k}\sum_{i=0}^nk^i\\ =&\sum_{k=0}^n\frac{1-k^{n+1}}{1-k}\sum_{j=k}^n\binom{j}{k}(-1)^{j-k}2^j \end{aligned}$$

在算法一中，我们直接使用卷积完成了本题。但注意到，这是一个特殊的卷积。

对于生成函数$G(x)=\sum_{i\ge 0}g_i$，考虑

$$\begin{aligned} G(x+q)&=\sum_{i\ge 0}g_i\sum_{j\ge 0}\binom{i}{j}x^{j}q^{i-j}\\ &=\sum_{j\ge 0}x^j\sum_{i\ge j}\binom{i}{j}g_iq^{i-j} \end{aligned}$$

因此$[x^j]G(x+q)=\sum_{i\ge j}\binom{i}{j}g_iq^{i-j}$。

不妨设$F(x)=\sum_{i=0}^n 2^ix^i=\frac{1-(2x)^{n+1}}{1-2x}$。那么原式就变成了

$$\sum_{k=0}^n\frac{1-k^{n+1}}{1-k}[x^k]F(x-1)$$

那么只要我们能快速求出$\frac{1-k^{n+1}}{1-k}$和$F(x-1)$的各项系数即可。前者可以线性筛，后者可以递推（除以一个一次式）。因此时间复杂度就是$O(n)$的。

Crash 的文明世界

给一棵$n$个结点边权为$1$的树，对于每个$i$求出

$$\sum_{j=1}^n \text{dist}(i,j)^m$$

$n\le 5\times 10^4,m\le 500$。

考虑到$x^m=\sum_{i=0}^mx^{\underline{i}}S(n,i)$。因此我们考虑维护每个子树$u$到$u$距离$m$次方和用下降幂展开后的$S(n,i)$的系数，记为$f(u,i)$。则对于根结点$root$，答案为$\sum_{i=0}^mf(root,i)S(n,i)$。因此在此基础上换根即可求出答案。

考虑如何计算$f(u,i)$。考虑到

$$(x+1)^{\underline{i}}=x^{\underline{i}}+ix^{\underline{i-1}}$$

则对于若干条路径$a_1,a_2,\cdots,a_k$，对$f(u,i)$的贡献为

$$\sum_{i=1}^ka_i^{\underline{i}}$$

如果我们将他们都加 1，则贡献变成

$$\sum_{i=1}^k(a_i+1)^{\underline{i}}=\sum_{i=1}^ka_i^{\underline{i}}+i\sum_{i=1}^ka_i^{\underline{i-1}}$$

而我们如果添加一条长度为 1 的路径，即把$a=1$加入到序列中，则将会对$f(u,0)$和$f(u,1)$都产生$1$的贡献。$f(u,0)$可以理解为是路径数。因此我们得到了$f(u,i)$的转移式：

$$f(u,i)\gets\sum_{v\in Son(u)}f(v,i)+i\cdot f(v,i-1)\\ f(u,1)\gets|Son(u)|\\ f(u,0)\gets|Son(u)|$$

注意处理上边界的转移，对于子树中最长的链，要把长度的阶乘贡献到对应的 DP 值上。

然后再换根即可。

时间复杂度$O(nm)$。

代码

Partitions

给你一个长度为$n$的序列$w$，对于一个下标集合$S$，定义它的价值$W(S)=|S|\sum_{i\in S}w_i$。

对于一个将$[1,\cdots,n]$划分到$k$个集合的方案，记这$k$个集合的集合是$R$。那么这种划分的价值定义为$P(R)=\sum_{S\in R}W(S)$。

现在求$[1,\cdots,n]$的所有划分方案的价值和。

$k\le n\le 2\times 10^5, w_i\le 10^9$。

可以直接写出一个暴力式子：

$$\sum_{i=1}^nw_i\sum_{j=1}^n\binom{n-1}{j-1}S(n-j,k-1)j$$

两边可以分别计算。看到组合数和斯特林数的乘积，考虑将它转化为斯特林数递推式的形式：

$$\begin{aligned} &\sum_{j=1}^n\binom{n-1}{j-1}S(n-j,k-1)j\\ =&\sum_{j=1}^n\binom{n-1}{j-1}S(n-j,k-1)+\sum_{j=1}^n\binom{n-1}{j-1}S(n-j,k-1)(j-1)\\ =&\sum_{j=1}^n\binom{n-1}{j-1}S(n-j,k-1)+(n-1)\sum_{j=1}^n\binom{n-2}{j-2}S(n-j,k-1)\\ =&S(n,k)+(n-1)S(n-1,k) \end{aligned}$$

这样只需要算两个斯特林数即可。时间复杂度$O(n\log_2n)$。

代码

图的价值

一个带标号的图的价值定义为每个点度数的$k$次方的和。

给定$n$和$k$，请计算所有$n$个点的带标号的简单无向图（不一定连通）的价值之和。

$n\le 10^9,k\le 2\times 10^5$。

对每个点的贡献分别计算：

$$\begin{aligned} Ans=&n\sum_{i=0}^{n-1}\binom{n-1}{i}2^{\binom{n-1}{2}}i^k\\ =&n2^{\binom{n-1}{2}}\sum_{i=0}^{n-1}\binom{n-1}{i}i^k \end{aligned}$$

这里我们考虑一个经典的套路：通常幂转下降幂（第二类斯特林数）：（把$n$减了$1$）

$$\begin{aligned} &\sum_{i=0}^n\binom{n}{i}i^k\\ =&\sum_{i=0}^n\binom{n}{i}\sum_{j=0}^k\binom{i}{j}j!S(k,j)\\ =&\sum_{i=0}^n\sum_{j=0}^k\frac{n!}{(n-i)!(i-j)!}S(k,j)\\ =&\sum_{i=0}^n\sum_{j=0}^k\binom{n-j}{i-j} n^{\underline{j}}S(k,j)\\ =&\sum_{j=0}^kn^{\underline{j}}S(k,j)\sum_{i=j}^n\binom{n-j}{i-j} \\ =&\sum_{j=0}^kn^{\underline{j}}S(k,j)2^{n-j} \end{aligned}$$

我们$O(n\log_2n)$计算出$S(k,j),j\in[0,k]$即可。复杂度$O(n\log_2n)$。

代码

经典问题

求$n$个点$m$条边带标号无向连通图的个数。

$n\le 200$。

我们对连通块数做斯特林反演。设$F(i)$表示$n$个点$m$条边$i$个连通块的方案数。那么答案就是$F(1)$。

应用斯特林反演，设$g(j)=\sum_{i=1}^n F(i)S(i,j)$。

答案是$\sum_{j}g(j)s(j,1)(-1)^{j-1}=\sum_{j}g(j)(j-1)!(-1)^{j-1}$。

考虑$g(j)$的组合意义：枚举$i$，对于$n$个点$m$条边$i$个连通块的方案，再把$i$个连通块划分到$j$个非空集合中。

这个组合意义等价于：枚举$n$个点划分成$j$个集合的方案，每个方案只能集合内连边，一共连$m$条边的方案数之和。

又可以转化为：枚举$n$个点划分成$j$个集合的方案，每个方案总共有$t$条可用边，那么这个方案的贡献是$\binom{t}{m}$。

考虑 DP。设$f_{i,j,k}$表示$i$个点有$j$条可用边，划分成$k$个集合的方案数。转移时枚举$1$号点所在集合：

$$f_{i,j,k}=\sum_{z=1}^i\binom{i-1}{z-1}f_{i-z,j-\binom{z}{2},k-1 }$$

那么$g(j)=\sum_{t} f_{n,t,j}\binom{t}{m}$。这是个 4D/1D 的 DP，复杂度$O(n^5)$。

考虑优化。

答案是$\sum_{j}g(j)(j-1)!(-1)^{j-1}=\sum_t\binom{t}{m}\sum_jf_{n,t,j}(j-1)!(-1)^{j-1}$。

设$f'_{i,j,k}=f_{i,j,k}(-1)^{k-1}$，则答案是$\sum_t \binom{t}{m}\sum_j f'_{n,t,j}(j-1)!$。

考虑求$g_{n,t}=\sum_j f'_{n,t,j}(j-1)!$。

如果系数是$j!$那么可以在转移的时候枚举任意集合，这样划分成$j$个集合就被算了$j!$次：

$$g_{n,t}=\sum_i \binom{n}{i}g_{n-i,t-\binom{i}{2}}$$

如果系数是$1$，就枚举$1$号点所在子集：

$$g_{n,t}=\sum_i \binom{n-1}{i-1}g_{n-i,t-\binom{i}{2}}$$

因此为了让系数是$(j-1)!$，我们可以在求$g_{i,t}$（$i<n$）的时候使用第一种转移，在求$g_{n,t}$的时候使用第二种转移。这样就确保每个划分为$j$个集合的方案，$1$号点所在集合的位置是固定的，其他集合可以任意排列，也就是$(j-1)!$种方案。注意，这个方法不能做$(j-k)!$。

异或图

定义两个结点数相同的图$G$与图$H$的异或为一个新的图$I$， 其中如果$(u, v)$在$G$与$H$中的出现次数之和为$1$，那么边$(u, v)$在$I$中，否则这条边不在$I$中。

现在给定$s$个结点数相同的图$G_1,\cdots,G_s$，设$S = {G_1, G_2,\cdots, G_s}$，请问$S$有多少个子集的异或为一个连通图？

$n\le 10,s\le 60$。

考虑容斥连通块的个数。

设$f(i)$表示在所有连通块个数大于等于$i$的方案（即异或出来的图）中，将连通块划分为$i$个集合的方案数。定义比较奇怪，但考虑如何计算。

对于点集，考虑枚举所有的集合划分方案（方案数与贝尔数同阶），同一个集合内的点任意连通，而不同集合的点强制不连通。问满足这个条件的异或图的个数。

考虑线性基，我们只考虑跨过集合的边对应的位，把图插入到线性基中，问题转化为求异或和为 0 的方案数，显然为$2^{S-tot}$，其中$tot$表示线性基的大小。因为线性基外的图任意异或，都可以用线性基里的图唯一地异或出一个反图，使得异或和为 0。

于是我们枚举所有的集合划分方案，$O(Sn^2)$计算贡献，贡献到对应的$f$上。这样就计算出了$f$。我们现在要求的是$g(i)$，表示连通块个数恰好为$i$的方案数（等价于在所有连通块个数等于$i$的方案中，将连通块划分为$i$个集合的方案数）。考虑到

$$f(i)=\sum_{x=i}^nS(x,i)g(x)$$

根据斯特林反演得到

$$g(i)=\sum_{x=i}^ns(x,i)(-1)^{x-i}f(x)$$

则得到

$$g(1)=\sum_{x=1}^n(x-1)!(-1)^{x-1}f(x)$$

于是我们在实现的时候不需要斯特林反演，直接做即可。

时间复杂度$O(B_nSn^2)$。

代码