组合数学——“盒子与小球问题”详解（2）

· · 个人记录

“盒子与小球”问题

“盒子与小球”问题指的是如下这一类问题：把k个小球放到n个盒子里，求一共有多少种方案。这类问题的约束条件有很多种，诸如盒子编号的，小球是编号的，盒子不编号（任意两个盒子没有区别），小球不编号（任意两个小球没有区别），允许有空盒，不允许有空盒，允许小球不放完，不允许小球不放完等等。

问题变种（1）：n个一样的小球放到k个编号的盒子里，允许盒子空，但小球必须全部放入盒子，一共有多少种方案？

记此问题的解为f(n,k)；当不允许盒子空时，是基础版的“盒子与小球”问题，解为: g(n,k) = C_{n-1}^{k-1};

不允许盒子空，则每个盒子至少有一个元素。如果从不允许盒子空的方案的每一个盒子中都分别拿走一个元素，就会成了允许盒子空的一个解，而且这些解显然是一一对应的，不会有重复解，也不会漏解。

假设我们进行如下两步操作：

（1）先把每一个盒子都装填1个元素，由于元素无编号，所以一共有1种方案；
（2）然后，按照允许盒子空的方式（用f表示允许盒子空的方式，g表示不允许盒子空的方式）装填k个盒子，一共装入n个元素，因此方案数为：f(n,k);
通过上述两个步骤产生的方案一共有1 × f(n,k) = f(n,k)种；

由于f方式允许盒子空，但每组都预先装填了一个元素，因此通过上述两个步骤产生的方案实际上是每组至少有一个元素的方案，即不允许盒子空的方案。一共放入了n+k个球，因此可以记为：g(n+k,k);

因此，f(n,k) = g(n+k,k) = C_{n+k-1}^{k-1};

从这个式子还可以看出：n个一样的小球放到k个编号的盒子里，允许盒子空的方案数可以由不允许盒子空的放置方案转移而来，具体方式是：从不允许盒子空的方案的每一个盒子中都拿走一个元素。因为拿走k个元素后还剩n个元素，因此f（n，k）可以由g(n+k,k)转移而来。

综上所述，问题变种（1）：n个一样的小球放到k个编号的盒子里，允许盒子空，方案数量为：

f(n,k)=C_{n+k-1}^{k-1}

问题变种（2）：n个一样的小球放到k个编号的盒子里，允许盒子空，且小球不必全部放入盒子，一共有多少种方案？

记小球不必全部放入盒子，允许盒子空的方案为u(n，k)。
从前面的问题变种（1）可以看到，我们可以修改其中一个约束条件，尝试从新问题的解转移到本问题的解。

不妨尝试从小球必须全部放入盒子的解转移过来。小球必须全部放入盒子的解为f(n,k),假设经过下面两个步骤操作：

（1）按照f的方式，把n个小球放入k个盒子，方案数量为f(n,k)。
（2）去掉第k组及其内部的元素。这样每一个f方式放置的方案都能转变为一个f(n-x,k-1)的方案，x=0，1，2，3....;x为第k组内可能含有的元素个数。

根据操作，上述两个步骤的操作，产生的方案数量为：

f(n,k)

由于第（2）步拿走了一个组及其内部的球，相当于球没有放完或者球剩余在手上，且剩余的球可以遍取0，1，2，3...n,因此由（1）（2）两部产生的解即u(n,k-1)。
故：

f(n,k)=u(n,k-1)

用k+1代k，得：

u(n,k)=f(n,k+1)=g(n+k+1,k+1)=C_{n+k}^{k}

从另外一个角度也可以解释：

根据题意，允许不放完小球的方案，即把放入0，1，2，3....n个小球的所有“放完”小球的方案加起来：

u(n,k)=\sum_{i=0}^{n}f(i,k)

用k-1代替k，则有：

u(n,k-1)=\sum_{i=0}^{n}f(i,k-1)

回到前面两个操作，按照去掉的第k组的元素个数分类，根据加法原理得：

f(n,k)=\sum_{i=0}^{n}f(n-i,k-1)

即：

f(n,k)=\sum_{i=0}^{n}f(i,k-1)

对比得到：u(n,k-1)=f(n,k)
再用k+1代替k，即得：

u(n,k)=f(n,k+1)=g(n+k+1,k+1)=C_{n+k}^{k}

综上所述，把n个一样的小球放入k个编号的盒子里，允许盒子空，并且小球可以不放完，方案数为：

u(n,k)=C_{n+k}^{k}=C_{n+k}^{n}