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

2.7分配问题所谓分配问题，粗略地说，就是把一些球放入一些盒子中的放法问题。本节中，我们将本章前几节所讨论的各类计数问题的结果应用到分配问题上，得到不同类型的分配问题的分配方案数。把n个球分放到r个盒子里，共有多少种不同的方案？本节中我们假定球在盒内是无序的，但我们要考虑以下三个方面的因素：（i）n个球是完全相同的还是完全不同的；（ii）n个盒子是完全相同的还是完全不同的；（iii）是否允许有空盒。下面我们来分类讨论：（1）把n个完全不同的球放入r个不同的盒子里，允许有空盒的方案数为nr。将n个不同的球分别记为12,,,nxxxr个不同的盒子分别记为12,,rbbb，每个球1ixin都可以放入r个不同的盒子1jbjr中的任一个，即每个球都有r种不同的放法，因而n个不同的球共有nr种放法。事实上，这个问题可以看成r个不同的盒子所构成的多重集合12,,,rMbbb的n排列问题。对于M的一个n排列，我们将其映射到12,,nxxx放入12,,rbbb中的一种方案，若该n排列的第i个位置是1ijbir，则将球ix放入盒子ijb中。例如，有4个不同的球1234,,,xxxx和3个不同的盒子123,,bbb，对应于123,,Mbbb的4排列：1231bbbb的放法是1x和4x放在盒子1b中，2x和3x放在盒子2b中。上面建立的映射显然是一一映射，所以此类分配方案数等于多重集合12,,,rMbbb的n排列数nr。（2）把n个完全不同的球放入r个不同的盒子里，不允许有空盒的方案数为!,rSnr。先认出盒子是完全相同的，把n个球构成的集合：12,,nAxxx划分成r个非空子集12,,rAAA，即：12rAAAA然后将每个1iAir放入一个盒子里，构成一个没有空盒的分配方案。这里，12,,rAAA是A的一个r分划，其方案数为,Snr。而这里r个盒子是完全不同的，所以，A的r个子集的不同排列构成的分配方案是不同的。由此可知，n个不同的球放入r个不同的盒子里，不允许有空盒的方案数为!,rSnr。（3）把n个完全不同的球放入r个相同的盒子里，不允许有空盒的方案数为,Snr由（2）的分析知，此类分配方案数为,Snr（4）把n个完全不同的球放入r个相同的盒子里，允许有空盒的方案数为1,riSni对于n个不同的球放入r个相同的盒子里并允许有空盒的一种放法，设有1iir个盒子不空，而另外ri个盒子为空，这就相当于将n个不同的球放i个相同的盒子里，并不允许有空盒的一种放法。由加法原则及（3）知，分配方案数为：1,riSni（5）把n个相同的球放入r个相同的盒子里，不允许有空盒的方案数为,Bnr这个问题相当于将整数n进行r分拆，方案数为,Bnr（6）把n个相同的球放入r个相同的盒子里，允许有空盒的方案数为1,riBni类似于（4），由（5）知这个问题相当于整数n的不大于r的所有分拆数，即为1,riBni（7）把n个相同的球放入r个完全不同的盒子里，允许有空盒的方案数为1nrn这个问题相当于求方程：12rxxxn的非负整数解的个数。对应于该方程的一组解12rxxx，相当于将1x个球放入第1个盒子里，将2x个球放入第2个盒子里，……，将rx个球放入第r个盒子里。所以，总的分配方案数为1nrn。设r个不同的盒子分别为12,,,rbbb，则这个问题也相当于求多重集合12,,,rMbbb的n组合数。对于M的一个n组合，我们将其映射到n个球放入r个盒子里的一种放法：若该组合中有ix个ib，就将ix球放入ib中1ir。上面的映射显然是一一映射。所以，此类分析方案数等于M的n组合数1nrn。（8）把n个相同的球放入r个完全不同的盒子里，不允许有空盒的方案数为11nr。类似于（7），这里要求的是方程：12rxxxn（2..7.1）的正整数解的个数。由定理2.3.4的证明知，其个数为11nr。事实上，方程（2.7.1）的一个正整数解也就是正整数n的一个有序r分拆，由定理2.6.1知，其个数为11nr。综合上述分析，我们得到各种情形下的分配方案数，见表2.7.1。表2.7.1分配方案数表下面介绍几个有关分配问题的例子。例1打桥牌时，52张牌分发给4个人，每人13张，问每人有一张A的概率有多少？解首先给4个人每人发一张A，然后再将剩下的48张牌分给4个人。这里将人看成盒子，把牌看成球，但这里的问题与（1），（2）不同，要求了每个盒子里放入球的数目，所以不能机械地套用（1），（2）中的公式。正确的做法是从48张牌中选出12张给第一个人，再从剩下的36张牌中选出12张给第二个人，依次下去。所以，将48张牌分给4个人的方法数为48!12!12!12!12!每人发一张A的方法数为4!，从而每人有一张A的方法数为：448!4!12!而每人有13张牌的方法数为52!13!4，由此可知，每人有一张A的概率为：4413!48!4!10.55%12!52!例24xyz的展开式有多少项？解4xyz的展开式中的每一项都是4次方，相当于将4个无区别的球放入3个有标志的盒子,,xyz里，每个盒子中放进的球不加限制。例如，4x相当于将4个球都放进盒子x中，盒子,yz为空；2xyz相当于将2个球放进盒子x中，盒子,yz中各放进一个球。所以，4,3rn，项数：43161544N这15项分别为433222223322223344,,,,,,,,,,,,,,xxyxzxyzxyxzxyxzxyzxyzyzyzzyyz例3会议室中有21n个座位，现摆成3排，要求任何两排的座位数都要占大多数，问有多少种摆法？解这个问题相当于把21n个完全相同的球分配到3个不同的盒子里，如果没有附加限制，应该有232131221nnn种方案。不符合题意的摆法的特征是有一排至少有1n个座位，这相当于将1n个座位先放到3排中的某一排，再将剩下的211nnn个座位任意分到3排中，这种摆法共有211312332112nnnnn种方案。本例中，如果将座位总数改为2n，如上，没有附加限制条件的摆法有2312222nnn种。不符合题意的摆法的特征是某一排最少有n个座位的摆法有：2223322nnnnn（2.7.2）种。但0,,,,0,,,,0nnnnnn这3种方案中都有两排的座位不少于n，所以在（2.7.2）的计数中，这3种方案中的每一个都在相应的两排中各计算了一次。所以，不合题意的摆法有：2332n种，符合题意的摆法有：222133222nnn种。例4把4个相同的桔子和6个不同的苹果放到5个不同的盒子里，问每个盒子里有2个水果的概率有多大？解把4个相同的桔子放入5个不同的盒子里有451844种方法，把6个不同的苹果放入5个不同的盒子里有65种方法，总共有6854种分配方法。每个盒子里有2个水果，有如下几种情况：（i）（苹苹）（苹苹）（苹苹）（桔桔）（桔桔）先从5个不同的盒子中选出2个放桔子，因为桔子是相同的，只要简单地一个盒子里放2个即可。剩下的3个不同的盒子放6个不同的苹果。此类放法共有56!22!2!2!种。（ii）（苹苹）（苹苹）（桔桔）（苹桔）（苹桔）先从5个不同的盒子里选出1个放2个桔子，再从剩下的4个不同的盒子中选出2个各放1个桔子。剩下6个苹果放入4个不同的盒子里，这4个盒子里苹果的数量分别为2个、2个、1个、1个。所以，共有546!122!2!1!1!种方案。（iii）（苹苹）（苹桔）（苹桔）（苹桔）（苹桔）与（ii）类似，方法数为456!42!1!综合上述分析，每个盒子里有2个水果的概率为32655456!6!6!21242!2!2!7.4%854