第二类斯特林数


定义

我们将 \(k\) 个互不相同的物品放入 \(n\) 个相同的盒子中且盒子非空的方案数 \(\begin{Bmatrix}k\\n\end{Bmatrix}\) 称做第二类斯特林数

性质

考虑如何求第二类斯特林数。 首先有递推式: \[ \begin{Bmatrix}k\\n\end{Bmatrix}=\begin{Bmatrix}k-1\\n-1\end{Bmatrix}+n\begin{Bmatrix}k-1\\n\end{Bmatrix} \] 组合意义为第 \(k\) 个物品单独一堆,或者和其它的放一起。

按组合意义考虑,有如下式子: \[ n^k=\sum_{i=0}^k\binom{n}{i}\begin{Bmatrix}k\\i\end{Bmatrix}i!=\sum_{i=0}^n\binom{n}{i}\begin{Bmatrix}k\\i\end{Bmatrix}i! \]

左边即将 \(k\) 个不同的物品放入不同的盒子的方案数。 右边盒子也是有标号的,枚举非空盒子数目,然后物品放入盒子,因为盒子有标号所以要乘上阶乘。

发现可以二项式反演,就变成了 \[ \begin{Bmatrix}k\\n\end{Bmatrix}n!=\sum_{i=0}^k(-1)^{i}\binom{n}{i}i^k \]


文章作者: ffacs
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 ffacs !
  目录