排列组合n个球放入m个盒子m问题总结（转）

原文链接&＃xff1a;http://blog.csdn.net/qwb492859377/article/details/50654627

求&＃xff0c;盒子都可以分成是否不能区分&＃xff0c;和能区分&＃xff0c;还能分成是否能有空箱子&＃xff0c;所以一共是8种情况&＃xff0c;我们现在来一一讨论。

1.球同&＃xff0c;盒不同&＃xff0c;无空箱

C(n-1,m-1), n>&＃61;m
0, n

使用插板法&＃xff1a;n个球中间有n-1个间隙&＃xff0c;现在要分成m个盒子&＃xff0c;而且不能有空箱子&＃xff0c;所以只要在n-1个间隙选出m-1个间隙即可

2.球同&＃xff0c;盒不同&＃xff0c;允许空箱

C(n&＃43;m-1,m-1)

我们在第1类情况下继续讨论&＃xff0c;我们可以先假设m个盒子里都放好了1个球&＃xff0c;所以说白了就是&＃xff0c;现在有m&＃43;n个相同的球&＃xff0c;要放入m个不同的箱子&＃xff0c;没有空箱。也就是第1种情况

3.球不同&＃xff0c;盒相同&＃xff0c;无空箱

第二类斯特林数dp[n][m]
dp[n][m]&＃61;m*dp[n-1][m]&＃43;dp[n-1][m-1],1<&＃61;m dp[k][k]&＃61;1,k>&＃61;0
dp[k][0]&＃61;0,k>&＃61;1
0,n

这种情况就是第二类斯特林数&＃xff0c;我们来理解一下这个转移方程。

对于第n个球&＃xff0c;如果前面的n-1个球已经放在了m个箱子里&＃xff0c;那么现在第n个球放在哪个箱子都是可以的&＃xff0c;所以m*dp[n-1][m];

如果前n-1个球已经放在了m-1个箱子里&＃xff0c;那么现在第n个球必须要新开一个箱子来存放&＃xff0c;所以dp[n-1][m-1]

其他的都没法转移过来

4.球不同&＃xff0c;盒相同&＃xff0c;允许空箱

sigma dp[n][i],0<&＃61;i<&＃61;m,dp[n][m]为情况3的第二类斯特林数

这种情况就是在第3种情况的前提下&＃xff0c;去枚举使用的箱子的个数

5.球不同&＃xff0c;盒不同&＃xff0c;无空箱

dp[n][m]*fact[m],dp[n][m]为情况3的第二类斯特林数,fact[m]为m的阶乘

因为球是不同的&＃xff0c;所以dp[n][m]得到的盒子相同的情况&＃xff0c;只要再给盒子定义顺序&＃xff0c;就等于现在的答案了

6.球不同&＃xff0c;盒不同&＃xff0c;允许空箱

power(m,n) 表示m的n次方

每个球都有m种选择&＃xff0c;所以就等于m^n

7.球同&＃xff0c;盒同&＃xff0c;允许空箱

dp[n][m]&＃61;dp[n][m-1]&＃43;dp[n-m][m], n>&＃61;m
dp[n][m]&＃61;dp[n][m-1], n 边界dp[k][1]&＃61;1,dp[1][k]&＃61;1,dp[0][k]&＃61;1

现在有n个球&＃xff0c;和m个箱子&＃xff0c;我可以选择在所有箱子里面都放上1个球&＃xff0c;也可以不选择这个操作。

如果选择了这个操作&＃xff0c;那么就从dp[n-m][m]转移过来

如果没有选择这个操作&＃xff0c;那么就从dp[n][m-1]转移过来

8.球同&＃xff0c;盒同&＃xff0c;无空箱

dp[n-m][m],dp同第7种情况,n>&＃61;m
0, n

因为要求无空箱&＃xff0c;我们先在每个箱子里面放1个球&＃xff0c;然后还剩下n-m个球了&＃xff0c;再根据情况7答案就出来了

如果有错误&＃xff0c;希望菊苣指出~

转载请注明出处...