定义

第二类斯特林数记作 $\begin{Bmatrix}n\\ k\end{Bmatrix}$ 或者 $S(n,k)$，其意义是将 $n$ 个互不相同的元素划分为 $k$ 个相同的非空集合的方案数。

朴素求解

$\begin{Bmatrix}n\\ k\end{Bmatrix} =\begin{Bmatrix}n-1\\ k-1\end{Bmatrix}+k\times\begin{Bmatrix}n-1\\ k\end{Bmatrix}$

如果前 $n-1$ 个元素只使用了 $[1,k)$ 的盒子，那么第 $n$ 个一定要放到第 $k$ 个盒子里。

如果前 $n-1$ 个元素用完了 $[1,k]$ 的盒子，那么第 $n$ 个元素就可以随便放。

显然将两种方案加起来就是最终的方案。

容易理解上式的边界条件为 $\begin{Bmatrix}0\\ 0\end{Bmatrix}=1$。

通项公式

设 $G_i$ 表示将 $n$ 个不同元素放入 $i$ 个不同盒子允许为空的方案数，$F_i$ 表示将 $n$ 个不同的元素放入 $i$ 个不同盒子不允许为空的方式。

那么显然：

$G_i=i^n$

同时还有：

$G_i=\sum\limits_{j=0}^i {i\choose j} F_j$

发现上面的式子和二项式反演一样，所以得到：

$F_i=\sum\limits_{j=0}^i (-1)^{i-j}\times {i\choose j}\times G_i$

将 $G$ 带入并化简得到：

$F_i=\sum\limits_{j=0}^i\dfrac{(-1)^{i-j}\times i!\times i^n}{j!\times (i-j)!}$

因为斯特林数的盒子不一样，所以 $F_k$ 就是就是 $\begin{Bmatrix}n\\ k\end{Bmatrix}$ 的 $k!$ 倍，所以得到：

$\begin{Bmatrix}n\\ k\end{Bmatrix}=\dfrac{F_k}{k!}=\sum\limits_{i=0}^k\dfrac{(-1)^{k-i}\times i^n}{i!\times (k-i)!}$

因为 $f(x)=x^n$ 是积性函数，所以可以 $O(n)$ 预处理，$O(1)$ 求解。

应用

当题目里出现 $i^n$ 是可以用第二类斯特林数展开。

得到：

$i^n=\sum\limits_{j=0}^n j!\times {i\choose j}\times \begin{Bmatrix} n\\j\end{Bmatrix}$

把组合数展开然后约分得到：

$i^n=\sum\limits_{j=0}^n \dfrac{i!}{(i-j)!}\times \begin{Bmatrix} n\\j\end{Bmatrix}$