摘自 http://azaleasays.com/2011/12/16/combinatorics-n-balls-in-m-boxes/
N球放M盒，其实有8种情况：
- 球同，盒同，盒不可以为空
- 球同，盒同，盒可以为空
- 球同，盒不同，盒不可以为空
- 球同，盒不同，盒可以为空
- 球不同，盒同，盒不可以为空
- 球不同，盒同，盒可以为空
- 球不同，盒不同，盒不可以为空
- 球不同，盒不同，盒可以为空
球同、盒同，球可以/不可以为空
枚举法。
例如 7 个相同球放入 4 个相同盒子，每盒至少一个，则先 4 个盒子每个放 1 个，多余 3 个。只需要考虑这3个球的去处就OK，由于盒子相同，所以只需要凑数就OK，不必考虑位置，因此只有300，211，111三种。
例如 7 个相同球放入 4 个相同盒子，可以空盒，则还是凑数，大的化小的，小的化更小的。
0007 0016 0025 0034 0115 0124 0133 0223 1114 1123 1222
11种。
代码实现上，可以用二维 DP。
球同，盒不同，盒可以/不可以为空
用插板法（隔板法）解决。
球同，盒不同，盒不可以为空 的公式是把 $N$ 个球排成一排（一种方法），它们中间有 $N-1$ 个空。取 $M-1$ 个板，放到空上，就把它们分成 $M$ 部分，由于板不相邻，所以没有空盒。它的方法数有 $C_{N-1}^{M-1}$
如果盒可以空（即 球同，盒不同，盒可以为空），为了避免空盒，先在每一个盒里假装放一个球，这样就有 $N+M$ 个球，$C_{N+M-1}^{M-1}$
球不同的情况
球不同的情况里，先来分析最特殊的：球不同，盒不同，盒可以为空。每个球都有 $M$ 种选择， $N$ 个球就有 $M^N$ 种分法。
关于剩下情况，“我先教大家一个非常特殊的三角形，这个你在 Google 百度非常难以找的到的，秘传型，一般人我不会告诉他的。”
看起来很复杂，其实很简单：
斯特林数
性质1，左右两边都是1，第几行就有几个数，比如第5行就是1XXX1
性质2，$S(N, K) = S(N-1, K-1) + K * S(N-1, K)$，含义是第N排的第K个数等于他上一排的上一个位置数字加上一排的同样位置数字的K倍。
例如 $S(7, 3)$ 就是第 7 排第 3 个数字，所以他等于上排第 6 排第 2 个数字+第 6 排第 3 个位置 3。
画图的话，明显第 1 排是 1，第 2 排 1, 1。
推理第 3 排（左右两边都是 1 ，只有中间那个数字没确定）。所以 $S(3, 2) = 第2排第1个数字+第2排第2个数字两倍 = 1+12 = 3$，所以第3排数字就是 1, 3, 1。
同理 $S(4, 2) = S(3, 1) + 2S(3, 2) = 1+23 = 7$, 以此类推。
球不同，盒同，盒不可以为空
$N$ 不同球，$M$ 同盒，无空盒。一共有 $S(N, M)$ 种分法，比如 7 个不同球， 4 个相同盒子，每个盒子至少一个，则看三角形的第 7 行，第 4 个数字多少。
球不同，盒同，盒可以为空
$N$ 不同球，$M$ 同盒，允许空的时候（在上一种情况的基础上允许空盒）。明显是 $N$ 个球不变，一个空盒子都没有 + 有一个空盒子 + 有两个空盒子 + 有三个空盒子 + … + 有 $M-1$ 个空盒。说的简单点一共有就是
$$S(N, 1) + S(N, 2) + S(N, 3) + … + S(N, M)$$
也就是说第 $N$ 排开始第 1 个数字一直加到第 $M$ 个数字就是总的分法。
球不同，盒不同，盒不可以为空
而 球不同，盒不同，盒不可以为空 的情况同样是在 球不同，盒同，盒不可以为空 的基础上升华，因为后者是盒同的，而前者不同，所以盒子自身多了 $M!$ 倍可能， 所以 球不同，盒不同，盒不可以为空 的公式就是 $M! * S(N, M)$
总结 $N$ 球 $M$ 盒结论
- 球同，盒同，盒不可以为空—穷举
- 球同，盒同，盒可以为空—穷举
- 球同，盒不同，盒不可以为空—$C(N-1, M-1)$
- 球同，盒不同，盒可以为空—$C(N+M-1, M-1)$
- 球不同，盒同，盒不可以为空—$S(N, M)$
- 球不同，盒同，盒可以为空—$S(N, 1) + S(N, 2) + S(N, 3) + … + S(N, M)$
- 球不同，盒不同，盒不可以为空—$M! * S(N, M)$
- 球不同，盒不同，盒可以为空—M^N$
