默认问题为 n 个小球放到 m 个盒子里：

1. 球相同，盒子不同，不能有空盒
   实质就是把 n 个小球分为 m 组（不能空）。利用插板法，就是在 n 个小球的 n-1 个空隙当中刚好插入 m-1 个板子，即恰好分为不为空的 m 组。

ans=\binom{n-1}{m-1}

2. 球相同，盒子不同，可以有空盒
   对于每个盒子，我们都给他一个球，那么上一个问题就和这问题一样了，所以我们可以看做自己有 n+m 个小球，然后我们在排列完之后在每一组都删去一个小球，这样就能枚举出有空盒的情况了。
   也可以考虑为 n+m-1 个位置分配 n 个板，形成了 m 个空间。
   此问题也等价与 a_1+a_2+\cdots+a_m=n 的方案数。

ans=\binom{n+m-1}{m-1}

3. 球不同，盒子不同，可以有空盒
   对于每一个球，可以放到 [1,m] 的任意一个位置，由于球不同，所以球与球之间是独立的。每个球有 m 种情况：

ans=m^n

4. 球不同，盒子相同，不能有空盒
   等价于第二类斯特林数，将 n 个物体划分为 m 个非空集合。

ans=\begin{Bmatrix}n\cr m\end{Bmatrix}

5. 球不同，盒子也不同，不能有空盒
   这种情况与上面唯一的不同就是有序性，我们只需要在那第二类斯特林数上乘上一个 m! 就可以了。

ans=m!\begin{Bmatrix}n\cr m\end{Bmatrix}

6. 球不同，盒子相同，可以有空盒
   等价于贝尔数，n 个物品划分为任意个集合的方案数。

ans=\sum_{i=1}^{m}\begin{Bmatrix}n\cr i\end{Bmatrix}

7. 球相同，盒子相同，可以有空盒
   等价于自然数拆分问题。可以动态规划解决。

ans=f[n][m]

8. 球相同，盒子相同，不能有空盒
   我们先假设在每一个盒子里都放上了一个球，就跟上面的情况一样了。

ans=f[n-m][m]

例题：

有 N 个相同的球，M 个不同的盒子，每个盒子最多放 K个球 ，请计算将这 N 个球全部放入盒子中的方案数模 1000007 后的结果 ，N\le 5000,M\le 5000。

分析：

考虑容斥定理。假设有 i 个盒子违规，则这 i 个盒子先至少装 k+1 个球；剩下的 n-i(k+1) 个相同球装在 m 个不同的盒子中，可以有空盒。

ans=\sum_{i=0}^{m} (-1)^i\binom{m}{i}\binom{n-i(k+1)+(m-1)}{m-1}