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

精心整理擺列組合中的分組分派問題分組分派問題是擺列組合教課中的一個(gè)要點(diǎn)和難點(diǎn)。某些擺列組合問題看似非分派問題，實(shí)質(zhì)上可運(yùn)用分派問題的方法來解決。一、提出分組與分派問題，澄清模糊觀點(diǎn)n個(gè)不同元素依據(jù)某些條件分派給k個(gè)不同得對象，稱為分派問題，分定向分派和不定向分派兩種問題；將n個(gè)不同元素依據(jù)某些條件分紅k組，稱為分組問題.分組問題有不均勻分組、均勻分組、和部分均勻分組三種情況。分組問題和分派問題是有區(qū)其余，前者組與組之間只需元素個(gè)數(shù)同樣是不劃分的；爾后者即便2組元素個(gè)數(shù)同樣，但因?qū)ο蟛煌耘f是可劃分的.關(guān)于后者一定先分組后擺列。二、基本的分組問題例1六本不同的書，分為三組，求在以下條件下各有多少種不同的分派方法？(1)每組兩本.(2)一組一本，一組二本，一組三本.(3)一組四本，此外兩組各一本.剖析：(1)分組與次序沒關(guān)，是組合問題。分組數(shù)是222=90(種)，這90種分組實(shí)質(zhì)上重復(fù)C6C4C2了6次。我們不如把六本不同的書寫上1、2、3、4、5、6六個(gè)號(hào)碼，觀察以下兩種分法：(1，2)(3，4)(5，6)與(3，4)(1，2)(5，6)，因?yàn)闀蔷鶆蚍纸M的，三組的本數(shù)同樣，又與次序沒關(guān)，所以這兩種分法是同一種分法。以上的分組方法實(shí)質(zhì)上加入了組的次序，所以還應(yīng)撤消分組的次序，即除以2223C6C4C2=15(種)。組數(shù)的全擺列數(shù)A3，所以分法是3A31233(2)先分組，方法是C6C5C3，那么還要不要除以A3？我們發(fā)現(xiàn)，因?yàn)槊拷M的書的本數(shù)是不同樣的，所以不會(huì)出現(xiàn)同樣的分法，即共有123C6C5C3=60(種)分法。411此中兩組的書的本(3)分組方法是C6C2C1=30(種)，那么此中有沒有重復(fù)的分法呢？我們發(fā)現(xiàn)，數(shù)都是一本，所以這兩組有了次序，而與四本書的那一組，因?yàn)闀谋緮?shù)不同樣，不行能重復(fù)。所411以實(shí)質(zhì)分法是C6C2C1=15(種)。2A2經(jīng)過以上三個(gè)小題的剖析，我們能夠得出分組問題的一般方法。結(jié)論1：一般地，n個(gè)不同的元素分紅p組，各組內(nèi)元素?cái)?shù)量分別為m1，m2，，mp，其mm2mmpCmpCn1Cnm1Cnm1m2中k組內(nèi)元素?cái)?shù)量相等，那么分組方法數(shù)是k。Ak精心整理精心整理三、基本的分派的問題(一)定向分派問題例2六本不同的書，分給甲、乙、丙三人，求在以下條件下各有多少種不同的分派方法？甲兩本、乙兩本、丙兩本.甲一本、乙兩本、丙三本.甲四本、乙一本、丙一本.剖析：因?yàn)榉峙山o三人，每人分幾本是必定的,屬分派問題中的定向分派問題，由散布計(jì)數(shù)原理不難解出：分別有222123411=30(種)。C6C4C2=90(種)，C6C5C3=60(種)，C6C2C1(二)不定向分派問題例3六本不同的書，分給甲、乙、丙三人，求在以下條件下各有多少種不同的分派方法？每人兩本.(2)一人一本、一人兩本、一人三本.(3)一人四本、一人一本、一人一本.剖析：此組題屬于分派中的不定向分派問題，是該類題中比較困難的問題。因?yàn)榉峙山o三人，同一本書給不同的人是不同的分法，所以是擺列問題。實(shí)質(zhì)上可看作“分為三組，再將這三組分給2223，即C6C4C23=90(種)，甲、乙、丙三人”，所以只需將分組方法數(shù)再乘以A33A3A34111233=360(種)C6C2C13=90(種)。C6C5C3A32A3A2結(jié)論2.一般地，假如把不同的元素分派給幾個(gè)不同對象，并且每個(gè)不同對象可接受的元素個(gè)數(shù)沒有限制，那么其實(shí)是先分組后擺列的問題，即分組方案數(shù)乘以不同對象數(shù)的全擺列數(shù)。經(jīng)過以上剖析不難得出解不定向分派題的一般原則：先分組后擺列。例4六本不同的書，分給甲、乙、丙三人，每人起碼一本，有多少種分法？剖析：六本書和甲、乙、丙三人都有“歸宿”，即書要分完，人不可以空手。所以，考慮先分組，后擺列。先分組，六本書怎么分為三組呢？有三類分法(1)每組兩本(2)分別為一本、二本、三本(3)22212341121兩組各一本，另一組四本。所以依據(jù)加法原理，分組法是64+C6C5C3+62=90(種)。再32A3A2考慮擺列，即再乘以A33。所以一共有540種不同的分法。四、分派問題的變形問題例5四個(gè)不同的小球放入編號(hào)為1，2，3，4的四個(gè)盒子中，恰有一個(gè)空盒的放法有多少種？剖析：恰有一個(gè)空盒，則此外三個(gè)盒子中小球數(shù)分別為1，1，2。實(shí)質(zhì)上可轉(zhuǎn)變?yōu)橄葘⑺膫€(gè)不1122同的小球分為三組，兩組各1個(gè)，另一組2個(gè)，分組方法有43(種)，而后將這三組(即三個(gè)不2A2精心整理精心整理112同元素)分派給四個(gè)小盒(不同對象)中的3個(gè)的擺列問題，即共有C4C3C232A4=144(種)。A2例6有甲、乙、丙三項(xiàng)任務(wù)，甲需2人擔(dān)當(dāng)，乙、丙各需1人擔(dān)當(dāng)，從10人中選派4人擔(dān)當(dāng)這三項(xiàng)任務(wù)，不同的選法有多少種？1121098(種)剖析：先考慮分組，即10人中選4人分為三組，此中兩組各一人，另一組二人，共有CC2CA2分法。再考慮擺列，甲任務(wù)需2人擔(dān)當(dāng)，所以2人的那個(gè)組只好擔(dān)當(dāng)甲任務(wù)，而一個(gè)人的兩組既112可擔(dān)當(dāng)乙任務(wù)又可擔(dān)當(dāng)丙任務(wù)，所以共有10982CC2CA2=2520(種)不同的選法。A2例7設(shè)會(huì)合A={1，2，3，4}，B={6，7，8}，A為定義域，B為值域，則從會(huì)合A到會(huì)合B的不同的函數(shù)有多少個(gè)？剖析：因?yàn)闀?huì)合A為定義域，B為值域，即會(huì)合A、B中的每個(gè)元素都有“歸宿”，而會(huì)合B的每個(gè)元素接受會(huì)合A中對應(yīng)的元素的數(shù)量不限，所以此問題實(shí)質(zhì)上仍是分組后分派的問題。先112考慮分組，會(huì)合A中4個(gè)元素分為三組，各組的元素?cái)?shù)量分別為1、1、2，則共有C4C3C2(種)分2A2112組方法。再考慮分派，即擺列，再乘以3，所以共有C4C3C23=36(個(gè))不同的函數(shù)。A32A3A2總之，掌握上述兩個(gè)結(jié)論，就能順利解決任何分派問題。并