資源描述：
《排列組合中分組(分堆)與分配問題》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、太奇MBA數(shù)學助教李瑞玲一．分組（分堆）與分配問題將n個不同元素按照某些條件分配給k個不同的對象，稱為分配問題，又分為定向分配和不定向分配兩種問題。將n個不同元素按照某些條件分成k組，稱為分組問題。分組問題有不平均分組，平均分組，部分平均分組三情況。分組問題和分配問題是有區(qū)別的，前者組與組之間只要元素個數(shù)相同是不區(qū)分的，而后者即使兩組的元素個數(shù)相同，但因所要分配的對象不同，仍然是可區(qū)分的。對于后者必須先分組后排列。一．基本的分組問題例1.六本不同的書，分為三組，求在下列條件下各有多少種不同的分配方法？（1）每組兩本（均分三組）（平均分組問題）（2）一組一本，一組
2、兩本，一組三本（不平均分組問題）（3）一組四本，另外兩組各一本（部分平均分組問題）分析：（1）分組和順序無關(guān)，是組合問題。分組數(shù)為222CCC=90,642而這90種分組方法實際上重復了6次。現(xiàn)把六本不同的書標上1,2,3,4,5,6六個號碼，先看一下這種情況：（1,2）（3,4）（5,6）（1,2）（5,6)(3,4)(3,4)(1,2）（5,6）（3,4）（5,6）（1,2）（5,6）（1,2）（3,4）（5,6）（3,4）（1,2）由于書是均勻分組的，三組的本數(shù)都一樣，又與順序無關(guān)，所以這種情況下這六種分法是同一種分法，于是可知重復了6次。以上的分組實際上
3、加入了組的順序，同理其他情況也是如此，因此還應取消分組222的順序，即除以3C6C4C290P,于是最后知分法為==15.33P63(2)先分組，分組方法是1233CCC=60，那么還要不要除以P???（很6533關(guān)鍵的問題）由于每組的書的本數(shù)是不一樣的，因此不會出現(xiàn)相同的分法，即共有123CCC=60。653（3）先分組，分組方法是411CCC=30，這其中有沒有重復的分法???(需621要好好考慮）現(xiàn)還把六本不同的書標上1,2,3,4,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é)果為411CCC30621==15.2P22通過以上三個小題的分析，可以得出分組問題的一般結(jié)論如下：一般地，將n個不同的元素分成p組，各組內(nèi)元素個數(shù)分別為m,m,?,m，其中k組內(nèi)元素個數(shù)相等，那
5、么分組方法數(shù)為12pCm1Cm2?Cmi?Cmpnn?m1n?(m1+m2+?+mi?1)mpk，即選完元素后要除以元素相同Pk的總組數(shù)的全排列！三．基本的分配問題1.定向分配問題例2六本不同的書，分給甲乙丙三人，求在下列條件下各有多少種不同的分法？（1）甲兩本，乙兩本，丙兩本（2）甲一本，乙兩本，丙三本（3）甲四本，乙一本，丙一本分析：由于分配給三人，每人分幾本是一定的，屬于分配問題中的定向分配問題。由分步計數(shù)原理得（1）222123411CCC=90(2)CCC=60(3)CCC=306426536212.不定向分配問題例3.六本不同的書，分給甲乙丙三人，求
6、在下列條件下各有多少種不同的分法？（1）每人兩本（2）一人一本，一人兩本，一人三本（3）一人四本，一人一本，一人一本分析：此題屬于分配中的不定向分配問題。由于分配給三人，同一本書給不同的人是不同的分法，所以是排列問題。實際上可看作是“六本不同的書分為三組，再將這三組分給甲乙丙三人”，因此只要將元素的分組的方法數(shù)再乘以所分配對象的全排列即可！222所以有（1）C6C4C23×P=9033P3（2）1233CCC×P=3606533411(3)C6C2C13×P=9023P2結(jié)論：一般地，如果把n個不同的元素分配給k個不同的對象，并且每個不同的對象可接受的元素個數(shù)沒
7、有限制，那么實際上是先分組后排列的問題，結(jié)果為分組方案數(shù)乘以不同對象數(shù)的全排列。解不定向分配題的一般原則是：先分組后排列！數(shù)學講義上第95頁排列組合本章作業(yè)第4題屬于不定向分配問題（需要先分組，再分配，其中分組為不平均分組）結(jié)果為1233CCC×P=360,故選B。6533第5題屬于定向分配問題，所以為123CCC=60,故選D。653第6題屬于不定向分配問題（需要先分組，再分配，其中分組為平均222分組）結(jié)果為C6C4C23×P=90，故選C。33P3第28題也屬于不定向分配問題，同第6題，結(jié)果為444C12C8C43444×P=CCC,故選A。331284P
8、3元素種類（1）元素相同
