斯特林数
阿丑
·
·
个人记录
第二类斯特林数
$$
{m\brace n}={m-1\brace n-1}+n\times{m-1\brace n}
$$
考虑组合意义，有：
$$
n^m=\sum_{i=0}^nn^{\underline i}{m\brace i}
$$
即
$$
n^m=\sum_{i=0}^n\binom nii!{m\brace i}
$$
主要在指数较小时使用。
二项式反演，有：
$$
{m\brace n}=\sum_{i=0}^n\frac{(-1)^{n-i}\binom nii^m}{n!}
$$
该式在 $n>m$ 时值为 $0$。不会证。
可以将二项式反演的这个式子略作变形成卷积形式：
$$
{m\brace n}=\sum_{i=0}^n\frac{(-1)^{n-i}}{(n-i)!}\frac{i^m}{i!}
$$
就可以 $\mathcal O(n\log n)$ 地求出一行第二类斯特林数。
### 第一类斯特林数
${m\brack n}$ 为第一类斯特林数，为将 $m$ 个可区分的元素放入 $n$ 个不可区分的环上的方案数。满足递推式：
$$
{m\brack n}={m-1\brack n-1}+(m-1)\times{m-1\brack n}
$$
归纳可证，
$$
x^{\underline n}=\sum_{i=0}^n{n\brack i}(-1)^{n-i}x^i\\
x^{\overline n}=\sum_{i=0}^n{n\brack i}x^i
$$
至于哪个要乘 $-1$ 的幂，可以通过下降幂、上升幂、普通幂的大小关系判断。
### 例题
##### 1.[P4091 求和](/problem/P4091)
- 给定 $n$，求 $\sum_{i=0}^n\sum_{j=0}^i{i\brace j}2^jj!$。
- $n\le10^5$。
$$
{i\brace j}=\sum_{k=0}^j\frac{(-1)^{j-k}\binom jkk^i}{j!}
$$
故：
$$
\begin{aligned}
&\sum_{i=0}^n\sum_{j=0}^i{i\brace j}2^jj!\\
=&\sum_{i=0}^n\sum_{j=0}^n{i\brace j}2^jj!\\
=&\sum_{i=0}^n\sum_{j=0}^n\sum_{k=0}^j\frac{(-1)^{j-k}\binom jkk^i}{j!}2^jj!\\
=&\sum_{j=0}^n2^jj!\sum_{k=0}^j\frac{(-1)^{j-k}}{(j-k)!}\times\frac{\sum_{i=0}^nk^i}{k!}
\end{aligned}
$$
卷积即可。据说有线性做法，不管。
##### 2.[AT4119 Everything on It](/problem/AT4119)
- 对于集合 $\{1,2,\dots,n\}$，求它的子集族中，满足 $1\sim n$ 都在其中出现了至少两次的集合数。
- $n\le3\times10^3$。
少于两次比多于两次好求，考虑容斥。相当于求没有一个数出现少于两次的方案数。
钦定某 $i$ 个数出现少于两次的方案数
$$
f(i)=2^{2^{n-i}}\sum_{j=0}^ig(i,j)2^{(n-i)j}
$$
$g(i,j)$ 表示把 $i$ 个数用 $j$ 个集合包含，每个数出现次数少于两次的方案数。即
$$
g(i,j)=\sum_{k=0}^i\binom ik{k\brace j}\quad(i\ge j)
$$
考虑第 $i$ 个元素是否包含在集合中、包含在哪个集合中。有
$$
g(i,j)=g(i-1,j-1)+(j+1)g(i-1,j)
$$
$g$ 可计算了。那 $f$ 也可计算了。
$$
ans=\sum_{i=0}^n(-1)^i\binom nif(i)
$$