排列組合復(fù)習(xí)課-解排列組合問題的常用技巧

1、知識(shí)復(fù)習(xí)知識(shí)復(fù)習(xí)+梳理梳理 12nN=m +m +m復(fù)習(xí)鞏固復(fù)習(xí)鞏固12nN=m mm復(fù)習(xí)回顧排列數(shù)排列數(shù)從從n n個(gè)不同元素中取出個(gè)不同元素中取出m(mn)m(mn)個(gè)元素個(gè)元素, ,按照一定按照一定的順序排成一列的順序排成一列, ,叫做從叫做從n n個(gè)不同元素中取出個(gè)不同元素中取出m m個(gè)個(gè)元素的元素的一個(gè)排列一個(gè)排列.從n nm m個(gè)元素的個(gè)元素的排列數(shù)排列數(shù)。n n個(gè)不同元素中取出個(gè)不同元素中取出叫做從所有排列的個(gè)數(shù)，所有排列的個(gè)數(shù)，個(gè)元素的個(gè)元素的個(gè)不同元素中取出個(gè)不同元素中取出m(mn)排列排列排列數(shù)公式排列數(shù)公式) 1() 2)(1(mnnnnAmn!mn )!n (我們規(guī)定我們

2、規(guī)定:0!=1:0!=1復(fù)習(xí)回顧組合數(shù)組合數(shù)從從n n個(gè)不同元素中取出個(gè)不同元素中取出m(mn)m(mn)個(gè)元素個(gè)元素, ,并成一組并成一組, ,叫做從叫做從n n個(gè)不同元素中取出個(gè)不同元素中取出m m個(gè)元素的個(gè)元素的一個(gè)組合一個(gè)組合.從n nm m個(gè)元素的個(gè)元素的組合數(shù)組合數(shù)。n n個(gè)不同元素中取出個(gè)不同元素中取出叫做從所有組合的個(gè)數(shù)，所有組合的個(gè)數(shù)，個(gè)元素的個(gè)元素的個(gè)不同元素中取出個(gè)不同元素中取出m(mn)組合組合組合數(shù)公式和兩個(gè)重要性組合數(shù)公式和兩個(gè)重要性質(zhì)質(zhì)!()!mmn mnnnmmAnCCAmnm 11mmmnnnCCC 解決實(shí)際問題時(shí)首先要看是否與順解決實(shí)際問題時(shí)首先要看是否與順

3、序有關(guān)，從而確定是排列問題還是組序有關(guān)，從而確定是排列問題還是組合問題，必要時(shí)要利用分類和分步計(jì)合問題，必要時(shí)要利用分類和分步計(jì)數(shù)原理數(shù)原理強(qiáng)調(diào)：排列強(qiáng)調(diào)：排列有順序；有順序； 組合組合無順序無順序 在處理問題時(shí)，一般可采用在處理問題時(shí)，一般可采用直接直接和和間接間接 兩種思維形式，從而尋求有效的解題途徑兩種思維形式，從而尋求有效的解題途徑:例例1.由由0,1,2,3,4,5可以組成多少個(gè)沒有重復(fù)數(shù)字可以組成多少個(gè)沒有重復(fù)數(shù)字 五位奇數(shù)五位奇數(shù). 解解:由于末位和首位有特殊要求由于末位和首位有特殊要求,應(yīng)該優(yōu)先安應(yīng)該優(yōu)先安 排排,以免不合要求的元素占了這兩個(gè)位置以免不合要求的元素占了這兩個(gè)位置

4、先排末位共有先排末位共有_ 然后排首位共有然后排首位共有_最后排其它位置共有最后排其它位置共有_13C13C14C14C34A34A由分步計(jì)數(shù)原理得由分步計(jì)數(shù)原理得=28813C14C34A例例2. 72. 7人站成一排人站成一排 , ,其中甲乙相鄰且丙丁相其中甲乙相鄰且丙丁相 鄰鄰, , 共有多少種不同的排法共有多少種不同的排法. .甲甲乙乙丙丙丁丁由分步計(jì)數(shù)原理可得共有由分步計(jì)數(shù)原理可得共有種不同的排法種不同的排法55A22A22A=480解：可先將甲乙兩元素捆綁成整體并看成解：可先將甲乙兩元素捆綁成整體并看成 一個(gè)復(fù)合元素，同時(shí)丙丁也看成一個(gè)一個(gè)復(fù)合元素，同時(shí)丙丁也看成一個(gè) 復(fù)合元素，再

5、與其它元素進(jìn)行排列，復(fù)合元素，再與其它元素進(jìn)行排列， 同時(shí)對(duì)相鄰元素內(nèi)部進(jìn)行自排。同時(shí)對(duì)相鄰元素內(nèi)部進(jìn)行自排。 . .55A第二步將第二步將4 4舞蹈插入第一步排舞蹈插入第一步排好的好的5 5個(gè)元素中間包含首尾兩個(gè)空位共有個(gè)元素中間包含首尾兩個(gè)空位共有種種 不同的方法不同的方法 46A由分步計(jì)數(shù)原理由分步計(jì)數(shù)原理,節(jié)目的節(jié)目的不同順序共有不同順序共有 種種55A46A相相相相獨(dú)獨(dú)獨(dú)獨(dú)獨(dú)獨(dú)四四. .重排問題求冪策略重排問題求冪策略例例4.4.把把6 6名實(shí)習(xí)生分配到名實(shí)習(xí)生分配到7 7個(gè)車間實(shí)習(xí)個(gè)車間實(shí)習(xí), ,共有共有 多少種不同的分法多少種不同的分法解解: :完成此事共分六步完成此事共分六步:

6、 :把第一名實(shí)習(xí)生分配把第一名實(shí)習(xí)生分配 到車間有到車間有 種分法種分法. .7 7把第二名實(shí)習(xí)生分把第二名實(shí)習(xí)生分配配 到車間也有到車間也有7 7種分法，種分法， 依此類推依此類推, ,由分步由分步計(jì)計(jì)數(shù)原理共有數(shù)原理共有 種不同的排法種不同的排法67允許重復(fù)的排列問題的特點(diǎn)是以元素為研究允許重復(fù)的排列問題的特點(diǎn)是以元素為研究對(duì)象，元素不受位置的約束，可以逐一安排對(duì)象，元素不受位置的約束，可以逐一安排各個(gè)元素的位置，一般地各個(gè)元素的位置，一般地n不同的元素沒有限不同的元素沒有限制地安排在制地安排在m個(gè)位置上的排列數(shù)為個(gè)位置上的排列數(shù)為 種種n nm m（住店法）（住店法）解決解決“允許重復(fù)排

7、列問題允許重復(fù)排列問題”要注意區(qū)分兩類元素：要注意區(qū)分兩類元素： 一類元素可以重復(fù)，另一類不能重復(fù)，把不能重復(fù)的一類元素可以重復(fù)，另一類不能重復(fù)，把不能重復(fù)的元素看作元素看作“客人客人”，能重復(fù)的元素看作，能重復(fù)的元素看作“店店”，再利用乘，再利用乘法原理直接求解。法原理直接求解。練習(xí)練習(xí) 七名學(xué)生爭(zhēng)奪五項(xiàng)冠軍，每項(xiàng)冠軍只能由一人七名學(xué)生爭(zhēng)奪五項(xiàng)冠軍，每項(xiàng)冠軍只能由一人獲得，獲得冠軍的可能的種數(shù)有（獲得，獲得冠軍的可能的種數(shù)有（ ）A. B. C D.分析：因同一學(xué)生可以同時(shí)奪得分析：因同一學(xué)生可以同時(shí)奪得n項(xiàng)冠軍，故學(xué)生可重復(fù)排列，項(xiàng)冠軍，故學(xué)生可重復(fù)排列，將七名學(xué)生看作將七名學(xué)生看作7家家

8、“店店”，五項(xiàng)冠軍看作，五項(xiàng)冠軍看作5名名“客人客人”，每，每個(gè)個(gè)“客人客人”有有7種住宿法，由乘法原理得種住宿法，由乘法原理得 種。種。注：對(duì)此類問題，常有疑惑，為什么不是注：對(duì)此類問題，常有疑惑，為什么不是 呢？呢？57577557A57C75用分步計(jì)數(shù)原理看，用分步計(jì)數(shù)原理看，5是步驟數(shù)，自然是指數(shù)。是步驟數(shù)，自然是指數(shù)。住店法：住店法：例例5.5. 8 8人排成前后兩排人排成前后兩排, ,每排每排4 4人人, ,其中甲乙其中甲乙在前排在前排, ,丁在后排丁在后排, ,共有多少排法？共有多少排法？解解:8人排前后兩排人排前后兩排,相當(dāng)于相當(dāng)于8人坐人坐8把椅子把椅子,可以可以 把椅子排成

9、一排把椅子排成一排. 先在前先在前4個(gè)位置排甲乙兩個(gè)位置排甲乙兩個(gè)特殊元素有個(gè)特殊元素有_種種,再排后再排后4個(gè)位置上的個(gè)位置上的特殊元素有特殊元素有_種種,其余的其余的5人在人在5個(gè)位置個(gè)位置上任意排列有上任意排列有_種種,則共有則共有_種種.前排后排后排24A14A55A24A55A14A一般地一般地,元素分成多排的排列問題元素分成多排的排列問題,可歸結(jié)為一排考慮可歸結(jié)為一排考慮,再分段研究再分段研究.例例6.6.有有5 5個(gè)不同的小球個(gè)不同的小球, ,裝入裝入4 4個(gè)不同的盒內(nèi)個(gè)不同的盒內(nèi), , 每盒至少裝一個(gè)球每盒至少裝一個(gè)球, ,共有多少不同的裝共有多少不同的裝 法法. .解解: :

10、第一步從第一步從5 5個(gè)球中選出個(gè)球中選出2 2個(gè)組成復(fù)合元共個(gè)組成復(fù)合元共 有有_種方法種方法. .再把再把5 5個(gè)元素個(gè)元素( (包含一個(gè)復(fù)合包含一個(gè)復(fù)合 元素元素) )裝入裝入4 4個(gè)不同的盒內(nèi)有個(gè)不同的盒內(nèi)有_種方法種方法. .25C44A根據(jù)分步計(jì)數(shù)原理裝球的方法共有根據(jù)分步計(jì)數(shù)原理裝球的方法共有_25C44A練習(xí)題一個(gè)班有一個(gè)班有6 6名戰(zhàn)士名戰(zhàn)士, ,其中正副班長(zhǎng)各其中正副班長(zhǎng)各1 1人人現(xiàn)從中選現(xiàn)從中選4 4人完成四種不同的任務(wù)人完成四種不同的任務(wù), ,每人每人完成一種任務(wù)完成一種任務(wù), ,且正副班長(zhǎng)有且只有且正副班長(zhǎng)有且只有1 1人人參加參加, ,則不同的選法有則不同的選法有

11、_ _ 種種192192例例7.7.用用1,2,3,4,51,2,3,4,5組成沒有重復(fù)數(shù)字的五位數(shù)組成沒有重復(fù)數(shù)字的五位數(shù) 其中恰有兩個(gè)偶數(shù)夾其中恰有兩個(gè)偶數(shù)夾在在1,1,兩個(gè)奇數(shù)之兩個(gè)奇數(shù)之 間間, ,這樣的五位數(shù)有多少個(gè)？這樣的五位數(shù)有多少個(gè)？解：把解：把,當(dāng)作一個(gè)小集團(tuán)與排隊(duì)當(dāng)作一個(gè)小集團(tuán)與排隊(duì)共有共有_種排法，再排小集團(tuán)內(nèi)部共有種排法，再排小集團(tuán)內(nèi)部共有_種排法，由分步計(jì)數(shù)原理共有種排法，由分步計(jì)數(shù)原理共有_種排法種排法.22A2222A A2222A A22A31524小集團(tuán)小集團(tuán)小集團(tuán)排列問題中，先整體后局小集團(tuán)排列問題中，先整體后局部，再結(jié)合其它策略進(jìn)行處理。部，再結(jié)合其它策略

12、進(jìn)行處理。八八. .元素相同問題隔板策略元素相同問題隔板策略例例8.有有1010個(gè)運(yùn)動(dòng)員名額，在分給個(gè)運(yùn)動(dòng)員名額，在分給7 7個(gè)班，每班至少個(gè)班，每班至少一個(gè)一個(gè), ,有多少種分配方案？有多少種分配方案？ 解：解：因?yàn)橐驗(yàn)?0個(gè)名額沒有差別，把它們排成一排。個(gè)名額沒有差別，把它們排成一排。相鄰名額之間形成個(gè)空隙。相鄰名額之間形成個(gè)空隙。在個(gè)空檔中選個(gè)位置插個(gè)隔板，可把名額在個(gè)空檔中選個(gè)位置插個(gè)隔板，可把名額分成份，對(duì)應(yīng)地分給個(gè)班級(jí)，每一種插板分成份，對(duì)應(yīng)地分給個(gè)班級(jí)，每一種插板方法對(duì)應(yīng)一種分法共有方法對(duì)應(yīng)一種分法共有_種分法。種分法。一班二班三班四班五班六班七班69C11mnC練習(xí)題.將將8個(gè)

13、學(xué)生干部的培訓(xùn)指標(biāo)分配給個(gè)學(xué)生干部的培訓(xùn)指標(biāo)分配給5個(gè)不同的個(gè)不同的班級(jí)，每班班級(jí)，每班至少至少分到分到1個(gè)名額，共有多少種不同個(gè)名額，共有多少種不同的分配方法？的分配方法？ .從從6個(gè)學(xué)校中選出個(gè)學(xué)校中選出30名學(xué)生參加數(shù)學(xué)競(jìng)賽名學(xué)生參加數(shù)學(xué)競(jìng)賽,每每校校至少至少有有1人人,這樣有幾種選法這樣有幾種選法?例例9.9.我們班里有我們班里有6262位同學(xué)位同學(xué), ,從中任抽從中任抽5 5人人, ,正、正、副班長(zhǎng)、團(tuán)支部書記至少有一人在內(nèi)的副班長(zhǎng)、團(tuán)支部書記至少有一人在內(nèi)的抽法有多少種抽法有多少種? ?十十. .平均分組問題除法策略平均分組問題除法策略例10. 6本不同的書平均分成本不同的書平均分

14、成3堆堆,每堆每堆2本共有本共有 多少分法？多少分法？解解: 分三步取書得分三步取書得 種方法種方法,但這里出現(xiàn)但這里出現(xiàn) 重復(fù)計(jì)數(shù)的現(xiàn)象重復(fù)計(jì)數(shù)的現(xiàn)象,不妨記不妨記6本書為本書為ABCDEF 若第一步取若第一步取AB,第二步取第二步取CD,第三步取第三步取EF 該分法記為該分法記為(AB,CD,EF),則則 中還有中還有 (AB,EF,CD),(CD,AB,EF),(CD,EF,AB) (EF,CD,AB),(EF,AB,CD)共有共有 種取法種取法 ,而而 這些分法僅是這些分法僅是(AB,CD,EF)一種分法一種分法,故共故共 有有 種分法。種分法。222642CCC222642CCC33

15、A222642CCC33A平均分成的組平均分成的組,不管它們的順序如何不管它們的順序如何,都是一都是一種情況種情況,所以分組后要一定要除以所以分組后要一定要除以 (n為均為均分的組數(shù)分的組數(shù))避免重復(fù)計(jì)數(shù)。避免重復(fù)計(jì)數(shù)。nnA練習(xí)練習(xí). 將將13個(gè)球隊(duì)分成個(gè)球隊(duì)分成3組組,一組一組5個(gè)隊(duì)個(gè)隊(duì),其它兩其它兩組組4個(gè)隊(duì)個(gè)隊(duì), 有多少分法？有多少分法？544138422C C CA “多面手多面手”沒有被選上的選法共有沒有被選上的選法共有_種種, ,“多面手多面手”若被選上，則又可以分兩類：若被選上，則又可以分兩類： 他唱歌他唱歌的選法共有的選法共有_種，種， 他跳舞的選法共有他跳舞的選法共有 種種

16、, ,由分類計(jì)數(shù)原理共有由分類計(jì)數(shù)原理共有_ _ _種。種。十一. 合理分類與分步策略例例1 11.1.在一次演唱會(huì)上共在一次演唱會(huì)上共1010名演員名演員, ,其中其中7 7人能人能 能唱歌能唱歌, ,4 4人會(huì)跳舞人會(huì)跳舞, ,現(xiàn)要演出一個(gè)現(xiàn)要演出一個(gè)2 2人人 唱歌唱歌2 2人伴舞的節(jié)目人伴舞的節(jié)目, ,有多少選派方法有多少選派方法? ?解：10演員中有演員中有6人只會(huì)唱歌，人只會(huì)唱歌，3人只會(huì)跳舞人只會(huì)跳舞 1人為人為“多面手多面手”。以以“多面手多面手”是否被是否被選上為標(biāo)準(zhǔn)進(jìn)行研究：選上為標(biāo)準(zhǔn)進(jìn)行研究：2263CC2163CC1263C C + +2263CC1263C C2163

17、CC解含有約束條件的排列組合問題，可按元素的性質(zhì)進(jìn)行分類，按事件發(fā)生的連續(xù)過程分步，做到標(biāo)準(zhǔn)明確。分步層次清楚，不重不漏，分類標(biāo)準(zhǔn)一旦確定要貫穿于解題過程的始終。十二十二. .構(gòu)造模型策略構(gòu)造模型策略例例1 12.2. 馬路上有編號(hào)為馬路上有編號(hào)為1,2,3,4,5,6,7,8,91,2,3,4,5,6,7,8,9的九只的九只路燈路燈, ,現(xiàn)要關(guān)掉其中的現(xiàn)要關(guān)掉其中的3 3盞盞, ,但不能關(guān)掉相鄰的但不能關(guān)掉相鄰的2 2盞盞, ,也不能關(guān)掉兩端的也不能關(guān)掉兩端的2 2盞盞, ,求滿足條件的關(guān)燈方法有多求滿足條件的關(guān)燈方法有多少種？少種？解：把此問題當(dāng)作一個(gè)排隊(duì)模型在解：把此問題當(dāng)作一個(gè)排隊(duì)模型

18、在6 6盞盞 亮燈的亮燈的5 5個(gè)空隙中插入個(gè)空隙中插入3 3個(gè)不亮的燈個(gè)不亮的燈 有有_ _ 種種35C一些不易理解的排列組合題如果能轉(zhuǎn)化為非常熟悉的模型，如插空法，排隊(duì)模型，裝盒模型等，可使問題直觀解決練習(xí)題某排共有某排共有1010個(gè)座位，若個(gè)座位，若4 4人就坐，每人左右人就坐，每人左右兩邊都有空位，那么不同的坐法有多少種？?jī)蛇叾加锌瘴?，那么不同的坐法有多少種？練習(xí)題B BA A3735C十三十三. .實(shí)際操作窮舉策略實(shí)際操作窮舉策略例例1 13.3.設(shè)有編號(hào)設(shè)有編號(hào)1,2,3,4,51,2,3,4,5的五個(gè)球和編號(hào)的五個(gè)球和編號(hào)1,2,3,4,51,2,3,4,5的五的五個(gè)盒子個(gè)盒子,

