第二类 Stirling 数 学习笔记

数学

---

定义

将 $n$ 个有区别的球放入 $m$ 个无区别的盒子里, 且无空盒的方案数, 被称为第二类斯特林数, 表示为 $S(n,m)$, 也是将 $n$ 个数拆分成 $m$ 个非空部分的方案数.

递推式

$$S(n,m)=mS(n-1,m) + S(n-1,m-1)$$

证明 :
设最后一个放入的球为 $b_n$, 则可以分为两种情况 :
1. 将 $b_n$ 和 $m$ 组球中的一组放在一起, 方案数为 $mS(n-1,m)$.
2. 将 $b_n$ 放在一个新的盒子里, 方案数为 $S(n-1,m-1)$.
然后加法原理即可.

公式

$$\begin{aligned} S(n,m) &=\frac{1}{m!} \left[ m^n - \binom{m}{1}(m-1)^n + \binom{m}{2}(m-2)^n - \cdots + (-1)^{m-1}\binom{m}{m-1}1^n \right] \\ &=\frac{1}{m!} \sum_{k=0}{m-1} (-1)^k \binom{m}{k} (m-k)^n \end{aligned}$$