八个放球问题方法总结(基础组合问题)


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

本文采用 BY-NC-SA 3.0 协议进行授权。

欢迎转载,如有错误欢迎指出。

本文链接:https://skywt.cn/posts/put-ball/


我们的征途是星辰大海。