“分球入盒”问题

顾名思义，该问题就是关于如何把多个小球放入多个盒子的问题。该问题共有 8 种变种，分别有 3 个不同点：

• 球之间有没有区别？
• 盒子之间有没有区别？
• 每个盒子是否至少要放 1 个球？

对此，我做了个表格（T 为肯定，F 为否定）：

情况	球之间有没有区别	盒子之间有没有区别	盒子是否至少要放 1 个球
#1	T	T	T
#2	T	T	F
#3	T	F	F
#4	T	F	T
#5	F	F	T
#6	F	T	F
#7	F	T	T
#8	F	F	F

后文的叙述顺序会按难度升序排序。

约定

我们约定：

• 共有 \(n\) 个球，\(m\) 个盒子，并假设 \(n \ge m\) 。
• \(\dbinom{n}{m}=\dfrac{n!}{m!(n-m)!}\)， 表示在 \(n\) 个物品中选择 \(m\) 个的可能数（不同顺序算一个可能）。

情况 #2

很明显对于每个球，我们都要选择一个盒子。于是解即为 \(m^n\)。

情况 #5

（插板法）我们可以在 \(n\) 个球之间插入 \((m-1)\) 个板子，来把这些球分成 \(m\) 份。因为不能有盒子不放，所以空隙数为 \((n-1)\) 。答案即为 \(\dbinom{n-1}{m-1}\)。

情况 #8

我们可以把这种情况转化成情况 #5，只需再加入 \(m\) 个球即可。于是答案为 \(\dbinom{n+m-1}{m-1}\)。

······