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

６個(gè)學(xué)生平均分成3組，有多少種分法？６個(gè)學(xué)生平均分到3個(gè)不同的班級(jí)，有多少種分法？頭痛了吧？分組分配問(wèn)題是排列組合教學(xué)中的一個(gè)重點(diǎn)和難點(diǎn)。某些排列組合問(wèn)題看似非分配問(wèn)題，實(shí)際上可運(yùn)用分配問(wèn)題的方法來(lái)解決。排列組合中的分組分配問(wèn)題６個(gè)學(xué)生平均分成3組，一提出分組與分配問(wèn)題，澄清模糊概念n個(gè)不同元素按照某些條件分配給k個(gè)不同得對(duì)象，稱(chēng)為分配問(wèn)題，分定向分配和不定向分配兩種問(wèn)題；將n個(gè)不同元素按照某些條件分成k組，稱(chēng)為分組問(wèn)題。分組問(wèn)題有不平均分組、平均分組、和部分平均分組三種情況。分組問(wèn)題和分配問(wèn)題是有區(qū)別的，前者組與組之間只要元素個(gè)數(shù)相同是不區(qū)分的；而后者即使2組元素個(gè)數(shù)相同，但因?qū)ο蟛煌匀皇强蓞^(qū)分的。對(duì)于后者必須先分組后排列。一提出分組與分配問(wèn)題，澄清模糊概念二基本的分組問(wèn)題例1六本不同的書(shū)，分為三組，求在下列條件下各有多少種不同的分配方法？(1)每組兩本（均分三堆）１５(2)一組一本，一組二本，一組三本６０(3)一組四本，另外兩組各一本１５二基本的分組問(wèn)題分析：(1)分組與順序無(wú)關(guān)，是組合問(wèn)題。分組數(shù)是Ｃ６２＊Ｃ４２＊Ｃ２２=90(種)這90種分組實(shí)際上重復(fù)了6次。我們不妨把六本不同的書(shū)標(biāo)上1、2、3、4、5、6六個(gè)號(hào)碼。考察以下兩種分法：(1，2)(3，4)(5，6)與(3，4)(1，2)(5，6)，由于書(shū)是均勻分組的，三組的本數(shù)一樣，又與順序無(wú)關(guān)，所以這兩種分法是同一種分法。以上的分組方法實(shí)際上加入了組的順序，因此還應(yīng)取消分組的順序，即除以組數(shù)的全排列數(shù)Ａ３３＝６，所以分法是９０／６=15(種)。(2)先分組，方法是Ｃ６１＊Ｃ５２＊Ｃ３３＝６０，那么還要不要除以Ａ３３？我們發(fā)現(xiàn)，由于每組的書(shū)的本數(shù)是不一樣的，因此不會(huì)出現(xiàn)相同的分法，即共有=60(種)分法。(3)分組方法是Ｃ６４＊Ｃ２１＊Ｃ１１=30(種)其中有沒(méi)有重復(fù)的分法？我們發(fā)現(xiàn)，其中兩組的書(shū)的本數(shù)都是一本，因此這兩組有了順序，而與四本書(shū)的那一組，由于書(shū)的本數(shù)不一樣，不可能重復(fù)。所以實(shí)際分法是Ｃ６４＊Ｃ２１＊Ｃ１１／Ａ２２=15(種)。分析：通過(guò)以上三個(gè)小題的分析，我們可以得出分組問(wèn)題的一般方法。結(jié)論1：一般地，n個(gè)不同的元素分成p組，各組內(nèi)元素?cái)?shù)目分別為m１，m２，…，mＰ，其中k組內(nèi)元素?cái)?shù)目相等，那么分組方法數(shù)是通過(guò)以上三個(gè)小題的分析，我們可以得出分組問(wèn)題的一般方法。三基本的分配的問(wèn)題１定向分配問(wèn)題例2六本不同的書(shū)，分給甲、乙、丙三人，求在下列條件下各有多少種不同的分配方法？(1)甲兩本、乙兩本、丙兩本.(2)甲一本、乙兩本、丙三本.(3)甲四本、乙一本、丙一本.分析：由于分配給三人，每人分幾本是一定的,屬分配問(wèn)題中的定向分配問(wèn)題，由分布計(jì)數(shù)原理不難解出：（１）Ｃ６２＊Ｃ４２＊Ｃ２２=90(種)（２）Ｃ６１＊Ｃ５２＊Ｃ３３=60(種)（３）Ｃ６４＊Ｃ２１＊Ｃ１１=30(種)。三基本的分配的問(wèn)題２不定向分配問(wèn)題例3六本不同的書(shū)，分給甲、乙、丙三人，求在下列條件下各有多少種不同的分配方法？(1)每人兩本(2)一人一本、一人兩本、一人三本(3)一人四本、一人一本、一人一本分析：此組題屬于分配中的不定向分配問(wèn)題，是該類(lèi)題中比較困難的問(wèn)題。由于分配給三人，同一本書(shū)給不同的人是不同的分法，所以是排列問(wèn)題。實(shí)際上可看作“分為三組，再將這三組分給甲、乙、丙三人”，因此只要將分組方法數(shù)再乘以Ａ３３＝６，即（１）１５＊６=90(種)（２）６０＊６=360(種)（３）１５＊６=90(種)。２不定向分配問(wèn)題結(jié)論2.一般地，如果把不同的元素分配給幾個(gè)不同對(duì)象，并且每個(gè)不同對(duì)象可接受的元素個(gè)數(shù)沒(méi)有限制，那么實(shí)際上是先分組后排列的問(wèn)題，即分組方案數(shù)乘以不同對(duì)象數(shù)的全排列數(shù)。解不定向分配題的一般原則：先分組后排列。結(jié)論2.一般地，如果把不同的元素分配給幾個(gè)不同對(duì)象，并且每例4六本不同的書(shū)，分給甲、乙、丙三人，每人至少一本，有多少種分法？分析：六本書(shū)和甲、乙、丙三人都有“歸宿”，即書(shū)要分完，人不能空手。因此，考慮先分組，后排列。先分組，六本書(shū)怎么分為三組呢？有三類(lèi)分法(1)每組兩本(2)分別為一本、二本、三本(3)兩組各一本，另一組四本。所以根據(jù)加法原理，分組法是

