「Algorithm」放球问题

继续填小学没学好的坑

都高二了还这么菜...

Content

$n$个球，放到$m$个盒子里（$n\ge m$），主要有下列八种情况：

序号	$n$个球是否有区别	$m$个盒子是否有区别	是否允许空盒
1	否	否	否
2	否	否	是
3	否	是	否
4	否	是	是
5	是	否	否
6	是	否	是
7	是	是	否
8	是	是	是

一、球相同，盒子相同，不允许空盒

要保证盒子大小非严格递减。每次把当前所有盒子里的球都$+1$；或者新增一个盒子，里面放一个球

设$f[n][m]$表示答案，那么

$f[n][m] = f[n - 1][m - 1] + f[n - m][m]$

• 另外，也可以从允许空盒的方案（情况2）$g$推出：

  每个盒子里都先铺一个球，即$f[n][m] = g[n - m][m]$

二、球相同，盒子相同，允许空盒

设$g[n][m]$表示答案，那么

$g[n][m] = g[n][m - 1] + g[n - m][m]$

（因为新增的盒子可以为空了）

• 与$f$（情况1）的关系：

  $\displaystyle g[n][m] = \sum_{i=1}^{m}f[n][i]$

三、球相同，盒子不同，不允许空盒

插板法，总共$n-1$个间隔，插$m-1$个板子

答案即为$\displaystyle \binom{n-1}{m-1}$

四、球相同，盒子不同，允许空盒

可以看作，先在最后添上$m$个球，总共$n+m$个球，往里插$m-1$个板子，然后从这$m$部分中每部分拿掉一个球，就变成了这种情况

答案是$\displaystyle \binom{n+m-1}{m-1}$

或者直接从代数角度

答案等于$\displaystyle \sum_{i=1}^{m}\binom{n-1}{i-1}$

根据杨辉三角某一列的前缀和，就等于最下面那个位置右下角的值，即$\displaystyle \binom{n+m-1}{m-1}$

• 如何从情况4推情况3？

  允许空盒的方案是$n+m$个球插$m-1$个板子。在每个盒子里先铺一个球，那么只剩$n$个球了。插$m-1$个板子的方案数就是$\displaystyle \binom{n-1}{m-1}$

五、球不同，盒子相同，不允许空盒

第二类斯特林数

考虑第$n$个球

• 若前$n-1$个球形成了$m-1$个集合，那么第$n$个球必须新开一个集合。因为盒子没有顺序（或者说一开始已经固定了顺序），所以不用乘$n-m+1$
• 若前$n-1$个球已经形成了$m$个集合，那第$n$个球可以插到其中任意一个中。因为第$n$个球是独一无二的，所以要乘$m$

六、球不同，盒子相同，允许空盒

答案就是

七、球不同，盒子不同，不允许空盒

答案就是

因为情况5中的每一种方案，任意两个集合交换后形成的方案一定与本身不同（若球都一样的话就不一定了，详见下文）

八、球不同，盒子不同，允许空盒

答案就是$m^n$

• 与情况7关系：

枚举空盒数量，是个经典的式子

Summary

• 什么东西是无标号的，那么就可以给它随便钦定一种顺序，形象地理解就是把它固定不动，再考虑另一个东西

  例如：

  • 情况1、2相当于先把球固定，考虑盒子的过程中盒子的顺序也是固定的（保证非严格递减）
  • 情况3、4相当于把球固定，考虑盒子如何摆
  • 情况5、6相当于把盒子的顺序固定，依次考虑每个球放到哪个盒子里

• Q. 为什么5到7可以直接乘$8!$，而1到3不行？

  A. 因为盒子是否有区别，不仅取决于是否有标号，还与集合大小有关！

  例如，在球不同，盒子不同的情况下，$\{1, 2, 3\},\{4, 5, 6\}$与$\{4, 5, 6\},\{1, 2, 3\}$是不同的。但若球不同，这两种情况都是$\{3\},\{3\}$，没有区别。这里需要注意