SkyWT

我们的征途是星辰大海。

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

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



Related posts

Kruskal 算法求最小生成树与次小生成树
发表评论
撰写评论