组合数学-第八节：分配问题

1、2.7 分配问题所谓分配问题，粗略地说，就是把一些球放入一些盒子中的放法问题。本节中，我们将本章前几节所讨论的各类计数问题的结果应用到分配问题上，得到不同类型的分配问题的分配方案数。把n个球分放到r个盒子里，共有多少种不同的方案？本节中我们假定球在盒内是无序的，但我们要考虑以下三个方面的因素：（i）n个球是完全相同的还是完全不同的；（ii）n个盒子是完全相同的还是完全不同的；（iii）是否允许有空盒。下面我们来分类讨论：（1）把n个完全不同的球放入r个不同的盒子里，允许有空盒的方案数为。将n个不同的球分别记为个不同的盒子分别记为，每个球都可以放入r个不同的盒子中的任一个，即每个球都有r种不同的

2、放法，因而n个不同的球共有种放法。事实上，这个问题可以看成r个不同的盒子所构成的多重集合的n排列问题。对于M的一个n排列，我们将其映射到放入中的一种方案，若该n排列的第i个位置是，则将球放入盒子中。例如，有4个不同的球和3个不同的盒子，对应于的4排列：的放法是和放在盒子中，和放在盒子中。上面建立的映射显然是一一映射，所以此类分配方案数等于多重集合的n排列数。（2）把n个完全不同的球放入r个不同的盒子里，不允许有空盒的方案数为。先认出盒子是完全相同的，把n个球构成的集合：划分成r个非空子集，即：然后将每个放入一个盒子里，构成一个没有空盒的分配方案。这里，是A的一个r分划，其方案数为。而这里r个盒

3、子是完全不同的，所以，A的r个子集的不同排列构成的分配方案是不同的。由此可知，n个不同的球放入r个不同的盒子里，不允许有空盒的方案数为。（3）把n个完全不同的球放入r个相同的盒子里，不允许有空盒的方案数为由（2）的分析知，此类分配方案数为（4）把n个完全不同的球放入r个相同的盒子里，允许有空盒的方案数为对于n个不同的球放入r个相同的盒子里并允许有空盒的一种放法，设有个盒子不空，而另外个盒子为空，这就相当于将n个不同的球放i个相同的盒子里，并不允许有空盒的一种放法。由加法原则及（3）知，分配方案数为：（5）把n个相同的球放入r个相同的盒子里，不允许有空盒的方案数为这个问题相当于将整数n进行r分拆

4、，方案数为（6）把n个相同的球放入r个相同的盒子里，允许有空盒的方案数为类似于（4），由（5）知这个问题相当于整数n的不大于r的所有分拆数，即为（7）把n个相同的球放入r个完全不同的盒子里，允许有空盒的方案数为这个问题相当于求方程：的非负整数解的个数。对应于该方程的一组解，相当于将个球放入第1个盒子里，将个球放入第2个盒子里，将个球放入第r个盒子里。所以，总的分配方案数为。设r个不同的盒子分别为，则这个问题也相当于求多重集合的n组合数。对于M的一个n组合，我们将其映射到n个球放入r个盒子里的一种放法：若该组合中有个，就将球放入中。上面的映射显然是一一映射。所以，此类分析方案数等于M的n组合数。

5、（8）把n个相同的球放入r个完全不同的盒子里，不允许有空盒的方案数为。类似于（7），这里要求的是方程：（2.7.1）的正整数解的个数。由定理2.3.4的证明知，其个数为。事实上，方程（2.7.1）的一个正整数解也就是正整数n的一个有序r分拆，由定理2.6.1知，其个数为。综合上述分析，我们得到各种情形下的分配方案数，见表2.7.1。表2.7.1 分配方案数表下面介绍几个有关分配问题的例子。例1 打桥牌时，52张牌分发给4个人，每人13张，问每人有一张A的概率有多少？解 首先给4个人每人发一张A，然后再将剩下的48张牌分给4个人。这里将人看成盒子，把牌看成球，但这里的问题与（1），（2）不同，要

6、求了每个盒子里放入球的数目，所以不能机械地套用（1），（2）中的公式。正确的做法是从48张牌中选出12张给第一个人，再从剩下的36张牌中选出12张给第二个人，依次下去。所以，将48张牌分给4个人的方法数为每人发一张A的方法数为，从而每人有一张A的方法数为：而每人有13张牌的方法数为，由此可知，每人有一张A的概率为：例2 的展开式有多少项？解 的展开式中的每一项都是4次方，相当于将4个无区别的球放入3个有标志的盒子里，每个盒子中放进的球不加限制。例如，相当于将4个球都放进盒子中，盒子为空；相当于将2个球放进盒子中，盒子中各放进一个球。所以，项数：这15项分别为例3 会议室中有个座位，现摆成3排，

7、要求任何两排的座位数都要占大多数，问有多少种摆法？解 这个问题相当于把个完全相同的球分配到3个不同的盒子里，如果没有附加限制，应该有种方案。不符合题意的摆法的特征是有一排至少有个座位，这相当于将个座位先放到3排中的某一排，再将剩下的个座位任意分到3排中，这种摆法共有种方案。本例中，如果将座位总数改为2n，如上，没有附加限制条件的摆法有种。不符合题意的摆法的特征是某一排最少有n个座位的摆法有：（2.7.2）种。但这3种方案中都有两排的座位不少于n，所以在（2.7.2）的计数中，这3种方案中的每一个都在相应的两排中各计算了一次。所以，不合题意的摆法有：种，符合题意的摆法有：种。例4 把4个相同的桔子和6个不同的苹果放到5个不同的盒子里，问每个盒子里有2个水果的概率有多大？解 把4个相同的桔子放入5个不同的盒子里有种方法，把6个不同的苹果放入5个不同的盒子里有种方法，总共有种分配方法。每个盒子里有2个水果，有如下几种情况：（i）（苹苹）（苹苹）（苹苹）（桔桔）（桔桔）先从5个不同的盒子中选出2个放桔子，因为桔子是相同的，只要简单地一个盒子里放2个即可。剩下的3个不同的盒子放6个不同的苹果。此类放法共有种。（ii）（苹苹）（苹苹）（桔桔）（苹桔）（苹桔）先从5个不同的盒子里选出1个放2个桔子，再从剩下的4个不同的