19. 球盒问题

把 $n$ 个球放到 $m$ 个盒子中，总共有多少种放法？

根据球是否相同、盒是否相同、是否允许空盒，分 8 种情形讨论。

19.1. 球同，盒不同，无空盒

插空法：$n$ 个球中间有 $n-1$ 个间隙，不能有空盒，所以在 $n-1$ 个间隙选出 $m-1$ 个间隙。

$$ \begin{cases} C_{n-1}^{m-1} & & n \geqslant m \\ 0 & & n < m \end{cases} $$

19.2. 球同，盒不同，允许空盒

本问题等价于“把 $n+m$ 个相同的球放到 $m$ 个不同盒子中，且无空盒”，即先在每个盒子中放 1 个球。

因此，放法有：

\[C_{n+m-1}^{m-1}\]

19.3. 球不同，盒同，无空盒

设 $dp[n][m]$ 表示 $n$ 个球放到 $m$ 个盒子中且无空盒的放法。如果前 $n-1$ 个球已经使用了 $m$ 个盒子中，则第 $n$ 个球可以放到任意一个盒子中（与任意一组球结合）；如果前 $n-1$ 个球只使用了 $m-1$ 个盒子中，则第 $n$ 个球只能放到剩下的空盒子中。

\[\begin{split}dp[n][m] &=\ m \times dp[n-1][m] + dp[n-1][m-1],\quad 1 \leqslant m \leqslant n. \\ dp[k][k] &=\ 1,\quad k \geqslant 0. \\ dp[k][0] &=\ 0,\quad k \geqslant 1. \\ dp[0][k] &=\ 1,\quad k \geqslant 0.\end{split}\]

19.4. 球不同，盒同，允许空盒

设 $dp[n][m]$ 表示 $n$ 个球放到 $m$ 个盒子中且无空盒的放法，递推公式如上。

可以枚举空盒的个数，则放法有：

\[\sum_{k=1}^m dp[n][k]\]

19.5. 球不同，盒不同，无空盒

设 $dp[n][m]$ 表示 $n$ 个球放到 $m$ 个盒子中且无空盒的放法，递推公式如上。

需要考虑盒子的排列，则放法有：

\[dp[n][m] \times m!\]

19.6. 球不同，盒不同，允许空盒

每个球都有 $m$ 种选择，放法有：

\[m^n\]

19.7. 球同，盒同，允许空盒

设 $dp[n][m]$ 表示 $n$ 个球至多使用 $m$ 个盒子（即允许空盒）的放法，可以分为两种情况：一，无空盒， $dp[n-m][m]$ ，即每个盒子先放 1 个球；二，至多使用 $m-1$ 个盒子， $dp[n][m-1]$ 。递推公式如下：

\[\begin{split}dp[n][m] &=\ dp[n][m-1] + dp[n-m][m],\quad 1 \leqslant m \leqslant n. \\ dp[n][m] &=\ dp[n][n],\quad m \geqslant n. \\ dp[k][0] &=\ 0,\quad k \geqslant 1. \\ dp[0][k] &=\ 1,\quad k \geqslant 0. \\ dp[1][k] &=\ 1,\quad k \geqslant 1. \\ dp[k][1] &=\ 1,\quad k \geqslant 0.\end{split}\]

19.8. 球同，盒同，无空盒

设 $dp[n][m]$ 表示 $n$ 个球至多使用 $m$ 个盒子（即允许空盒）的放法，递推公式如上。

先在每个盒子先放 1 个球，则无空盒的放法有：

$$ \begin{cases} dp[n-m][m] & & n \geqslant m \\ 0 & & n < m \end{cases} $$

19.9. 参考资料

排列组合 “n个球放入m个盒子m”问题总结

https://blog.csdn.net/qwb492859377/article/details/50654627?tdsourcetag=s_pctim_aiomsg