问题：$n$个球，放到$m$个盒子里$(n≥m)$，主要有下列八种情况：
| $n$个球是否有区别 | $m$个盒子是否有区别 | 是否允许空盒 | |
|---|---|---|---|
| 1 | $F$ | $F$ | $F$ |
| 2 | $F$ | $F$ | $T$ |
| 3 | $F$ | $T$ | $F$ |
| 4 | $F$ | $T$ | $T$ |
| 5 | $T$ | $F$ | $F$ |
| 6 | $T$ | $F$ | $T$ |
| 7 | $T$ | $T$ | $F$ |
| 8 | $T$ | $T$ | $T$ |
球相同，盒子相同，不允许空盒
要保证盒子大小非严格递减。每次把当前所有盒子里的球都$+1$；或者新增一个盒子，里面放一个球。
$$
f[n][m] = f[n-1][m-1]+f[n-m][m]
$$
另外，也可以从允许空盒的方案 $g$ 推出:
$$
f[n][m]=g[n-m][m]
$$
球相同，盒子相同，允许空盒
要保证盒子大小非严格递减。每次把当前所有盒子里的球都$+1$；或者新增一个盒子，里面不放球。
$$
g[n][m] = g[n][m-1]+g[n-m][m]
$$
另外，也可以从允许无空盒的方案 $g$ 推出:
$$
g[n][m] = \sum_{i=1}^{m}f[n][i]
$$
球相同，盒子不同，不允许空盒
插板法，总共$n-1$个间隔，插$m-1$个板子
$$
C_{n-1}^{m-1}
$$
球相同，盒子不同，允许空盒
可以看作，先在最后添上$m$个球，总共$n+m$个球，往里插$m-1$个板子，然后从这$m$部分中每部分拿掉一个球，就变成了这种情况
$$
C_{n-1}^{n+m-1}= \sum_{i=1}^{m}C^{i-1}_{n-1}
$$
球不同，盒子相同，不允许空盒
第二类斯特林数 $String$
考虑第$n$个球
- 若前$n-1$个球形成了$m-1$个集合，那么第$n$个球必须新开一个集合。因为盒子没有顺序（或者说一开始已经固定了顺序），所以不用乘$n-m+1$
- 若前$n-1$个球已经形成了$m$个集合，那第$n$个球可以插到其中任意一个中。因为第$n$个球是独一无二的，所以要乘$m$
球不同，盒子相同，允许空盒
答案就是
球不同，盒子不同，不允许空盒
答案就是
因为情况5中的每一种方案，任意两个集合交换后形成的方案一定与本身不同（若球都一样的话就不一定了，详见下文）
球不同，盒子不同，允许空盒
$$
m^n
$$
