小球放入盒子的方案数总结

$n$ 个小球放入 $m$ 个盒子的方案数目，分情况讨论如下（ $S_2$ 表示第二类斯特林数）：

1. 不同的小球，不同的盒子，可以有空盒：

每个小球可以放入任何一个盒子里，所以方案数是 $m^n$

2. 不同的小球，不同的盒子，不能有空盒：

先认为盒子是相同的，放入小球后再进行排列，所以方案数是 $m! \ S_2(n,m)$

3. 不同的小球，相同的盒子，可以有空盒：

非空盒的数量可以是 $1,2,\dots,min\{m,n\}$ ，所以方案数是 $\sum_{k=1}^{min\{m,n\} } S_2(n,k)$

4. 不同的小球，相同的盒子，不能有空盒：

方案数是 $S_2(n,m) = \frac{1}{m!} \sum_{k=0}^{m} (-1)^k \left(\begin{array}{c} m \\ k \end{array}\right) (m-k)^n$

5. 相同的小球，不同的盒子，可以有空盒：

可以认为是从 $m$ 个盒子中挑选 $n$ 个的可重复的组合，所以方案数是 $\left( \begin{array}{c}m+n-1 \\ n \end{array} \right)$

6. 相同的小球，不同的盒子，不能有空盒：

相当于每个盒子都放入一球后再计算 5. 中的问题，所以方案数是 $\left(\begin{array}{c} n-1 \\ m-1 \end{array}\right)$

7. 相同的小球，相同的盒子，可以有空盒：

相当于将整数 $n$ 拆分为最多 $m$ 个数的拆分数，母函数为：

$G(x) = \prod_{k=1}^m (1-x^k)^{-1}$ ，方案数为 $G(x)$ 中 $x^n$ 项的系数

8. 相同的小球，相同的盒子，不能有空盒：

相当于将整数 $n$ 拆分为 $m$ 个数的拆分数，母函数为：

$G(x) = x^m \prod_{k=1}^m (1-x^k)^{-1}$ ，方案数为 $G(x)$ 中 $x^n$ 项的系数