【专题】组合数学之球盒问题

组合数学之球盒问题"/>

【专题】组合数学之球盒问题

球盒问题是组合数学中的经典问题，问题统一一下就是这样：
有 n n n 个(不)同的球，放进 m m m 个(不)同的盒子里，(不)允许有空盒，求方案数。

根据上面的描述可以看出，这个问题总共有 8 8 8 种情况，我们一个一个来看。为了方便起见，我们只考虑有解的情况 。

• 球相同，盒不同，无空盒

  C n − 1 m − 1 C_{n - 1}^{m - 1} Cn−1m−1​

  可以用插板法， n n n 个球中总共有 n − 1 n - 1 n−1 个空隙，根据条件，我们只需要在 n − 1 n - 1 n−1 个空隙中插 m − 1 m-1 m−1 个板子即可。

• 球相同，盒不同，有空盒

  C n + m − 1 m − 1 C_{n + m - 1}^{m - 1} Cn+m−1m−1​

  既然允许有空盒，那么我们可以多加 m m m 个“虚”的球，预先塞进每个盒子。

  这样问题就化归成了有 n + m n + m n+m 个相同的球和 m m m 个不同的盒子，不允许有空盒的情况，直接运用上面的结论就可以解决问题了。

• 球不同，盒相同，无空盒