- 相關(guān)推薦
排列組合中的分組分配問題-藍天蔚-新浪博客
排列組合中的分組分配問題(2010-03-12 17:44:05) 標簽： 教育 中學 高中 數(shù)學 分組 均勻 不均勻 分配 定向分配 不定向分配 雜談 分類：誤人子弟 ６個學生平均分成3組，有多少種分法？ �。秱�學生平均分到3個不同的班級，有多少種分法？ 頭痛了吧？分組分配問題是排列組合教學中的一個重點和難點。某些排列組合問題看似非分配問題，實際上可運用分配問題的方法來解決。 一 提出分組與分配問題，澄清模糊概念 n個不同元素按照某些條件分配給k個不同得對象，稱為分配問題，分定向分配和不定向分配兩種問題； 將n個不同元素按照某些條件分成k組，稱為分組問題�！》纸M問題有不平均分組、平均分組、和部分平均分組三種情況�！》纸M問題和分配問題是有區(qū)別的，前者組與組之間只要元素個數(shù)相同是不區(qū)分的；而后者即使2組元素個數(shù)相同，但因?qū)ο蟛煌�，仍然是可區(qū)分的。對于后者必須先分組后排列。二 基本的分組問題例1 六本不同的書，分為三組，求在下列條件下各有多少種不同的分配方法？(1)每組兩本（均分三堆）１５(2)一組一本，一組二本，一組三本６０(3)一組四本，另外兩組各一本１５(４)平均分給甲乙丙三人９０分析：(1)分組與順序無關(guān)，是組合問題。分組數(shù)是Ｃ６２＊Ｃ４２＊Ｃ２２=90(種) 這90種分組實際上重復(fù)了6次。 我們不妨把六本不同的書標上1、2、3、4、5、6六個號碼�！】疾煲韵聝煞N分法：(1，2)(3，4)(5，6)與(3，4)(1，2)(5，6)，由于書是均勻分組的，三組的本數(shù)一樣，又與順序無關(guān)，所以這兩種分法是同一種分法。以上的分組方法實際上加入了組的順序，因此還應(yīng)取消分組的順序，即除以組數(shù)的全排列數(shù)Ａ３３＝６，所以分法是 ９０／６=15(種)。 (2)先分組，方法是Ｃ６１＊Ｃ５２＊Ｃ３３＝６０ ，那么還要不要除以Ａ３３？我們發(fā)現(xiàn)，由于每組的書的本數(shù)是不一樣的，因此不會出現(xiàn)相同的分法，即共有 =60(種) 分法。 (3)分組方法是Ｃ６４＊Ｃ２１＊Ｃ１１=30(種) 其中有沒有重復(fù)的分法？我們發(fā)現(xiàn)，其中兩組的書的本數(shù)都是一本，因此這兩組有了順序，而與四本書的那一組，由于書的本數(shù)不一樣，不可能重復(fù)。所以實際分法是Ｃ６４＊Ｃ２１＊Ｃ１１／Ａ２２=15(種)�！ ⊥ㄟ^以上三個小題的分析，我們可以得出分組問題的一般方法�！〗Y(jié)論1： 一般地，n個不同的元素分成p組，各組內(nèi)元素數(shù)目分別為m１ ，m ２，…，mＰ ，其中k組內(nèi)元素數(shù)目相等，那么分組方法數(shù)是Ｃ。 三 基本的分配的問題 １定向分配問題例2 六本不同的書，分給甲、乙、丙三人，求在下列條件下各有多少種不同的分配方法？(1) 甲兩本、乙兩本、丙兩本.(2) 甲一本、乙兩本、丙三本.(3) 甲四本、乙一本、丙一本. 分析：由于分配給三人，每人分幾本是一定的,屬分配問題中的定向分配問題，由分布計數(shù)原理不難解出：（１）Ｃ６２＊Ｃ４２＊Ｃ２２=90(種)（２）Ｃ６１＊Ｃ５２＊Ｃ３３=60(種)（３）Ｃ６４＊Ｃ２１＊Ｃ１１=30(種)。 ２不定向分配問題例3 六本不同的書，分給甲、乙、丙三人，求在下列條件下各有多少種不同的分配 方法？(1) 每人兩本(2) 一人一本、一人兩本、一人三本(3) 一人四本、一人一本、一人一本分析：此組題屬于分配中的不定向分配問題，是該類題中比較困難的問題。由于分配給三人，同一本書給不同的人是不同的分法，所以是排列問題。實際上可看作“分為三組，再將這三組分給甲、乙、丙三人”，因此只要將分組方法數(shù)再乘以Ａ３３＝６ ，即�。ǎ保保担�=90(種) （２）６０＊６=360(種)�。ǎ常保担�=90(種)。結(jié)論2. 一般地，如果把不同的元素分配給幾個不同對象，并且每個不同對象可接受的元素個數(shù)沒有限制，那么實際上是先分組后排列的問題，即分組方案數(shù)乘以不同對象數(shù)的全排列數(shù)。 解不定向分配題的一般原則：先分組后排列。 例4 六本不同的書，分給甲、乙、丙三人，每人至少一本，有多少種分法？分析：六本書和甲、乙、丙三人都有“歸宿”，即書要分完，人不能空手。因此，考慮先分組，后排列。先分組，六本書怎么分為三組呢？有三類分法(1)每組兩本(2)分別為一本、二本、三本(3)兩組各一本，另一組四本。所以根據(jù)加法原理，分組法是 + + =90(種)。再考慮排列，即再乘以 。所以一共有540種不同的分法。 四 分配問題的變形問題例5 四個不同的小球放入編號為1，2，3，4的四個盒子中，恰有一個空盒的放法有多少種？分析：恰有一個空盒，則另外三個盒子中小球數(shù)分別為1，1，2。實際上可轉(zhuǎn)化為先將四個不同的小球分為三組，兩組各1個，另一組2個，分組方法有 (種)，然后將這三組(即三個不同元素)分配給四個小盒(不同對象)中的3個的排列問題，即共有 =144(種)。 例6 有甲、乙、丙三項任務(wù)，甲需2人承擔，乙、丙各需1人承擔，從10人中選派4人承擔這三項任務(wù)，不同的選法有多少種？分析：先考慮分組，即10人中選4人分為三組，其中兩組各一人，另一組二人，共有Ｃ１０�。矗茫矗�(種)分法。再考慮排列，甲任務(wù)需2人承擔，因此2人的那個組只能承擔甲任務(wù)，而一個人的兩組既可承擔乙任務(wù)又可承擔丙任務(wù)，全排。共Ｃ１０�。矗茫矗玻粒玻� =2520(種)不同的選法。 例7 設(shè)集合A={1，2，3，4}，B={6，7，8}，A為定義域，B為值域，則從集合A到集合B的不同的函數(shù)有多少個？分析：由于集合A為定義域，B為值域，即集合A、B中的每個元素都有“歸宿”，而集合B的每個元素接受集合A中對應(yīng)的元素的數(shù)目不限，所以此問題實際上還是分組后分配的問題。先考慮分組，集合A中4個元素分為三組，各組的元素數(shù)目分別為1、1、2，則共有 (種)分組方法。再考慮分配，即排列，再乘以 ，所以共有 =36(個)不同的函數(shù)。 例８設(shè)集合A={1，2，3，4}，B={6，7，8},映射f:A->B滿足f(1)<＝f(2)<＝f(3)<＝f(4)＝<f(5)且Ｂ中的三個元素在Ａ中都有原象，這樣的映射共有多少個？從１，２，３，４，５，中插入３個隔板，依次與６，７，８，對應(yīng)，因此共有Ｃ４３＝４種不同的映射 附一 編號分組：1 相同元素 編號分組 “編號分組”的意思是：即使分出來兩個或多個組中，元素的個數(shù)相同，仍然看成不同的組 例題： 10個相同的小球，放入5個不同的盒子里面，每個盒子至少要放一個球�！ 栍袔追N放法？ 方法（隔板法） 5個盒子，設(shè)置4個隔板，插入9個空中。C94 2 不同元素 編號分組 分成兩種情況： (i)非均勻編號分組（每組元素個數(shù)不同） 例題：10個人分成三組，各組人數(shù)分別為2、3、5，去參加不同（在這里體現(xiàn)“編號分組”）勞動，問有幾種安排方法？ 方法：分步選人，分別適合各組人數(shù)，然后要乘以組數(shù)的全排列。 C102×C83×C55×A33 (ii)均勻編號分組（包括部分均勻、全部均勻） 例題：10個人分成三組，各組人數(shù)分別為2、2、6，去參加不同勞動 問有幾種安排方法？ 方法：分步選人，分別適合各組人數(shù)。 但是，由于有兩個或兩個以上的組人數(shù)相同，而選人時又是分步選人的（即有順序在里面），所以必然會造成重復(fù)。比如：甲乙、丙丁和丙丁、甲乙是一種情況，我們卻多算了。要除以元素相同的幾個組的組數(shù)的全排列 選人完之后要放進編好號碼的組里面，所以乘以總組數(shù)的全排列。 C102×C82×C66÷A22×A33 二 不編號分組： 與編號分組不同的是，在不編號分組中，各個組元素的個數(shù)成為了區(qū)別不同組的唯一標志，換言之，只要有兩個或者多個組有相同個數(shù)的元素，它們就被視為相同的組。 在這里，由于組已經(jīng)沒有編號了，如果要放進組里面的元素再不可區(qū)分，那問題就變得沒什么意義，而且很簡單了。比如：三個相同的球，放入兩個相同的盒子里面，只有一種放法，那就是其中一個盒子放一個球，另外那個盒子放剩下的那兩個球。所以用列舉法就可以了。 在這里主要討論不同元素的情況。 1，不同元素，不編號不均勻分組。 例題：10個人分成三組，各組人數(shù)分別為2、3、5，去參加相同（在這里體現(xiàn)“不編號分組”）勞動，問有幾種安排方法？ 方法：和“不同元素，編號不均勻分組”相比，不必乘以組數(shù)的全排列，因為三個組參加的是相同的勞動（這里“相同”的言下之意是：勞動內(nèi)容相同，又是同時去的，如果不同時，還要當作編號分組） C102×C83×C55 不同元素 不編號均勻分組（部分均勻、全部均勻） 例題：10個人分成三組，各組人數(shù)分別為2、2、6，去參加相同勞動，問有幾種安排方法？ 方法：要除以相同元素個數(shù)的那幾個組的組數(shù)的全排列，但是不必乘以總組數(shù)的全排列。 C102×C82×C66÷A22【排列組合中的分組分配問題-藍天蔚-新浪博客】相關(guān)文章：
論博客傳播中的倫理問題04-29
試析收入分配中的公平與效率問題04-28
倫理視角下的博客問題研究04-29
排列組合中的數(shù)學思想方法04-29
排列組合中的序、分例析04-29
問題為主線,活動為主體的分組教學04-29
高考作文素材：精美仿寫100例(1)-茶博士-新浪博客04-25
分組教學在羽毛球教學中的運用04-29
博客在大學英語教學中的作用04-28
博客在教育教學中的應(yīng)用初探04-28