斯特林数

第二类斯特林数

定义：将 \(n\) 个不同元素分到 \(k\) 个完全相同的非空盒子里面的方案数为 \(\begin{Bmatrix}n \\ k\end{Bmatrix}\)。

递推式： \(\begin{Bmatrix}n \\ k\end{Bmatrix} = \begin{Bmatrix}n - 1 \\ k - 1\end{Bmatrix} + k \begin{Bmatrix}n - 1 \\ k\end{Bmatrix}\)。

证明：就是考虑新加入的这个球是放到原有的还是新建一个。

边界：\(\begin{Bmatrix}n \\ 0\end{Bmatrix} = [n = 0]\)。

另外一种证明：

我们考虑钦定有多少个盒子是空的，然后剩下的就类似于 \(n\) 个不同元素 \(k\) 个不相同盒子的情况。

先做一个容斥然后除掉盒子排列的方案就可以了，这个最后得到的就是第二类斯特林数的通项公式。

也就是

\[ \begin{Bmatrix}n \\ k\end{Bmatrix} = \dfrac{1}{k!}\sum\limits_{i = 0}^k (-1)^i\dbinom{k}{i}(k - i)^n \]

---

最后更新: September 21, 2023