+

+

=90(種)。再考慮排列，即再乘以

。所以一共有540種不同的分法。例4六本不同的書(shū)，分給甲、乙、丙三人，每人至少一本，有多少例6有甲、乙、丙三項(xiàng)任務(wù)，甲需2人承擔(dān)，乙、丙各需1人承擔(dān)，從10人中選派4人承擔(dān)這三項(xiàng)任務(wù)，不同的選法有多少種？分析：先考慮分組，即10人中選4人分為三組，其中兩組各一人，另一組二人，共有Ｃ１０４＊Ｃ４２(種)分法。再考慮排列，甲任務(wù)需2人承擔(dān)，因此2人的那個(gè)組只能承擔(dān)甲任務(wù)，而一個(gè)人的兩組既可承擔(dān)乙任務(wù)又可承擔(dān)丙任務(wù)，全排。共Ｃ１０４＊Ｃ４２＊Ａ２２=2520(種)不同的選法。例6有甲、乙、丙三項(xiàng)任務(wù)，甲需2人承擔(dān)，乙、丙各需1人承擔(dān)四分配問(wèn)題的變形問(wèn)題例5四個(gè)不同的小球放入編號(hào)為1，2，3，4的四個(gè)盒子中，恰有一個(gè)空盒的放法有多少種？分析：恰有一個(gè)空盒，則另外三個(gè)盒子中小球數(shù)分別為1，1，2。實(shí)際上可轉(zhuǎn)化為先將四個(gè)不同的小球分為三組，兩組各1個(gè)，另一組2個(gè)，分組方法有(種)，然后將這三組(即三個(gè)不同元素)分配給四個(gè)小盒(不同對(duì)象)中的3個(gè)的排列問(wèn)題，即共有=144(種)。四分配問(wèn)題的變形問(wèn)題例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ù)目不限，所以此問(wèn)題實(shí)際上還是分組后分配的問(wèn)題。先考慮分組，集合A中4個(gè)元素分為三組，各組的元素?cái)?shù)目分別為1、1、2，則共有(種)分組方法。再考慮分配，即排列，再乘以，所以共有=36(個(gè))不同的函數(shù)。例7設(shè)集合A={1，2，3，4}，B={6，7，8}，A為附一編號(hào)分組：1相同元素編號(hào)分組“編號(hào)分組”的意思是：即使分出來(lái)兩個(gè)或多個(gè)組中，元素的個(gè)數(shù)相同，仍然看成不同的組例題：10個(gè)相同的小球，放入5個(gè)不同的盒子里面，每個(gè)盒子至少要放一個(gè)球。問(wèn)有幾種放法？方法（隔板法）5個(gè)盒子，設(shè)置4個(gè)隔板，插入9個(gè)空中。C94