19、 ,現(xiàn)將現(xiàn)將5 5個(gè)球投入這五盒子內(nèi)個(gè)球投入這五盒子內(nèi), ,要求每個(gè)盒子放一個(gè)要求每個(gè)盒子放一個(gè)球，并且恰好有兩個(gè)球的編號(hào)與盒子的編號(hào)相同球，并且恰好有兩個(gè)球的編號(hào)與盒子的編號(hào)相同, ,有多少有多少投法投法? ? 利用實(shí)際操作法，如果剩利用實(shí)際操作法，如果剩下下3,4,53,4,5號(hào)球和號(hào)球和3,4,53,4,5號(hào)盒號(hào)盒, ,3 3號(hào)球裝號(hào)球裝4 4號(hào)盒時(shí)，則號(hào)盒時(shí)，則4,54,5號(hào)球有只有號(hào)球有只有1 1種裝法種裝法. .3 3號(hào)盒號(hào)盒4 4號(hào)盒號(hào)盒5 5號(hào)盒號(hào)盒3 34 45 5解：從解：從5 5個(gè)球中取出個(gè)球中取出2 2個(gè)與盒子對(duì)號(hào)有個(gè)與盒子對(duì)號(hào)有_種種, ,還剩還剩下下3 3球球3 3

20、盒序號(hào)不能對(duì)應(yīng)，盒序號(hào)不能對(duì)應(yīng)，25C 同理同理3 3號(hào)球裝號(hào)球裝5 5號(hào)盒時(shí)號(hào)盒時(shí),4,5,4,5號(hào)球號(hào)球有也只有有也只有1 1種裝法種裝法, ,由分步計(jì)數(shù)原理有由分步計(jì)數(shù)原理有2 2 種種. .25C類似列舉法類似列舉法（實(shí)驗(yàn)法）（實(shí)驗(yàn)法） 題中附加條件增多，直接解決困難時(shí)，用實(shí)驗(yàn)逐題中附加條件增多，直接解決困難時(shí)，用實(shí)驗(yàn)逐步尋求規(guī)律有時(shí)也是行之有效的方法。步尋求規(guī)律有時(shí)也是行之有效的方法。 例例8 將數(shù)字將數(shù)字1，2，3，4填入標(biāo)號(hào)為填入標(biāo)號(hào)為1，2，3，4的四個(gè)的四個(gè)方格內(nèi)，每個(gè)方格填方格內(nèi)，每個(gè)方格填1個(gè)，則每個(gè)方格的標(biāo)號(hào)與所填的個(gè)，則每個(gè)方格的標(biāo)號(hào)與所填的數(shù)字均不相同的填法種數(shù)有（

