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

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

2018 年 7 月 30 日 07:27


文章目录

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

八个问题索引:

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

球相同,盒相同,不能为空

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

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

球相同,盒相同,可以为空

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

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

球不同,盒相同,不能为空

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

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

球不同,盒相同,可以为空

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

球不同,盒不同,不能为空

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

球不同,盒不同,可以为空

很显然,每个球都有 mm 种选择,答案就是:nmn^m

球相同,盒不同,不能为空

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

球相同,盒不同,可以为空

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


暂无评论


发表新的评论

所有评论都将经过博主审核。请勿填写无意义邮箱或发表无关评论、广告等,否则会被视为垃圾评论。

提交评论即表明你同意本网站使用 Cookie,并允许本站在后台记录你的邮箱、IP 地址等必要信息。这些信息不会被透露给其他用户。(提交一次评论后,本提示将不再展示)