附2不同元素編號(hào)分組分成兩種情況：(i)非均勻編號(hào)分組（每組元素個(gè)數(shù)不同）例題：10個(gè)人分成三組，各組人數(shù)分別為2、3、5，去參加不同（在這里體現(xiàn)“編號(hào)分組”）勞動(dòng)，問(wèn)有幾種安排方法？方法：分步選人，分別適合各組人數(shù)，然后要乘以組數(shù)的全排列。C102×C83×C55×A33(ii)均勻編號(hào)分組（包括部分均勻、全部均勻）2不同元素編號(hào)分組例題：10個(gè)人分成三組，各組人數(shù)分別為2、2、6，去參加不同勞動(dòng)問(wèn)有幾種安排方法？方法：分步選人，分別適合各組人數(shù)。但是，由于有兩個(gè)或兩個(gè)以上的組人數(shù)相同，而選人時(shí)又是分步選人的（即有順序在里面），所以必然會(huì)造成重復(fù)。比如：甲乙、丙丁和丙丁、甲乙是一種情況，我們卻多算了。要除以元素相同的幾個(gè)組的組數(shù)的全排列選人完之后要放進(jìn)編好號(hào)碼的組里面，所以乘以總組數(shù)的全排列。C102×C82×C66÷A22×A33例題：10個(gè)人分成三組，各組人數(shù)分別為2、2、6，去參加不同二不編號(hào)分組：與編號(hào)分組不同的是，在不編號(hào)分組中，各個(gè)組元素的個(gè)數(shù)成為了區(qū)別不同組的唯一標(biāo)志，換言之，只要有兩個(gè)或者多個(gè)組有相同個(gè)數(shù)的元素，它們就被視為相同的組。在這里，由于組已經(jīng)沒(méi)有編號(hào)了，如果要放進(jìn)組里面的元素再不可區(qū)分，那問(wèn)題就變得沒(méi)什么意義，而且很簡(jiǎn)單了。比如：三個(gè)相同的球，放入兩個(gè)相同的盒子里面，只有一種放法，那就是其中一個(gè)盒子放一個(gè)球，另外那個(gè)盒子放剩下的那兩個(gè)球。所以用列舉法就可以了。在這里主要討論不同元素的情況。二不編號(hào)分組：1，不同元素，不編號(hào)不均勻分組。例題：10個(gè)人分成三組，各組人數(shù)分別為2、3、5，去參加相同（在這里體現(xiàn)“不編號(hào)分組”）勞動(dòng)，問(wèn)有幾種安排方法？方法：和“不同元素，編號(hào)不均勻分組”相比，不必乘以組數(shù)的全排列，因?yàn)槿齻€(gè)組參加的是相同的勞動(dòng)（這里“相同”的言下之意是：勞動(dòng)內(nèi)容相同，又是同時(shí)去的，如果不同時(shí)，還要當(dāng)作編號(hào)分組）C102×C83×C551，不同元素，不編號(hào)不均勻分組。不同元素不編號(hào)均勻分組（部分均勻、全部均勻）例題：10個(gè)人分成三組，各組人數(shù)分別為2、2、6，去參加相同勞動(dòng)，問(wèn)有幾種安排方法？方法：要除以相同元素個(gè)數(shù)的那幾個(gè)組的組數(shù)的全排列，但是不必乘以總組數(shù)的全排列。C102×C82×C66÷A22不同元素不編號(hào)均勻分組（部分均勻、全部均勻）排列組合中的分組分配問(wèn)題