21、數(shù)字均不相同的填法種數(shù)有（ ）A.6 B.9 C.11 D.23分析：分析：此題考查排列的定義，由于附加條件較多，解法較為困難，此題考查排列的定義，由于附加條件較多，解法較為困難，可用實(shí)驗(yàn)法逐步解決。可用實(shí)驗(yàn)法逐步解決。第一方格內(nèi)可填第一方格內(nèi)可填2或或3或或4。如填。如填2，則第二方格中內(nèi)可填，則第二方格中內(nèi)可填1或或3或或4。若第二方格內(nèi)填若第二方格內(nèi)填1，則第三方格只能填，則第三方格只能填4，第四方格應(yīng)填，第四方格應(yīng)填3。若第二方格內(nèi)填若第二方格內(nèi)填3，則第三方格只能填，則第三方格只能填4，第四方格應(yīng)填，第四方格應(yīng)填1。同理，若第二方格內(nèi)填同理，若第二方格內(nèi)填4，則第三方格只能填，則第三方格只能填1，第四方格應(yīng)，第四方格應(yīng)填填3。因而，第一格填。因而，第一格填2有有3種方法。種方法。（實(shí)驗(yàn)法）（實(shí)驗(yàn)法）1 1對(duì)有約束條件問題，注意如下類型最常見：對(duì)有約束條件問題，注意如下類型最常見： 特殊位置；必須相鄰；不能相鄰；特殊位置；必須相鄰；不能相鄰；2 2基本的解題方法：基本的解題方法： 優(yōu)先法優(yōu)先法； 捆綁法捆綁法； 插空法插空法；3. 3. 在處理問題時(shí)，一般可采用在處理問題時(shí)，一般可采用直接直接和和間接間接兩種思維形式，從而尋求有效的解題途徑兩種思維形式，從而尋求有效的解題途徑4.4.借助借助一題多解一題多解檢驗(yàn)答案