问题:$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
$$