组合数学之球盒问题"/>
【专题】组合数学之球盒问题
球盒问题是组合数学中的经典问题,问题统一一下就是这样:
有 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 个不同的盒子,不允许有空盒的情况,直接运用上面的结论就可以解决问题了。
-
球不同,盒相同,无空盒
更多推荐
【专题】组合数学之球盒问题
发布评论