６個(gè)學(xué)生平均分成3組，有多少種分法？６個(gè)學(xué)生平均分到3個(gè)不同的班級(jí)，有多少種分法？頭痛了吧？分組分配問(wèn)題是排列組合教學(xué)中的一個(gè)重點(diǎn)和難點(diǎn)。某些排列組合問(wèn)題看似非分配問(wèn)題，實(shí)際上可運(yùn)用分配問(wèn)題的方法來(lái)解決。排列組合中的分組分配問(wèn)題６個(gè)學(xué)生平均分成3組，一提出分組與分配問(wèn)題，澄清模糊概念n個(gè)不同元素按照某些條件分配給k個(gè)不同得對(duì)象，稱(chēng)為分配問(wèn)題，分定向分配和不定向分配兩種問(wèn)題；將n個(gè)不同元素按照某些條件分成k組，稱(chēng)為分組問(wèn)題。分組問(wèn)題有不平均分組、平均分組、和部分平均分組三種情況。分組問(wèn)題和分配問(wèn)題是有區(qū)別的，前者組與組之間只要元素個(gè)數(shù)相同是不區(qū)分的；而后者即使2組元素個(gè)數(shù)相同，但因?qū)ο蟛煌匀皇强蓞^(qū)分的。對(duì)于后者必須先分組后排列。一提出分組與分配問(wèn)題，澄清模糊概念二基本的分組問(wèn)題例1六本不同的書(shū)，分為三組，求在下列條件下各有多少種不同的分配方法？(1)每組兩本（均分三堆）１５(2)一組一本，一組二本，一組三本６０(3)一組四本，另外兩組各一本１５二基本的分組問(wèn)題分析：(1)分組與順序無(wú)關(guān)，是組合問(wèn)題。分組數(shù)是Ｃ６２＊Ｃ４２＊Ｃ２２=90(種)這90種分組實(shí)際上重復(fù)了6次。我們不妨把六本不同的書(shū)標(biāo)上1、2、3、4、5、6六個(gè)號(hào)碼。考察以下兩種分法：(1，2)(3，4)(5，6)與(3，4)(1，2)(5，6)，由于書(shū)是均勻分組的，三組的本數(shù)一樣，又與順序無(wú)關(guān)，所以這兩種分法是同一種分法。以上的分組方法實(shí)際上加入了組的順序，因此還應(yīng)取消分組的順序，即除以組數(shù)的全排列數(shù)Ａ３３＝６，所以分法是９０／６=15(種)。(2)先分組，方法是Ｃ６１＊Ｃ５２＊Ｃ３３＝６０，那么還要不要除以Ａ３３？我們發(fā)現(xiàn)，由于每組的書(shū)的本數(shù)是不一樣的，因此不會(huì)出現(xiàn)相同的分法，即共有=60(種)分法。(3)分組方法是Ｃ６４＊Ｃ２１＊Ｃ１１=30(種)其中有沒(méi)有重復(fù)的分法？我們發(fā)現(xiàn)，其中兩組的書(shū)的本數(shù)都是一本，因此這兩組有了順序，而與四本書(shū)的那一組，由于書(shū)的本數(shù)不一樣，不可能重復(fù)。所以實(shí)際分法是Ｃ６４＊Ｃ２１＊Ｃ１１／Ａ２２=15(種)。分析：通過(guò)以上三個(gè)小題的分析，我們可以得出分組問(wèn)題的一般方法。結(jié)論1：一般地，n個(gè)不同的元素分成p組，各組內(nèi)元素?cái)?shù)目分別為m１，m２，…，mＰ，其中k組內(nèi)元素?cái)?shù)目相等，那么分組方法數(shù)是通過(guò)以上三個(gè)小題的分析，我們可以得出分組問(wèn)題的一般方法。三基本的分配的問(wèn)題１定向分配問(wèn)題例2六本不同的書(shū)，分給甲、乙、丙三人，求在下列條件下各有多少種不同的分配方法？(1)甲兩本、乙兩本、丙兩本.(2)甲一本、乙兩本、丙三本.(3)甲四本、乙一本、丙一本.分析：由于分配給三人，每人分幾本是一定的,屬分配問(wèn)題中的定向分配問(wèn)題，由分布計(jì)數(shù)原理不難解出：（１）Ｃ６２＊Ｃ４２＊Ｃ２２=90(種)（２）Ｃ６１＊Ｃ５２＊Ｃ３３=60(種)（３）Ｃ６４＊Ｃ２１＊Ｃ１１=30(種)。三基本的分配的問(wèn)題２不定向分配問(wèn)題例3六本不同的書(shū)，分給甲、乙、丙三人，求在下列條件下各有多少種不同的分配方法？(1)每人兩本(2)一人一本、一人兩本、一人三本(3)一人四本、一人一本、一人一本分析：此組題屬于分配中的不定向分配問(wèn)題，是該類(lèi)題中比較困難的問(wèn)題。由于分配給三人，同一本書(shū)給不同的人是不同的分法，所以是排列問(wèn)題。實(shí)際上可看作“分為三組，再將這三組分給甲、乙、丙三人”，因此只要將分組方法數(shù)再乘以Ａ３３＝６，即（１）１５＊６=90(種)（２）６０＊６=360(種)（３）１５＊６=90(種)。２不定向分配問(wèn)題結(jié)論2.一般地，如果把不同的元素分配給幾個(gè)不同對(duì)象，并且每個(gè)不同對(duì)象可接受的元素個(gè)數(shù)沒(méi)有限制，那么實(shí)際上是先分組后排列的問(wèn)題，即分組方案數(shù)乘以不同對(duì)象數(shù)的全排列數(shù)。解不定向分配題的一般原則：先分組后排列。結(jié)論2.一般地，如果把不同的元素分配給幾個(gè)不同對(duì)象，并且每例4六本不同的書(shū)，分給甲、乙、丙三人，每人至少一本，有多少種分法？分析：六本書(shū)和甲、乙、丙三人都有“歸宿”，即書(shū)要分完，人不能空手。因此，考慮先分組，后排列。先分組，六本書(shū)怎么分為三組呢？有三類(lèi)分法(1)每組兩本(2)分別為一本、二本、三本(3)兩組各一本，另一組四本。所以根據(jù)加法原理，分組法是

