排列組合中的分組與分配問(wèn)題

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

2、與順序無(wú)關(guān)，是組合問(wèn)題。分組數(shù)是C2C2C2=90(種)，這90種分組實(shí)際上重復(fù)了 6次。我們不妨把六本不同的書寫上1、2、3、4、5、6六個(gè)號(hào)碼，考察以下兩種分法:(1, 2) (3, 4) (5,6)與(3, 4) (1,2) (5,6),由于書是均勻分組的，三組的本數(shù)一樣， 又與順序無(wú)關(guān)，所以這兩種分法是同一種分法.以上的分組方法實(shí)際上加入了組的順序，因222此還應(yīng)取消分組的順序，即除以組數(shù)的全排列數(shù)a3,所以分法是 C6C 3c2=15 (種).(2)先A3分組,方法是C6C2c3,那么還要不要除以 a3?我們發(fā)現(xiàn)，由于每組的書的本數(shù)是不一樣的，因此不會(huì)出現(xiàn)相同的分法，即共有c6c5c

3、3=60 (種)分法。(3)分組方法是 c4c2c1 =30(種)，那么其中有沒有重復(fù)的分法呢？我們發(fā)現(xiàn)，其中兩組的書的本數(shù)都是一本，因此這兩組有了順序， 而與四本書的那一組， 由于書的本數(shù)不一411樣，不可能重復(fù)。所以實(shí)際分法是C6C2C1=15（種）。2A2結(jié)論1: 一般地,n個(gè)不同的元素分成p組,各組內(nèi)元素?cái)?shù)目分別為m1 ,m2，,m p ,m1m2 m3其中k組內(nèi)元素?cái)?shù)目相等，那么分組方法數(shù)是C n C n m1c n m1 m2Ak三、基本的分配的問(wèn)題(一)定向分配問(wèn)題例2六本不同的書，分給甲、乙、丙三人，求在下列條件下各有多少種不同的分配方法(1)甲兩本、乙兩本、丙兩本 .(2)甲

4、一本、乙兩本、丙三本。(3)甲四本、乙一本、丙一本 .分析：由于分配給三人，每人分幾本是一定的，屬分配問(wèn)題中的定向分配問(wèn)題，由分布計(jì)數(shù)原理不難解出：分別有C 6c 4c2=90 (種),C16C2c3=60 (種)，C4c2c：=30 (種).(二)不定向分配問(wèn)題例3六本不同的書，分給甲、乙、丙三人，求在下列條件下各有多少種不同的分配方法？(1)每人兩本。(2) 一人一本、一人兩本、一人三本。(3) 一人四本、一人一本、一人一本。分析：此組題屬于分配中的不定向分配問(wèn)題，是該類題中比較困難的問(wèn)題。由于分配給a3,即 c6c3c2 a3=90（種）,3三人，同一本書給不同的人是不同的分法，所以是排列問(wèn)題。實(shí)際上可看作“分為三組，再 將這三組分給甲、乙、丙三人”，因此只要將分組方法數(shù)再乘以A2c6c2C3 a3=360 （種）C6C2c1 a3=90 （種）。結(jié)論2。一般地，如果把不同的元素分配給幾個(gè)不同對(duì)象，并且每個(gè)不同對(duì)象可接受的元素個(gè)數(shù)沒有