排列組合中的分組與分配問題

1、精品文檔排列組合中的分組分配問題一、提出分組與分配問題，澄清模糊概念n 個不同元素按照某些條件分配給k 個不同得對象，稱為分配問題 ，分定向分配和不定向分配兩種問題；將n 個不同元素按照某些條件分成k 組，稱為分組問題. 分組問題有不平均分組、平均分組、和部分平均分組三種情況。分組問題和分配問題是有區(qū)別的，前者組與組之間只要元素個數(shù)相同是不區(qū)分的；而后者即使2 組元素個數(shù)相同， 但因對象不同， 仍然是可區(qū)分的 . 對于后者必須先分組后排列。二、基本的分組問題例 1 六本不同的書，分為三組，求在下列條件下各有多少種不同的分配方法？(1) 每組兩本 .(2) 一組一本，一組二本，一組三本.(3)

2、一組四本，另外兩組各一本 .分析： (1)分組與順序無關，是組合問題。分組數(shù)是=90( 種 )，這90 種分組實際上重復了6 次。我們不妨把六本不同的書寫上1、 2、 3、 4、5、 6 六個號碼，考察以下兩種分法： (1 ，2)(3，4)(5 ，6) 與 (3 ，4)(1 ，2)(5 ，6) ，由于書是均勻分組的，三組的本數(shù)一樣， 又與順序無關， 所以這兩種分法是同一種分法。以上的分組方法實際上加入了組的順3222CC C2序，因此還應取消分組的順序，即除以組數(shù)的全排列數(shù)A3 ，所以分法是64=15(種)。3A3(2) 先分組， 方法是，那么還要不要除以A 33 ？我們發(fā)現(xiàn)， 由于每組的書的

3、本數(shù)是不一樣的，因此不會出現(xiàn)相同的分法，即共有=60( 種)分法。(3) 分組方法是=30( 種 )，那么其中有沒有重復的分法呢？我們發(fā)現(xiàn)，其中兩組的書的本數(shù)都是一本，因此這兩組有了順序，而與四本書的那一組，由于書的本數(shù)不一樣，411不可能重復。所以實際分法是C 6C 2C1=15( 種) 。2A 2結論 1： 一般地， n 個不同的元素分成p 組，各組內元素數(shù)目分別為m ， m ， ，mmmm pC n1 C n2m1C n 3m1 m2C m pm ，其中 k 組內元素數(shù)目相等，那么分組方法數(shù)是k。Ak三、基本的分配的問題( 一 ) 定向分配問題例 2 六本不同的書，分給甲、乙、丙三人，求

4、在下列條件下各有多少種不同的分配方。1歡迎下載精品文檔法？(1) 甲兩本、乙兩本、丙兩本 .(2) 甲一本、乙兩本、丙三本 .(3) 甲四本、乙一本、丙一本 .分析：由于分配給三人， 每人分幾本是一定的, 屬分配問題中的定向分配問題，由分布計數(shù)原理不難解出：分別有222=90(種 ) ，=60( 種) ，411=30(種 ) 。C6C4C2C 6C 2C1( 二 ) 不定向分配問題例 3 六本不同的書，分給甲、乙、丙三人，求在下列條件下各有多少種不同的分配方法？(1) 每人兩本 .(2) 一人一本、一人兩本、一人三本.(3) 一人四本、一人一本、一人一本.分析：此組題屬于分配中的不定向分配問題， 是該類題中比較困難的問題。 由于分配給三人，同一本書給不同的人是不同的分法，所以是排列問題。實際上可看作“分為三組，再22C2A33642種 ) ，將這三組分給甲、 乙、丙三人”，因此只要將分組方法數(shù)再乘以，即CC3A33 =90(A34C11A362133=360( 種 ) C2CA3=90( 種) 。A2結論 2.一般地， 如果把不同的元素分配給幾個不同對象，并且每個不同對象可接受的元素個數(shù)沒有限制，那么實際上是先分組后排列的問題，即分組方案數(shù)乘以不同對象數(shù)的全排列數(shù)。通過以上分析不難得出解不定向分配題的一般原