小球放盒子公式总结

1、 盒子相同，球相同，不允许空。

这个其实就相当于整数划分问题，就是把球看做数字，把盒子看做每一份。设 f[i][j] 为考虑了前i个，分成了j份，转移方程为:

f[i][j]=f[i−1][j−1]+f[i−j][j]

2、盒子相同，球相同，允许空。

这个东西就是刚刚求的那个整数划分的前缀和。

3、盒子相同，球不同，不允许空。

第二类斯特林数，设f[i][j]表示处理了前i个球 ，用了j个盒子，转移方程为：

f[i][j]=f[i−1][j−1]+f[i−1][j]∗j
　　这个东西的含义就是讨论当前新加入的球要放哪，第一种放法就是再开一个盒子：f[i][j]+=f[i−1][j−1]，第二种方法就是在前面的j个盒子里随便挑一个放进去，因为有j个盒子，所以f[i][j]+=f[i−1][j]∗j。
（f[n][n] = 1, f[1~n][1] = 1）

4、盒子相同，球不同，允许空。

第二类斯特林数的前缀和。其实就是看最后放了几个盒子，剩下的都是空的，加起来即可。

5、盒子不同，球相同，不允许空。

比较经典的隔板法，把m盒子看做m−1个木板，然后要插入到n−1个空隙里，所以答案就是Cm−1n−1。

6、盒子不同，球相同，允许空。

这个就是上一个的变形，可以添加m个小球放到这m个盒子里，这样就保证了盒子非空，答案就是Cm−1n+m−1。

7、盒子不同，球不同，不允许空。

这个是第二类斯特林数∗m!，具体怎么证明不太会，好像就是把斯特林数换一种写法 ，然后消掉有序性。

8、盒子不同，球不同，允许空。

对于每一个小球都可以放到m个盒子里，答案就是mn