皮一下,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}$