1、2.7 分配問(wèn)題所謂分配問(wèn)題，粗略地說(shuō)，就是把一些球放入一些盒子中的放法問(wèn)題。本節(jié)中，我們將本章前幾節(jié)所討論的各類(lèi)計(jì)數(shù)問(wèn)題的結(jié)果應(yīng)用到分配問(wèn)題上，得到不同類(lèi)型的分配問(wèn)題的分配方案數(shù)。把n個(gè)球分放到r個(gè)盒子里，共有多少種不同的方案？本節(jié)中我們假定球在盒內(nèi)是無(wú)序的，但我們要考慮以下三個(gè)方面的因素：（i）n個(gè)球是完全相同的還是完全不同的；（ii）n個(gè)盒子是完全相同的還是完全不同的；（iii）是否允許有空盒。下面我們來(lái)分類(lèi)討論：（1）把n個(gè)完全不同的球放入r個(gè)不同的盒子里，允許有空盒的方案數(shù)為。將n個(gè)不同的球分別記為個(gè)不同的盒子分別記為，每個(gè)球都可以放入r個(gè)不同的盒子中的任一個(gè)，即每個(gè)球都有r種不同的

2、放法，因而n個(gè)不同的球共有種放法。事實(shí)上，這個(gè)問(wèn)題可以看成r個(gè)不同的盒子所構(gòu)成的多重集合的n排列問(wèn)題。對(duì)于M的一個(gè)n排列，我們將其映射到放入中的一種方案，若該n排列的第i個(gè)位置是，則將球放入盒子中。例如，有4個(gè)不同的球和3個(gè)不同的盒子，對(duì)應(yīng)于的4排列：的放法是和放在盒子中，和放在盒子中。上面建立的映射顯然是一一映射，所以此類(lèi)分配方案數(shù)等于多重集合的n排列數(shù)。（2）把n個(gè)完全不同的球放入r個(gè)不同的盒子里，不允許有空盒的方案數(shù)為。先認(rèn)出盒子是完全相同的，把n個(gè)球構(gòu)成的集合：劃分成r個(gè)非空子集，即：然后將每個(gè)放入一個(gè)盒子里，構(gòu)成一個(gè)沒(méi)有空盒的分配方案。這里，是A的一個(gè)r分劃，其方案數(shù)為。而這里r個(gè)盒

3、子是完全不同的，所以，A的r個(gè)子集的不同排列構(gòu)成的分配方案是不同的。由此可知，n個(gè)不同的球放入r個(gè)不同的盒子里，不允許有空盒的方案數(shù)為。（3）把n個(gè)完全不同的球放入r個(gè)相同的盒子里，不允許有空盒的方案數(shù)為由（2）的分析知，此類(lèi)分配方案數(shù)為（4）把n個(gè)完全不同的球放入r個(gè)相同的盒子里，允許有空盒的方案數(shù)為對(duì)于n個(gè)不同的球放入r個(gè)相同的盒子里并允許有空盒的一種放法，設(shè)有個(gè)盒子不空，而另外個(gè)盒子為空，這就相當(dāng)于將n個(gè)不同的球放i個(gè)相同的盒子里，并不允許有空盒的一種放法。由加法原則及（3）知，分配方案數(shù)為：（5）把n個(gè)相同的球放入r個(gè)相同的盒子里，不允許有空盒的方案數(shù)為這個(gè)問(wèn)題相當(dāng)于將整數(shù)n進(jìn)行r分拆

4、，方案數(shù)為（6）把n個(gè)相同的球放入r個(gè)相同的盒子里，允許有空盒的方案數(shù)為類(lèi)似于（4），由（5）知這個(gè)問(wèn)題相當(dāng)于整數(shù)n的不大于r的所有分拆數(shù)，即為（7）把n個(gè)相同的球放入r個(gè)完全不同的盒子里，允許有空盒的方案數(shù)為這個(gè)問(wèn)題相當(dāng)于求方程：的非負(fù)整數(shù)解的個(gè)數(shù)。對(duì)應(yīng)于該方程的一組解，相當(dāng)于將個(gè)球放入第1個(gè)盒子里，將個(gè)球放入第2個(gè)盒子里，將個(gè)球放入第r個(gè)盒子里。所以，總的分配方案數(shù)為。設(shè)r個(gè)不同的盒子分別為，則這個(gè)問(wèn)題也相當(dāng)于求多重集合的n組合數(shù)。對(duì)于M的一個(gè)n組合，我們將其映射到n個(gè)球放入r個(gè)盒子里的一種放法：若該組合中有個(gè)，就將球放入中。上面的映射顯然是一一映射。所以，此類(lèi)分析方案數(shù)等于M的n組合數(shù)。

