小球放盒模型 | guanghechen

预备知识
¶

组合数
$(\binom{n}{m}) = C (n, m) = {\begin{aligned} \frac{n!}{m! (n - m)!}, & n ⩾ m \\ 0, & n < m \end{aligned}$
第二类斯特林数
$\begin{aligned} S (n, m) & = m S (n - 1, m) + S (n - 1, m - 1) \\ = \frac{1}{m!} \sum_{k = 0}^{m} (- 1)^{k} (\binom{m}{k}) (m - k)^{n} \\ 其中， n > 1, m ⩾ 1 。 \end{aligned}$

小球放盒模型
¶

有 $n$ 个小球放入 $m$ 个盒子中，求方案数。

000 小球无区别、盒子无区别、不允许空盒
¶

初始时，先给每一个盒子放一个小球。问题转化成将 $n - m$ 个 无区别小球 放入 $m$ 个 无区别盒子 中，且 允许有空盒。

方案数： $G (x) = \frac{x^{m}}{(1 - x) (1 - x^{2}) \dots (1 - x^{m})}$ 的 $x^{n}$ 项系数。

001 小球无区别、盒子无区别、允许有空盒
¶

设某一方案中，有 $i$ 个小球的盒子有 $a_{i}$ 个。

显然， $(\sum_{i = 0}^{n} a_{i}) = m, 0 ⩽ a_{i} ⩽ m$ 。对于每一个方案，我们仅用 $a_{i} \neq 0$ 的项组成的形如 ${(r, a_{r}), (p, a_{p}), \dots, (q, a_{q})}$ 的序偶序列表示足矣。问题等价于用 ${1, 2, \dots, m}$ 拆分 $n$ 的拆分数。利用母函数，容易得到：

\begin{aligned} G (x) & = (1 + x + x^{2} + \dots) (1 + x^{2} + x^{4} + \dots) \dots (1 + x^{m} + x^{2 m} + \dots) \\ = \frac{x^{m}}{(1 - x) (1 - x^{2}) \dots (1 - x^{m})} \end{aligned}

方案数： $G (x) = \frac{x^{m}}{(1 - x) (1 - x^{2}) \dots (1 - x^{m})}$ 的 $x^{n}$ 项系数。

010 小球无区别、盒子有区别、不允许空盒
¶

相当于在 $n$ 个小球中放置 $m - 1$ 块挡板将小球分成不为空的 $m$ 部分。这个问题等价于在 $n - 1$ 个位置中选择 $m - 1$ 个位置。方案数： $C (n - 1, m - 1)$ 。

011 小球无区别、盒子有区别、允许有空盒
¶

由于允许空盒，根据前面的分析，挡板可以相邻。所以问题等价于，在 $n + m - 1$ 个位置中放置 $m - 1$ 块挡板。方案数： $C (n + m - 1, m - 1)$ 。

100 小球有区别、盒子无区别、不允许空盒
¶

设方案数 $f (n, m)$ 。讨论任一小球 $b_{i}$ 的摆放情况，则所有的方案分为两类：

$b_{i}$ 独占一个盒子；相当于其它 $n - 1$ 个不同球需要放入 $m - 1$ 个相同盒子且不允许空盒。方案数： $f (n - 1, m - 1)$ 。
$b_{i}$ 不独占一个盒子; 相当于先把 $n - 1$ 个不同球放入 $m$ 个相同盒子且不允许空盒，再将 $b_{i}$ 放入任一盒子中。

根据组合数的加法原理，总结以上两种情况，可得到递推式：

f (n, m) = m \times f (n - 1, m) + f (n - 1, m - 1)

比较第二类斯特林数，不难发现： $f (n, m) = S (n, m)$ 。

101 小球有区别、盒子无区别、允许有空盒
¶

在 不允许空盒 的基础上枚举空盒个数就好了。方案数： $\sum_{i = 1}^{min (n, m)} S (n, i)$

110 小球有区别、盒子有区别、不允许空盒
¶

因为无空盒，且每个小球必然只能放到一个盒子中，故方案数等于 盒子无区别 时的方案数乘上 $m!$ 。故方案数： $m! \times S (n, m)$ 。

111 小球有区别、盒子有区别、允许有空盒
¶

显然每个球有 $m$ 个选择，且互不影响。方案数： $m^{n}$ 。

小记
¶

$n$ 个球	$m$ 个盒子	是否允许空盒	方案数
无区别	无区别	无空盒	$G (x) = \frac{x^{m}}{(1 - x) (1 - x^{2}) \dots (1 - x^{n})}$ 的 $x^{n}$ 项的系数
无区别	无区别	有空盒	$G (x) = \frac{1}{(1 - x) (1 - x^{2}) \dots (1 - x^{n})}$ 的 $x^{n}$ 项的系数
无区别	有区别	无空盒	$C (n - 1, m - 1)$
无区别	有区别	有空盒	$C (n + m - 1, n)$
有区别	无区别	无空盒	$S (n, m)$
有区别	无区别	有空盒	$\begin{aligned} (1) & S (n, 1) + S (n, 2) + \dots + S (n, m), & n ⩾ m \\ (2) & S (n, 1) + S (n, 2) + \dots + S (n, n), & n ⩽ m \end{aligned}$
有区别	有区别	无空盒	$m! S (n, m)$
有区别	有区别	有空盒	$m^{n}$

参考资料：《组合数学》（第 4 版》 ---by 卢开澄、卢华明

预备知识¶