排列組合復習課-解排列組合問題的常用技巧

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

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

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

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

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

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

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

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

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

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

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

12、進行處理。八八. .元素相同問題隔板策略元素相同問題隔板策略例例8.有有1010個運動員名額，在分給個運動員名額，在分給7 7個班，每班至少個班，每班至少一個一個, ,有多少種分配方案？有多少種分配方案？ 解：解：因為因為10個名額沒有差別，把它們排成一排。個名額沒有差別，把它們排成一排。相鄰名額之間形成個空隙。相鄰名額之間形成個空隙。在個空檔中選個位置插個隔板，可把名額在個空檔中選個位置插個隔板，可把名額分成份，對應地分給個班級，每一種插板分成份，對應地分給個班級，每一種插板方法對應一種分法共有方法對應一種分法共有_種分法。種分法。一班二班三班四班五班六班七班69C11mnC練習題.將將8個

13、學生干部的培訓指標分配給個學生干部的培訓指標分配給5個不同的個不同的班級，每班班級，每班至少至少分到分到1個名額，共有多少種不同個名額，共有多少種不同的分配方法？的分配方法？ .從從6個學校中選出個學校中選出30名學生參加數學競賽名學生參加數學競賽,每每校校至少至少有有1人人,這樣有幾種選法這樣有幾種選法?例例9.9.我們班里有我們班里有6262位同學位同學, ,從中任抽從中任抽5 5人人, ,正、正、副班長、團支部書記至少有一人在內的副班長、團支部書記至少有一人在內的抽法有多少種抽法有多少種? ?十十. .平均分組問題除法策略平均分組問題除法策略例10. 6本不同的書平均分成本不同的書平均分

14、成3堆堆,每堆每堆2本共有本共有 多少分法？多少分法？解解: 分三步取書得分三步取書得 種方法種方法,但這里出現但這里出現 重復計數的現象重復計數的現象,不妨記不妨記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為均為均分的組數分的組數)避免重復計數。避免重復計數。nnA練習練習. 將將13個球隊分成個球隊分成3組組,一組一組5個隊個隊,其它兩其它兩組組4個隊個隊, 有多少分法？有多少分法？544138422C C CA “多面手多面手”沒有被選上的選法共有沒有被選上的選法共有_種種, ,“多面手多面手”若被選上，則又可以分兩類：若被選上，則又可以分兩類： 他唱歌他唱歌的選法共有的選法共有_種，種， 他跳舞的選法共有他跳舞的選法共有 種種

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

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

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

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

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

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