八个放球问题方法总结（基础组合问题）

文章目录

皮一下，N 个求放入 M 个盒子，总问题数量是 $C_2^1 \ast C_2^1 \ast C_2^1=8$ 个～

八个问题索引：

本页面含有大量 $\KaTeX$ 公式，请确保浏览器支持。
部分题目有很多解法，这里只提供了一种。

可以用 DP 解： $F(i,j)$ 表示把 $i$ 拆分成小于等于 $j$ 个整数的方案数，也就是把 $i$ 个小球分到 $j$ 个盒子里的方案数。考虑状态转移，既然盒子不能是空的，我们就先给每个盒子分配一个球，然后剩余的随意分配。转移方程是：

F(i,j)=F(i-j,j)

这个问题相当于整数拆分。其实和前面一种类似，只是增加了有盒子为空的情况： $F(i,j-1)$ 。转移方程：

F(i,j)=F(i,j-1)+F(i-j,j)

这种情况q其其实就是第二类斯特林数，具体可以去看之前的文章， $F(i,j)$ 表示前 $i$ 个小球分成了 $j$ 个非空集合（放到了 $j$ 个盒子里），转移方程：

F(i,j)=F(i-1,j-1)+j \ast F(i-1,j)

和球不同，盒相同，不能为空的情况类似，只要最后累计一下就可以了，也就是说答案是 $\displaystyle \sum_{i=1}^{m} F(n,i)$ 。

先假设盒子是相同的，就转换成了球不同，盒相同，可以为空的问题。最后把盒子全排列一下即可。最后的答案也就是： $F(n,m)\ast m!$ 。

很显然，每个球都有 $m$ 种选择，答案就是： $n^m$ 。

这种情况可以用隔板法。答案是： $\displaystyle C_{n-1}^{m-1}$ 。

预先把所有盒子里放上一个球，那么后面的做法就等价于前面一个球相同，盒不同，不能为空的情况了。答案就是： $\displaystyle C_{n+m-1}^{n-1}$