继续填小学没学好的坑

都高二了还这么菜...

Content

nn个球,放到mm个盒子里(nmn\ge m),主要有下列八种情况:

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

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

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

f[n][m]f[n][m]表示答案,那么

f[n][m]=f[n1][m1]+f[nm][m] f[n][m] = f[n - 1][m - 1] + f[n - m][m]
  • 另外,也可以从允许空盒的方案(情况2gg推出:

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

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

g[n][m]g[n][m]表示答案,那么

g[n][m]=g[n][m1]+g[nm][m] g[n][m] = g[n][m - 1] + g[n - m][m]

(因为新增的盒子可以为空了)

  • ff情况1)的关系:

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

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

插板法,总共n1n-1个间隔,插m1m-1个板子

答案即为(n1m1)\displaystyle \binom{n-1}{m-1}

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

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

答案是(n+m1m1)\displaystyle \binom{n+m-1}{m-1}

或者直接从代数角度

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

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

  • 如何从情况4情况3

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

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

第二类斯特林数

考虑第nn个球

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

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

答案就是

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

答案就是

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

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

答案就是mnm^n

Summary

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

    例如:

    • 情况1、2相当于先把球固定,考虑盒子的过程中盒子的顺序也是固定的(保证非严格递减)
    • 情况3、4相当于把球固定,考虑盒子如何摆
    • 情况5、6相当于把盒子的顺序固定,依次考虑每个球放到哪个盒子里
  • Q. 为什么57可以直接乘8!8!,而13不行?

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

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