本文讨论的内容为：在不同的限制条件下，将 \(n\) 个球放到 \(m\) 个盒子中（\(n \ge m\)），有多少种放置方案。
文中出现的符号含义如下表所示。
| 符号 | 含义 |
|---|---|
| \(P(n, m)\) | 正整数 n 拆分成最大不超过 m 的正整数的 无序拆分 方案数。 |
| \(B(n, m)\) | 正整数 n 拆分成 m 个正整数的无序拆分方案数。 |
| \(S(n, m)\) | 大小为 n 的集合划分为 m 个（覆盖所有元素而又互不相交）部分的方案数，即第二类 Stirling 数。 |
| \((a_1, a_2, \cdots , a_m)\) | 表示一个放置方案：m 个盒子中分别放置 \(a_1, a_2, \cdots , a_m\) 个球。 |
我们先来讨论不允许盒子空的情况。
不区分球的情况下，我们可以根据每个盒子中球的数量来计算放置方案数。对于两种放置方式，如果同一个盒子里的球的数量不同，这两种放置方式就被视为不同的方案。 如（1, 2, 3）与（3, 2, 1）便是两种不同的放置方案。
为什么首先讨论“球相同 盒子不同”这种情况呢？因为大家应该对这种情况最不陌生， 中学学过的一种叫做“隔板法”的计数方法，正适用于计算这种条件下的放置方案数。实际上，这是一个整数有序拆分问题。 将正整数 \(n\) 有序拆分成 \(m\) 个正整数的方案数为： \(C_{n - 1}^{m - 1}\)。
如果不区分每个球、每个盒子的话，那我们只能用盒子中球数量的分布情况来区别不同的方案。 与上一种情况不同的是，在这种情况下，（1, 2 ,3）与（3, 2, 1）被视为相同的放置方案。
可以想到，这种情况实际上是一个整数无序拆分问题。 正整数 \(n\) 无序拆分成 \(m\) 个正整数的方案数为： \(B(n, m) = P(n, m) - P(n, m - 1)\)。该结论可使用 Ferrers 图证明。
\(P(n, m)\) 的求法这里不再展开叙述。整数的无序拆分是一个很庞大的话题，我会另外写一篇文章来介绍它。
这种情况下，不同的球可以抽象成同一个集合中的不同元素。则放置方案数就是将该集合划分成 \(m\) 份的方案数。 这就是经典的集合划分问题。将含有 \(n\) 个元素的集合划分为 \(m\) 个部分的方案数为：\(S(n, m)\)，也被称为第二类 Stirling 数。 感兴趣的读者可以自行搜索求解 \(S(n, m)\) 的具体方法，在此不再赘述。
这种情况实际上就是上一种情况的全排列。因此放置方案数为：\(S(n, m) \cdot A_m^m\) = \(S(n, m) \cdot m!\)
允许盒子空的话，上面各种情况中的问题模型可能会发生变化。
该问题经过变形，可以等价转化为相应的不允许盒子空问题，具体转化方法见这里。 转化后，可以计算出放置方案数为：\(C_{n + m - 1}^{m - 1}\)。
该情况下，可以枚举多少个盒子不是空的。有 \(i\) 个盒子非空的放置方案数为 \(B(n, i)\)。 则所有的放置方案数为： \(\sum_{i = 1}^m B(n, i) = P(n, m)\)。该结论可用 Ferrers 图证明。
该情况与上一种情况类似，可以枚举非空盒子的数目。\(i\) 个非空盒子的放置方案数为 \(S(n, i)\)。 所有的放置方案数为：\(\sum_{i = 1}^m S(n, i)\)。另外， \(n = m\) 时放置方案数被称为 Bell 数。
因为每个球都会被放到一个盒子中，也就是说每一个球都有一个盒子与之对应。因此放置方案数为：\(m^n\)。 这是一个非常简洁优美的答案。
下面使用表格列出了以上各种情况的放置方案数，供读者总结对比。
| 盒子相同 | 盒子不同 | |
|---|---|---|
| 球相同 | $$B(n, m) = P(n, m) - P(n, m - 1)$$ | $$C_{n - 1}^{m - 1}$$ |
| 球不同 | $$S(n, m)$$ | $$S(n, m) \cdot A_{m}^{m}$$ |
| 盒子相同 | 盒子不同 | |
|---|---|---|
| 球相同 | $$\sum_{i = 1}^{m}B(n, i) = P(n, m)$$ | $$C_{n + m - 1}^{m - 1}$$ |
| 球不同 | $$\sum_{i = 1}^{m}S(n, i)$$ | $$m^n$$ |
16 May 2017