经典问题8连:小球和盒子

xiaoxiao2021-02-28  24

 

问题列举:

把n个不同的小球放在m不同的个盒子里,空盒把n个不同的小球放在m不同的个盒子里,空盒把n个不同的小球放在m相同的个盒子里,空盒把n个不同的小球放在m相同的个盒子里,空盒把n个的小球放在m不同的个盒子里,空盒把n个相同的小球放在m不同的个盒子里,空盒把n个相同的小球放在m的个盒子里,空盒把n个相同的小球放在m的个盒子里,空盒

 

方案数量:

把n个不同的小球放在m不同的个盒子里,有空盒:m^n

把n个不同的小球放在m不同的个盒子里,无空盒:S2(n, m)*m!

其中S2表示第二类斯特林数

方案数公式可以用母函数或泰勒展开进行变换:

细心的你发现了其实后面的那个公式正是容斥法求出来的公式

 

把n个不同的小球放在m相同的个盒子里,有空盒:Bell(n)

即第n个贝尔数,其中(里面的S()仍然是第二类斯特林数),并且贝尔数具有递推公式

 

把n个不同的小球放在m相同的个盒子里,无空盒:S2(n, m)

把n个相同的小球放在m不同的个盒子里,有空盒:C(n+m-1, m-1)

很经典的隔板法

把n个相同的小球放在m不同的个盒子里,无空盒:C(n-1, m-1)

仍然是很经典的隔板法,不过是在n-1个空隙中,选择m-1个放上隔板

把n个相同的小球放在m相同的个盒子里,有空盒:dp[n+m][m]= dp[n][m]+ dp[n+m-1][m-1]

把n个相同的小球放在m相同的个盒子里,无空盒:dp[n][m]= dp[n-m][m]+ dp[n-1][m-1]

 

 

转载请注明原文地址: https://www.6miu.com/read-2620694.html

最新回复(0)