+

+

=90(種)。再考慮排列，即再乘以

。所以一共有540種不同的分法。例4六本不同的書(shū)，分給甲、乙、丙三人，每人至少一本，有多少例6有甲、乙、丙三項(xiàng)任務(wù)，甲需2人承擔(dān)，乙、丙各需1人承擔(dān)，從10人中選派4人承擔(dān)這三項(xiàng)任務(wù)，不同的選法有多少種？分析：先考慮分組，即10人中選4人分為三組，其中兩組各一人，另一組二人，共有Ｃ１０４＊Ｃ４２(種)分法。再考慮排列，甲任務(wù)需2人承擔(dān)，因此2人的那個(gè)組只能承擔(dān)甲任務(wù)，而一個(gè)人的兩組既可承擔(dān)乙任務(wù)又可承擔(dān)丙任務(wù)，全排。共Ｃ１０４＊Ｃ４２＊Ａ２２=2520(種)不同的選法。例6有甲、乙、丙三項(xiàng)任務(wù)，甲需2人承擔(dān)，乙、丙各需1人承擔(dān)四分配問(wèn)題的變形問(wèn)題例5四個(gè)不同的小球放入編號(hào)為1，2，3，4的四個(gè)盒子中，恰有一個(gè)空盒的放法有多少種？分析：恰有一個(gè)空盒，則另外三個(gè)盒子中小球數(shù)分別為1，1，2。實(shí)際上可轉(zhuǎn)化為先將四個(gè)不同的小球分為三組，兩組各1個(gè)，另一組2個(gè)，分組方法有(種)，然后將這三組(即三個(gè)不同元素)分配給四個(gè)小盒(不同對(duì)象)中的3個(gè)的排列問(wèn)題，即共有=144(種)。四分配問(wèn)題的變形問(wèn)題例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ù)目不限，所以此問(wèn)題實(shí)際上還是分組后分配的問(wèn)題。先考慮分組，集合A中4個(gè)元素分為三組，各組的元素?cái)?shù)目分別為1、1、2，則共有(種)分組方法。再考慮分配，即排列，再乘以，所以共有=36(個(gè))不同的函數(shù)。例7設(shè)集合A={1，2，3，4}，B={6，7，8}，A為附一編號(hào)分組：1相同元素編號(hào)分組“編號(hào)分組”的意思是：即使分出來(lái)兩個(gè)或多個(gè)組中，元素的個(gè)數(shù)相同，仍然看成不同的組例題：10個(gè)相同的小球，放入5個(gè)不同的盒子里面，每個(gè)盒子至少要放一個(gè)球。問(wèn)有幾種放法？方法（隔板法）5個(gè)盒子，設(shè)置4個(gè)隔板，插入9個(gè)空中。C94

附2不同元素編號(hào)分組分成兩種情況：(i)非均勻編號(hào)分組（每組元素個(gè)數(shù)不同）例題：10個(gè)人分成三組，各組人數(shù)分別為2、3、5，去參加不同（在這里體現(xiàn)“編號(hào)分組”）勞動(dòng)，問(wèn)有幾種安排方法？方法：分步選人，分別適合各組人數(shù)，然后要乘以組數(shù)的全排列。C102×C83×C55×A33(ii)均勻編號(hào)分組（包括部分均勻、全部均勻）2不同元素編號(hào)分組例題：10個(gè)人分成三組，各組人數(shù)分別為2、2、6，去參加不同勞動(dòng)問(wèn)有幾種安排方法？方法：分步選人，分別適合各組人數(shù)。但是，由于有兩個(gè)或兩個(gè)以上的組人數(shù)相同，而選人時(shí)