球盒问题

1.球相同 盒不同 无空箱 $ans=\left\{ \begin{matrix} C_{n-1}^{m-1} (n>=m) \\ 0(n<m) \end{matrix} \right.$

使用插板法，n个球中总共有n-1个间隙，根据条件，需要在 n−1 个空隙中插 m-1 个板子。

2.球相同 盒不同 允许空箱 $ans=\left\{ \begin{matrix} C_{n+m-1}^{m-1} (n>=m) \\ 0(n<m) \end{matrix} \right.$

允许有空盒，那么可以多加 m 个“虚”的球，预先塞进每个盒子。

这样问题就化归成了有 n+m 个相同的球和 m 个不同的盒子，不允许有空盒的情况，直接运用第1条的结论就可以解决问题了。

3.球不同 盒相同 无空箱

即第二类斯特林数

//1:
dp[n][m]=m*dp[n-1][m]+dp[n-1][m-1] (1<=m<n)
dp[k][k]=1(k>=0)
dp[k][0]=0(k>=1)
//2:
ans=0;(n<m)

对于第 n 个球，如果之前的 n-1 个球已经放在了 m 个盒子里，那么第 n 个球就可以随便放在这 m 个盒子中，因为我没有新开一个盒子，那么答案就是m×dp[n-1,m]。 另外，如果我是新开了一个盒子，那么只有一种可能，答案是dp[n-1][m-1]。

4.球不同 盒相同 允许空箱 $ans=\sum dp[n][i],0<=i<=m,dp[n][m]$

状态转移方程同第三种情况。 其实允许空盒就是可以不用把 m 个盒子全部用完，那么就直接在上一种情况的基础上枚举实际用到的盒子的个数，将答案累加起来就可以了。

5.球不同 盒不同 无空箱

$ans=m!*dp[n][m]$

较第三种情况就多了盒的有序性，dp[n][m]是相同的情况，m!是考虑顺序。

6.球不同 盒不同 允许空箱 $ans=m^n$

每个球都有m种选择，所以就等于$m^n$。

7.球相同 盒相同 无空箱

dp1[n][m]=dp2[n-m][m] (n>=m)  //dp2见问题八
dp1[n][m]=0 (n<m)

dp1[n][m]表示已经放进n个球，有m个空盒子

8.球相同 盒相同 允许空箱

dp2[n][m]=dp2[n][m-1]+dp2[n-m][m] (n>=m)
dp2[n][m]=dp2[n][m-1] (n<m)
边界：dp2[k][1]=1;

dp2[n][m]表示已放进n个球，有 m 个盒子。 考虑小球比盒子多时，可以选择将盘子不放满或者放满分别对应 dp2[n][m−1] 和 dp2[n−m][m]。 但小球比盒子少时，已经不存在放满的情况了，直接dp2[n][m-1] 。