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

1、-1 -排列組合中的分組分配問題分組分配問題是排列組合教學(xué)中的一個(gè)重點(diǎn)和難點(diǎn)。某些排列組合問題看似非分配問題，實(shí)際上可運(yùn)用分配問題的方法來解決。一、提出分組與分配問題，澄清模糊概念n個(gè)不同元素按照某些條件分配給k個(gè)不同得對(duì)象，稱為 分配問題，分定向分配和不定向分配兩種問題；將 n個(gè)不同元素按照某些條件分成k組，稱為分組問題分組問題有不平均分組、平均分組、 和部分平均分組三種情況。分組問題和分配問題是有區(qū)別的，前者組與組之間只要元素個(gè)數(shù)相同是不區(qū)分的；而后者即使2組元素個(gè)數(shù)相同，但因?qū)ο蟛煌匀皇强蓞^(qū)分的對(duì)于后者必須先分組后排列。二、基本的分組問題例1六本不同的書，分為三組，求在下列條件下各有

2、多少種不同的分配方法？（1）每組兩本.（2）組一本，一組二本，一組三本.（3）組四本，另外兩組各一本.分析：分組與順序無關(guān)，是組合問題。分組數(shù)是c2c2c2=9o（種），這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ù)一樣， 又與順序無關(guān)，所以這兩種分法是同一種分法。以上的分組方法實(shí)際上加入了組的順序，因2 2 2此還應(yīng)取消分組的順序，即除以組數(shù)的全排列數(shù)A3，所以分法是 C6C4C2 =15（種）。A 3先分組，方法是 c6 c2 c3，

3、那么還要不要除以 A3 ?我們發(fā)現(xiàn)，由于每組的書的本數(shù)是不一樣的，因此不會(huì)出現(xiàn)相同的分法，即共有c6c2c3=6o（種）分法。分組方法是c6c2c1=3o（種），那么其中有沒有重復(fù)的分法呢？我們發(fā)現(xiàn)，其中兩組的書的本數(shù)都是一本，因此這兩組有了順序，而與四本書的那一組，由于書的本數(shù)不一樣，411不可能重復(fù)。所以實(shí)際分法是C 6 C 2C1 =15（種）。A 2通過以上三個(gè)小題的分析，我們可以得出分組問題的一般方法。結(jié)論1:一般地，n個(gè)不同的元素分成 p組，各組內(nèi)元素?cái)?shù)目分別為m 1，m 2，,，m p，其中k組內(nèi)元素?cái)?shù)目相等，那么分組方法數(shù)是mgCn Cm2 n mm3n -m -m2mpmpk

4、Ak三、基本的分配的問題（一）定向分配問題例2六本不同的書，分給甲、乙、丙三人，求在下列條件下各有多少種不同的分配方法？（1）甲兩本、乙兩本、丙兩本 .（2）甲一本、乙兩本、丙三本 .（3）甲四本、乙一本、丙一本 .分析：由于分配給三人，每人分幾本是一定的，屬分配問題中的定向分配問題，由分布計(jì)數(shù)原理不難解出：分別有C 2 C 2C 2 =90（種），C16C2c3=6O（種），c 4C 2c 1=30（種）。（二 ）不定向分配問題例3六本不同的書，分給甲、乙、丙三人，求在下列條件下各有多少種不同的分配方法？（1）每人兩本.（2）一人一本、一人兩本、一人三本.（3）一人四本、一人一本、一人一本.

5、分析：此組題屬于分配中的不定向分配問題，是該類題中比較困難的問題。由于分配給三人，同一本書給不同的人是不同的分法，所以是排列問題。實(shí)際上可看作“分為三組，再2 2 2將這三組分給甲、乙、丙三人”，因此只要將分組方法數(shù)再乘以A3，即c6c3C2 A3 =90（#），A 3CeC2c3 a3=360（種）C 6C 2C1 a3=90（種）。A 2結(jié)論2. 一般地，如果把不同的元素分配給幾個(gè)不同對(duì)象，并且每個(gè)不同對(duì)象可接受的 元素個(gè)數(shù)沒有限制，那么實(shí)際上是先分組后排列的問題，即分組方案數(shù)乘以不同對(duì)象數(shù)的 全排列數(shù)。通過以上分析不難得出解不定向分配題的一般原則：先分組后排列。例4六本不同的書，分給甲、

6、乙、丙三人，每人至少一本，有多少種分法？分析：六本書和甲、乙、丙三人都有“歸宿”，即書要分完，人不能空手。因此，考慮先分組，后排列。先分組，六本書怎么分為三組呢？有三類分法（1）每組兩本（2）分別為一本、二本、三本兩組各一本，另一組四本。所以根據(jù)加法原理，分組法是C 2C 2C 2C 4C 1C 16 4 2 + c6c2c3+ C 6 ； 1 =90（種）。再考慮排列，即再乘以 A3。所以一共有 540種不A 3A 2同的分法。四、分配問題的變形問題例5四個(gè)不同的小球放入編號(hào)為1 , 2, 3, 4的四個(gè)盒子中，恰有一個(gè)空盒的放法有多少種？分析：恰有一個(gè)空盒，則另外三個(gè)盒子中小球數(shù)分別為1

7、, 1, 2。實(shí)際上可轉(zhuǎn)化為先將1 1 2四個(gè)不同的小球分為三組，兩組各1個(gè)，另一組2個(gè)，分組方法有 C 4C 2 （種），然后將這A 2三組（即三個(gè)不同元素）分配給四個(gè)小盒（不同對(duì)象）中的3個(gè)的排列問題，即共有1 1 2C 4C 2C 2 A3 =144（種）。A 2例6有甲、乙、丙三項(xiàng)任務(wù)，甲需2人承擔(dān)，乙、丙各需 1人承擔(dān)，從10人中選派4人承擔(dān)這三項(xiàng)任務(wù)，不同的選法有多少種？分析：先考慮分組，即10人中選4人分為三組，其中兩組各一人，另一組二人，共1 1 2有c10C;C 8 （種）分法。再考慮排列，甲任務(wù)需2人承擔(dān)，因此2人的那個(gè)組只能承擔(dān)甲任A 2務(wù)，而一個(gè)人的兩組既可承擔(dān)乙任務(wù)又

8、可承擔(dān)丙任務(wù)，所以共有1 1 2C 10 C 9C 8A2A2 =2520(種)-4 -# -的問題。先考慮分組，集合A中4個(gè)元素分為三組，各組的元素?cái)?shù)目分別為1、1、2,則共1 1 2 有C 4C 3C2 (種)分組方法。A 2再考慮分配,即排列,再乘以A3，所以共有c 3c 2A2A3=36(個(gè))不同的選法。例7設(shè)集合A=1, 2，3, 4，B=6, 7, 8，A為定義域，B為值域，則從集合 A到集合B的不同的函數(shù)有多少個(gè)？分析：由于集合A為定義域，B為值域，即集合 A、B中的每個(gè)元素都有"歸宿”，而集合B的每個(gè)元素接受集合A中對(duì)應(yīng)的元素的數(shù)目不限，所以此問題實(shí)際上還是分組后分配-# -不同的函數(shù)?？傊?，掌握上述兩個(gè)結(jié)論，就能順利解決任何分配問題。而且，學(xué)會(huì)了分配