组合计数与递推数列初步:球盒问题

计数问题(counting problems)是国内算法竞赛流行的一类问题,由于方法众多、技巧要求高等缘故,这类题目往往给初学者带来不小的困难。这篇文章将通过对球和盒子的八个经典问题进行总结,对组合数与递推数列在计数问题上的初步应用做一个简单介绍。

球和盒子问题的描述如下:将\(n\)个球放入\(m\)个盒子中(\(n\geq m\)),求有多少种本质不同的方案数。由于球可以完全相同或互不相同、盒子可以完全相同或互不相同、盒子可以允许为空或不允许为空,所以这个问题一共有八个小问。

我们首先给出问题的全部结论,然后根据难度从易到难对每种情况进行推导。

问题编号 小球 盒子 允许为空 方案数
完全相同 完全相同 允许 \(G[n][m]\)
完全相同 完全相同 不允许 \(G[n-m][m]\)
完全相同 互不相同 允许 \(C_{n+m-1}^{m-1}\)
完全相同 互不相同 不允许 \(C_{n-1}^{m-1}\)
互不相同 完全相同 允许 \(\sum_{i=1}^mF[n][i]\)
互不相同 完全相同 不允许 \(F[n][m]\)
互不相同 互不相同 允许 \(m^n\)
互不相同 互不相同 不允许 \(m!\cdot F[n][m]\)

其中涉及两个递推数列,递推式分别如下:

$$F[n][m]=F[n-1][m-1]+m\cdot F[n-1][m]$$

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

⑦小球不同,盒子不同,允许为空

这是最简单的情形,考虑每个小球有\(m\)个盒子可以选择放入,而一共又有\(n\)个小球,所以方案数为\(m^n\)。注意这种放法下有可能有盒子为空,比如可能把所有球都放到同一个盒子里,故要求允许为空。

④小球相同,盒子不同,不允许为空

考虑插板法:将\(n\)个小球排成一排,将\(m-1\)块板子插在小球之间的空隙中,每个空隙中最多插一块板子,再假设最左端和最右端各有一块板子,这样每两块相邻的板子代表一个盒子,它们之间夹着的小球就是放在这个盒子中的小球。由于一共有\(n-1\)个缝隙,所以答案为\(C_{n-1}^{m-1}\)。

由于每个空隙只允许插一块板子,故所有的方案里盒子都非空。假如有两对板子之间都夹了相同个数的小球,把它们之间的小球交换后再这里被认为是和原来相同的方案,故要求小球相同。又比如\(2,2,1\)和\(1,2,2\)被视为不同的方案,故要求盒子不同,即有每个盒子是“第几个”盒子的意义在里面。

③小球相同,盒子不同,允许为空

与④中情况类似,同样使用插板法,但是现在两块板子可以插到同一个缝隙中。我们考虑插板后的结果,是\(m-1\)块板子和\(n\)个小球一共\(n+m-1\)个物体排成一排,考虑这些物体中有\(m-1\)个板子即是一种方案,所以答案为\(C_{n+m-1}^{m-1}\)。

⑥小球不同,盒子相同,不允许为空

考虑递推,设\(F[n][m]\)表示将\(n\)个小球放入\(m\)个盒子中的方案数。由于小球互不相同,考虑第\(i\)个小球的方法,可以是放到前\(i-1\)个小球已经放过的盒子中,也可以放到一个新盒子中。

假设前\(i-1\)个小球已经占用了\(j\)个盒子,由于小球互不相同,故放了小球的盒子也应该被视为互不相同的,所以将第\(i\)个小球放入这些盒子共有\(j\)种不同方案。如果将第\(i\)个小球放入一个新盒子,由于盒子都是相同的,所以只有一种方案。

综上所述,最后的递推式为\(F[i][j]=j\cdot F[i-1][j]+F[i-1][j-1]\)。

⑧小球不同,盒子不同,不允许为空

与⑥中情况类似,只是现在盒子互不相同,我们只需要在⑥的基础上,对盒子做一个全排列即可。由于盒子共有\(m\)个,故总方案数为\(m!\cdot F[n][m]\)。

⑤小球不同,盒子相同,允许为空

与⑥中情况类似,只是现在盒子允许为空,我们只需要在⑥的基础上,枚举一下使用了多少个盒子即可,总方案数为\(\sum_{i=1}^mF[n][m]\)。

①小球相同,盒子相同,允许为空

由于这种情况下小球都是相同的,所以我们不能再用放“第几个”小球这样的顺序和思路来考虑问题了。换一个思路,假设初始时我们既没有盒子也没有小球,考虑用如下两个操作来构造出所有方案:增加一个全新的盒子,或给所有已有的盒子中各放入一个小球。

容易知道,任意一种合法的方案都可以通过上述两种操作构造出来,且构造方式是唯一的。设\(G[n][m]\)表示将\(n\)个小球放入\(m\)个盒子中的方案数,由两种操作的描述即可得递推式\(G[i][j]=G[i][j-1]+G[i-j][j]\)。

②小球相同,盒子相同,不允许为空

与①中情况类似,现在要求盒子均不能为空,只需事先给每个盒子放入一个球即可,总方案数为\(G[n-m][m]\)。

发表评论

电子邮件地址不会被公开。 必填项已用*标注