第二类斯特林数

定义

第二类斯特林数$\begin{Bmatrix}n\\k\end{Bmatrix}$表示将 $n$ 个两两不同的元素划分为 $k$ 个互不区分的非空子集的方案数。

递推式

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

类似于组合数的递推式，我们考虑加入一个新元素后子集个数达到 $k$ 的时候，它的方案数就等于这个元素自己分到一个新子集的方案数，即 $\begin{Bmatrix}n-1\\k-1\end{Bmatrix}$ ，加上把它分到之前已有的集合中的方案数，即 $k*\begin{Bmatrix}n-1\\k\end{Bmatrix}$ 。

通项公式

$\begin{Bmatrix}n\\k\end{Bmatrix}=\sum_{i=0}^{k}\cfrac{(-1)^{k-i}i^n}{i!(k-i)!}$

证明：设 $G_j$ 表示将 $n$ 个两两不同的元素划分为 $j$ 个相互区分的子集**（可以为空）的方案数，$F_j$ 表示将 $n$ 个两两不同的元素划分为 $k$ 个相互区分的非空子集**的方案数，所以有：

$G_j=i^j$

$G_j=\sum_{i=0}^{j}{j\choose i}F_i$

根据二项式反演可得：

$F_j=\sum_{i=0}^{j}(-1)^{j-i}{j\choose i}G_i$

$=\sum_{i=0}^{j}(-1)^{j-i}{j\choose i}i^n$

$=\sum_{i=0}^{j}\cfrac{j!(-1)^{j-i}i^n}{i!(j-i)!}$

考虑 $F_j$ 因为和斯特林数的区别只有 $F_j$ 区分子集，所以 $F_j$ 正好为斯特林数的 $j!$倍，即

$\begin{Bmatrix}n\\k\end{Bmatrix}=\cfrac{F_k}{k!}=\sum_{i=0}^{k}\cfrac{(-1)^{k-i}i^n}{i!(k-i)!}$