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

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

2、下各有多少種不同的分配方法？(1) 每組兩本.(2) 一組一本，一組二本，一組三本 .(3) 一組四本，另外兩組各一本.分析：(1)分組與順序無關，是組合問題。分組數是C2C2C2=90(種)，這90種分組實際上重復了 6次。我們不妨把六本不同的書寫上1、2、3、4、5、6六個號碼，考察以下兩種分法：(1, 2)(3 , 4)(5 , 6)與(3, 4)(1, 2)(5, 6),由于書是均勻分組的，三組的本數一樣， 又與順序無關，所以這兩種分法是同一種分法。以上的分組方法實際上加入了組的順序，因222此還應取消分組的順序，即除以組數的全排列數a3,所以分法是 C6C4C2 =15(種)。A 3

3、先分組，方法是 c6c2c3,那么還要不要除以 A3?我們發(fā)現，由于每組的書的本數是不一樣的，因此不會出現相同的分法，即共有c6c2C3=60(種)分法。(3)分組方法是C4c2c1=30(種),那么其中有沒有重復的分法呢？我們發(fā)現，其中兩組的書的本數都是一本，因此這兩組有了順序，而與四本書的那一組，由于書的本數不一樣，411不可能重復。所以實際分法是C 6 C 2C1 =15(種)。A 2通過以上三個小題的分析，我們可以得出分組問題的一般方法。結論1:一般地，n個不同的元素分成 p組，各組內元素數目分別為m 1 , m 2 ,m2 n -m1噸Cn -m -m2m p，其中k組內元素數目相等

4、，那么分組方法數是 pmpmpkAk三、基本的分配的問題（一）定向分配問題例2六本不同的書，分給甲、乙、丙三人，求在下列條件下各有多少種不同的分配方 法？（1）甲兩本、乙兩本、丙兩本 .（2）甲一本、乙兩本、丙三本 .（3）甲四本、乙一本、丙一本 .分析：由于分配給三人，每人分幾本是一定的，屬分配問題中的定向分配問題，由分布計數原理不難解出：分別有 C 6 C 4c 2=90（種），C16C2C3=60（種）,C 4C 2c 1 =30（種）。O 4 26 5 /36 2 I（二）不定向分配問題例3六本不同的書，分給甲、乙、丙三人，求在下列條件下各有多少種不同的分配方法？（1）每人兩本.（2）

5、一人一本、一人兩本、一人三本.（3）一人四本、一人一本、一人一本.分析：此組題屬于分配中的不定向分配問題，是該類題中比較困難的問題。由于分配給三人，同一本書給不同的人是不同的分法，所以是排列問題。實際上可看作“分為三組，再 將這三組分給甲、乙、丙三人”，因此只要將分組方法數再乘以 a3，即 C 2C 3C * a3=90（種）,A 3411 cC16C2C3 A3=360（種）C C2C a3=90（種）。A 2結論2. 一般地，如果把不同的元素分配給幾個不同對象，并且每個不同對象可接受的 元素個數沒有限制，那么實際上是先分組后排列的問題，即分組方案數乘以不同對象數的 全排列數。通過以上分析不

6、難得出解不定向分配題的一般原則：先分組后排列。例4六本不同的書，分給甲、乙、丙三人，每人至少一本，有多少種分法？分析：六本書和甲、乙、丙三人都有“歸宿”，即書要分完，人不能空手。因此，考慮先分組，后排列。先分組，六本書怎么分為三組呢？有三類分法（1）每組兩本（2）分別為一本、二本、三本兩組各一本，另一組四本。所以根據加法原理，分組法是2224116 32 + c6c2C3+°62 1 =90（種）。再考慮排列，即再乘以 a3。所以一共有540種不同的分法。四、分配問題的變形問題例5四個不同的小球放入編號為1 , 2, 3, 4的四個盒子中，恰有一個空盒的放法有多少種？分析：恰有一個空

7、盒，則另外三個盒子中小球數分別為1, 1, 2。實際上可轉化為先將四個不同的小球分為三組，兩組各1個，另一組2個，分組方法有 C4C 3C 2 （種），然后將這A 2三組（即三個不同元素）分配給四個小盒（不同對象）中的3個的排列問題，即共有112C 4C 2C2A4=144（種）。A 2例6有甲、乙、丙三項任務，甲需2人承擔，乙、丙各需 1人承擔，從10人中選派4人承擔這三項任務，不同的選法有多少種？分析：先考慮分組，即10人中選4人分為三組，其中兩組各一人，另一組二人，共112有C10C;C8 （種）分法。再考慮排列，甲任務需 2人承擔，因此2人的那個組只能承擔甲任A 2112務，而一個人的

8、兩組既可承擔乙任務又可承擔丙任務，所以共有C10C29C 8 A2 =2520(種)A 2不同的選法。例7設集合A=1, 2, 3, 4, B=6,乙8, A為定義域，B為值域，則從集合 A到集合 B的不同的函數有多少個？分析：由于集合 A為定義域，B為值域，即集合 A、B中的每個元素都有"歸宿”，而集 合B的每個元素接受集合 A中對應的元素的數目不限，所以此問題實際上還是分組后分配 的問題。先考慮分組，集合 A中4個元素分為三組，各組的元素數目分別為1、1、2,則共112112有C 4C 3C 2 （種）分組方法。再考慮分配，即排列，再乘以a3,所以共有C 4C 2C 2 a3=36（個）A 2A 2不同的函數?？傊莆丈鲜鰞蓚€結論，就能順利解決任何分配