排列組合中分組(分堆)與分配問題

1、太奇MBA數(shù)學助教李瑞玲一分組（分堆）與分配問題將 n 個不同元素按照某些條件分配給 k 個不同的對象，稱為分配問 題，又分為定向分配和不定向分配兩種問題。將n個不同元素按照某些條件分成k組，稱為分組問題。分組問題有不平均分組，平均分組，部分平均分組三情況。分組問題和分配問題是有區(qū)別的， 前者組與組之間只要元素個數(shù)相 同是不區(qū)分的， 而后者即使兩組的元素個數(shù)相同， 但因所要分配的對 象不同，仍然是可區(qū)分的。對于后者必須先分組后排列。 一基本的分組問題平均分組問題）不平均分組問題） 部分平均分組問題）例 1. 六本不同的書，分為三組，求在下列條件下各有多少種不同 的分配方法？1）每組兩本（均分三

2、組）2）一組一本，一組兩本，一組三本3）一組四本，另外兩組各一本分析：（1）分組和順序無關(guān)，是組合問題。分組數(shù)為 C62C42C22 = 90 ,而這 90種分組方法實際上重復了6 次?，F(xiàn)把六本不同的書標上1,2,3,4,5,6 六個號碼，先看一下這種情況：1,2 ）（3,4 ）（5,6 ）（3,4） （1,2 ）（5,6 ）5,6 ）（1,2 ）（3,4 ）1,2 ）（5,6） （3,4）（3,4 ）（5,6 ）（1,2 ）（5,6 ）（3,4 ）（1,2 ）由于書是均勻分組的，三組的本數(shù)都一樣，又與順序無關(guān)，所以這種情況下這六種分法是同一種分法，于是可知重復了 6次。以上的分組 實際上加入

3、了組的順序，同理其他情況也是如此，因此還應(yīng)取消分組 的順序，即除以P33,于是最后知分法為C6cp4c2=960=i5.先分組，分組方法是C；C；C3=6O，那么還要不要除以P；3? （很 關(guān)鍵的問題）由于每組的書的本數(shù)是不一樣的，因此不會出現(xiàn)相同的分法，即共有 c6c；c； = 60。（3）先分組，分組方法是C；c2g甲兩本，乙兩本，丙兩本 =30，這其中有沒有重復的分法 ?（需 要好好考慮）現(xiàn)還把六本不同的書標上1,234,5,6六個號碼，先看以下情況1）先取四本分一組，剩下的兩本，一本一組，情況如下（1,2,3,4）56（ 1,2,3,4）652）先取一本分一組，再取四本分一組，剩余的一

4、本為一組， 情 況如下5（ 1,2,3，4）66（ 1,2,3,4） 53）先取一本分一組，再取一本為一組，剩下的四本為一組， 情 況如下56（ 1,2,3,4）65（ 1,2,3,4）由此可知每一種分法重復了 2次，原因是其中兩組的的書的本 數(shù)都是一本，這兩組有了順序，需要把分組的順序取消掉，而四本的 那一組，由于書的本數(shù)不一樣，不可重復，故最后的結(jié)果為CQC； = 30 = 15P；2'通過以上三個小題的分析，可以得出分組問題的一般結(jié)論如下：一般地，將n個不同的元素分成p組，各組內(nèi)元素個數(shù)分別為耳,口2,?, mp，其中k組內(nèi)元素個數(shù)相等，那么分組方法數(shù)為C m1 C m2 ? C

5、 mi? C mpn n_mi ? n_ (mi +m2 +? +mi-1) mp(2) 人一本，一人兩本，一人三本(3) 人四本，一人一本，一人一本 分析：此題屬于分配中的不定向分配問題。由于分配給三人，同一本 書給不同的人是不同的分法，所以是排列問題。實際上可看作是“六本不同的書分為三組，再將這三組分給甲乙丙三人”，因此只要將元 素的分組的方法數(shù)再乘以所分配對象的全排列即可！所以有(1)P33XF33 = 90(2) C：c2c3 XF3甲四本，乙一本，丙一本分析：由于分配給三人，每人分幾本是一定的，屬于分配問題中的定 向分配問題。由分步計數(shù)原理得(1) C6* 1 2 3c2c|=90(

6、2) c6c；C；=60(3) C：c2c1 = 302. 不定向分配問題例3.六本不同的書，分給甲乙丙三人，求在下列條件下各有多少種 不同的分法？(1) 每人兩本 = 360(3) X3 = 90結(jié)論：一般地，如果把n個不同的元素分配給k個不同的對象，并且 每個不同的對象可接受的元素個數(shù)沒有限制，那么實際上是先分組后 排列的問題，結(jié)果為分組方案數(shù)乘以不同對象數(shù)的全排列。解不定向 分配題的一般原則是：先分組后排列！數(shù)學講義上第95頁排列組合本章作業(yè) 第4題 屬于不定向分配問題(需要先分組，再分配，其中分組為不 平均分組)結(jié)果為C6C2C； XP33 = 360,故選B。第5題屬于定向分配問題，

7、所以為C；C2C； = 6O,故選D。第6題屬于不定向分配問題(需要先分組，再分配，其中分組為平均 分組)結(jié)果為 CC程XP33 = 90，故選C。第28題也屬于不定向分配問題，同第6題，結(jié)果為C2評 XP33=G：C：C：,故選 A元素種類（1）元素相同（2）元素不同1分配對象相同 2）分配對象不同1）分配對象相同 2）分配對象不同分組（分堆）問題 隔板法解決分組（分堆）問題 可重復和不可重復此時要依據(jù)每組的數(shù)量來區(qū)別要依據(jù)每組的數(shù)量和元素特征來區(qū)別可重復：投信，人進房間問題 不可重復：組合，排列問題例：現(xiàn)有6個球，4個盒子，每個盒子至少一個球，在下列各種情況下各有多少 種放法？（1）球不同

8、，盒子不同（2）球不同，盒子相同（3）球相同，盒子不同（4）球相同，盒子相同解:（1）屬于組合，排列問題，需要先分組，再分配給不同的對象。分組有兩種分法:1）2 2 1 12）3 1 1 122113111?2 C2113111 ?則有 CeC4C2C1 +C6C3C2C1，最后結(jié)果為?CeC4C2C1 +C6C3C2C1?xp4.P2R3? P2P3 ?由于分配對象相同，沒有區(qū)別，所以實質(zhì)上為分組問題分組有兩種分法：1）2 2 1 12）3 1 1 1C ?c ?c 1C1 c 3c1 c 1C1則有g(shù)gG2cl + ggGcl，即為最后結(jié)果。P22戌（3）球相同，即元素相同，但分配對象不同，又要求每個盒子至少一個球，故為隔板問題，需用隔板法來解決，即 c；=1o種。（4