把球放到瓶子问题合集

xianrena

从一个朋友处得来的，总结得很全面。

——————————————————————————————————————————————————————

概率中的数数问题绝大多数都可以归结为把球放到瓶子里的过程，下面我们就看看把球放到瓶子里有多少种放法。参考：Enumerative Combinatorics, Volume 1, Richard Stanley

首先，球可以分成可被区分和不可被区分两种情况，瓶子也可以被分成可被区分和不可以被区分两种情况，而放球的方法，则可以分成没有限制条件，每个瓶子至少一个球和每个瓶子最多一个球这三种情况，所以整体来说，总共有12种情况。下面就这12中情况，进行分别讨论。

设定，球有b个，瓶子有u个。

1、球可区分，瓶子可区分，没有限制条件

这个比较简单，u的b次方

2、球可区分，瓶子可区分，每个瓶子里最多一个球

如果，b>u，无解

b<=u，u(u-1)(u-2)...(u-b+1)

3、球不可分，瓶子可分，每个瓶子最多一个球

如果，b>u，无解

如果b<=u，则C(u,b)

4、球不可区分，瓶子可区分，每个瓶子至少一个球

如果，b<u，无解

如果，b>=u

这种情况可以看成b个球中间放u-1个隔板，b中间的间隔有b-1个间隔，则方法有C(b-1,u-1)

5、球不可区分，瓶子可区分，没有限制

这种情况比较烦，但是在放好球之后，我们可以在每个瓶子中再放一个球，这就转化成了情况4，由于球不可分，所以这是放球的方法是一样的。即C(b+u-1,u-1)=C(b+u-1,b)

6、球可区分，瓶子不可区分，每个瓶子至少一个球

b<u，无解

b>=u，这种情况比较复杂，先把结果记为S(b,u)。当放最后一个球的时候，有两种情况：一、u个瓶子里至少有一个球了，则前面放球的方法有S(b-1,u)，而最后一个球则可以放到任何一个瓶子里，则一共有uS(b-1,u)种放球的方法；二、还有一个空瓶子（不可能有更多空瓶子了），则前面放球的方法有S(b-1,u-1)。所以综合两种情况，S(b,u)=uS(b-1,u)+S(b-1,u-1)。这种情况没有更简化的形式，可以写个递归的程序算一下。

7、球可区分，瓶子可区分，每个瓶子至少一个球

b<u，无解

b>=u，这种情况的结果是u!S(b,u)，可以先认为是情况6，然后在把瓶子可区分的条件加上去。

8、球可区分，瓶子不可区分，没有限制

如果有u'个瓶子装了球，则可看成S(b,u')，由于瓶子不可区分，取多少个瓶子情况只有一种，则整体的放球方法有：S(b,1)+S(b,2)+...+S(b,u)。

9、球可区分，瓶子不可区分，每个瓶子最多一个球

b>u，无解

b<=u，1

10、球不可区分，瓶子不可区分，每个瓶子最多一个球

b>u，无解

b<=u，1

11、球不可区分，瓶子不可区分，每个瓶子至少一个球

b<u，无解

b>=u，这种情况也比较复杂，先把结果记为p(b,u)。在放最后一个球之前，有两种情况：一、一个瓶子是空的，则前面放球的方法有p（b-1,u-1)；二、每个瓶子里至少一个球，但是放完最后一个球之后，每个瓶子里至少两个球，不然会与第一种情况相重，所以第二种情况有p(b-u,u）中放球的方法。总体可得p(b,u)=p(b-1,u-1)+p(b-u,u)。

12、球不可分，瓶子不可分，没有限制

参照情况8，可得p(b,1)+p(b,2)+...+p(b,u)。