5、（8）把n個(gè)相同的球放入r個(gè)完全不同的盒子里，不允許有空盒的方案數(shù)為。類(lèi)似于（7），這里要求的是方程：（2.7.1）的正整數(shù)解的個(gè)數(shù)。由定理2.3.4的證明知，其個(gè)數(shù)為。事實(shí)上，方程（2.7.1）的一個(gè)正整數(shù)解也就是正整數(shù)n的一個(gè)有序r分拆，由定理2.6.1知，其個(gè)數(shù)為。綜合上述分析，我們得到各種情形下的分配方案數(shù)，見(jiàn)表2.7.1。表2.7.1 分配方案數(shù)表下面介紹幾個(gè)有關(guān)分配問(wèn)題的例子。例1 打橋牌時(shí)，52張牌分發(fā)給4個(gè)人，每人13張，問(wèn)每人有一張A的概率有多少？解 首先給4個(gè)人每人發(fā)一張A，然后再將剩下的48張牌分給4個(gè)人。這里將人看成盒子，把牌看成球，但這里的問(wèn)題與（1），（2）不同，要

6、求了每個(gè)盒子里放入球的數(shù)目，所以不能機(jī)械地套用（1），（2）中的公式。正確的做法是從48張牌中選出12張給第一個(gè)人，再?gòu)氖Ｏ碌?6張牌中選出12張給第二個(gè)人，依次下去。所以，將48張牌分給4個(gè)人的方法數(shù)為每人發(fā)一張A的方法數(shù)為，從而每人有一張A的方法數(shù)為：而每人有13張牌的方法數(shù)為，由此可知，每人有一張A的概率為：例2 的展開(kāi)式有多少項(xiàng)？解 的展開(kāi)式中的每一項(xiàng)都是4次方，相當(dāng)于將4個(gè)無(wú)區(qū)別的球放入3個(gè)有標(biāo)志的盒子里，每個(gè)盒子中放進(jìn)的球不加限制。例如，相當(dāng)于將4個(gè)球都放進(jìn)盒子中，盒子為空；相當(dāng)于將2個(gè)球放進(jìn)盒子中，盒子中各放進(jìn)一個(gè)球。所以，項(xiàng)數(shù)：這15項(xiàng)分別為例3 會(huì)議室中有個(gè)座位，現(xiàn)擺成3排，

7、要求任何兩排的座位數(shù)都要占大多數(shù)，問(wèn)有多少種擺法？解 這個(gè)問(wèn)題相當(dāng)于把個(gè)完全相同的球分配到3個(gè)不同的盒子里，如果沒(méi)有附加限制，應(yīng)該有種方案。不符合題意的擺法的特征是有一排至少有個(gè)座位，這相當(dāng)于將個(gè)座位先放到3排中的某一排，再將剩下的個(gè)座位任意分到3排中，這種擺法共有種方案。本例中，如果將座位總數(shù)改為2n，如上，沒(méi)有附加限制條件的擺法有種。不符合題意的擺法的特征是某一排最少有n個(gè)座位的擺法有：（2.7.2）種。但這3種方案中都有兩排的座位不少于n，所以在（2.7.2）的計(jì)數(shù)中，這3種方案中的每一個(gè)都在相應(yīng)的兩排中各計(jì)算了一次。所以，不合題意的擺法有：種，符合題意的擺法有：種。例4 把4個(gè)相同的桔子和6個(gè)不同的蘋(píng)果放到5個(gè)不同的盒子里，問(wèn)每個(gè)盒子里有2個(gè)水果的概率有多大？解 把4個(gè)相同的桔子放入5個(gè)不同的盒子里有種方法，把6個(gè)不同的蘋(píng)果放入5個(gè)不同的盒子里有種方法，總共有種分配方法。每個(gè)盒子里有2個(gè)水果，有如下幾種情況：（i）（蘋(píng)蘋(píng)）（蘋(píng)蘋(píng)）（蘋(píng)蘋(píng)）（桔桔）（桔桔）先從5個(gè)不同的盒子中選出2個(gè)放桔子，因?yàn)榻圩邮窍嗤模灰?jiǎn)單地一個(gè)盒子里放2個(gè)即可。剩下的3個(gè)不同的盒子放6個(gè)不同的蘋(píng)果。此類(lèi)放法共有種。（ii）（蘋(píng)蘋(píng)）（蘋(píng)蘋(píng)）（桔桔）（蘋(píng)桔）（蘋(píng)桔）先從5個(gè)不同的盒子里選出1個(gè)放2個(gè)桔子，再?gòu)氖Ｏ碌?個(gè)不同的