解排列組合問題的常用策略課件

1、解排列組合問題的常用策略課件解排列組合問題的常用策略課件1.排列和組合的區(qū)別和聯(lián)系：名 稱排 列組 合定義種數符號計算公式關系性質 ，從n個不同元素中取出m個元素，按一定的順序排成一列從n個不同元素中取出m個元素，把它并成一組所有排列的的個數所有組合的個數回目錄 牛牛文庫文檔分享1.排列和組合的區(qū)別和聯(lián)系：名 稱排 列組 某校組織學生分4個組從3處風景點中選一處去春游,則不同的春游方案的種數是A. B. C. D.（ 選 C）回目錄 牛牛文庫文檔分享某校組織學生分4個組從3處風景點中選一處去春游,則不同的春游將數字1、2、3、4 填入標號為1、2、3、4 的四個方格里 , 每格填一個數字，則每

2、個方格的標號與所填的數字都不相同的填法共有 A. 6 種 B. 9種 C.11種 D.23種（ 331= 9. 可用框圖具體填寫）回目錄 牛牛文庫文檔分享將數字1、2、3、4 填入標號為1、2、3、4 的四個方格里判斷下列問題是組合問題還是排列問題? (1)設集合A=a,b,c,d,e，則集合A的含有3個元素的子集有多少個?(2)某鐵路線上有5個車站，則這條鐵路線上共需準備多少種車票? 有多少種不同的火車票價？組合問題排列問題(3)10名同學分成人數相同的數學和英語兩個學習小組，共有多少種分法?組合問題(4)10人聚會，見面后每兩人之間要握手相互問候，共需握手多少次?組合問題(5)從4個風景點

3、中選出2個安排游覽,有多少種不同的方法?組合問題(6)從4個風景點中選出2個,并確定這2個風景點的游覽順序,有多少種不同的方法?排列問題組合問題回目錄 牛牛文庫文檔分享判斷下列問題是組合問題還是排列問題? (1)設集合A=a,總的原則合理分類和準確分步解法1 分析：先安排甲，按照要求對其進行分類，分兩類：根據分步及分類計數原理，不同的站法共有例1 6個同學和2個老師排成一排照相， 2個老師站中間，學生甲不站排頭，學生乙不站排尾，共有多少種不同的排法？1）若甲在排尾上，則剩下的5人可自由安排，有 種方法.若甲在第2、3、6、7位，則排尾的排法有 種，1位的排法有 種, 第2、3、6、7位的排法有

4、 種，根據分步計數原理，不同的站法有 種。再安排老師，有2種方法?；啬夸?牛牛文庫文檔分享總的原則合理分類和準確分步解法1 分析：先安排甲，按把握分類原理、分步原理是基礎例1如圖，某電子器件是由三個電阻組成的回路,其中有6個焊接點A，B，C，D，E，F，如果某個焊接點脫落，整個電路就會不通?，F發(fā)現電路不通了, 那么焊接點脫落的可能性共有（ ）（A） 63種 （B）64種 （C）6種 （D）36種分析:由加法原理可知由乘法原理可知 222222-1=63回目錄 牛牛文庫文檔分享把握分類原理、分步原理是基礎分析:由加法原理可知由乘法原理可（1）0，1，2，3，4，5可組成多少個無重復數字且能被五整

5、除的五位數？練 習 1分類：個位數字為5或0：個位數為0：個位數為5：回目錄 牛牛文庫文檔分享（1）0，1，2，3，4，5可組成多少個無重復數字且能被五整（2）0，1，2，3，4，5可組成多少個無重復數字且大于31250的五位數？分類：引申1：31250是由0，1，2，3，4，5組成的無重復數字的五位數中從小到大第幾個數？方法一：（排除法）方法二：（直接法）回目錄 牛牛文庫文檔分享（2）0，1，2，3，4，5可組成多少個無重復數字且大于31（2005福建理）從6人中選4人分別到巴黎、倫敦、悉尼、莫斯科四個城市游覽，要求每個城市有一人游覽，每人只游覽一個城市，且這6人中甲、乙兩人不去巴黎游覽，則

6、不同的選擇方案共有（ ） A300種B240種C144種D96種B（間接法）回目錄（直接法）分三種情況：情況一,不選甲、乙兩個去游覽情況二:甲、乙中有一人去游覽情況三：甲、乙兩人都去游覽綜上不同的選擇方案共有 240 牛牛文庫文檔分享（2005福建理）從6人中選4人分別到巴黎、倫敦、悉尼、1.從4名男生和3名女生中選出4人參加某個座 談會，若這4人中必須既有男生又有女生，則不同的選法共有_ 34 練習題2. 3成人2小孩乘船游玩,1號船最多乘3人, 2 號船最多乘2人,3號船只能乘1人,他們任選 2只船或3只船,但小孩不能單獨乘一只船, 這3人共有多少乘船方法.27回目錄 牛牛文庫文檔分享1.

7、從4名男生和3名女生中選出4人參加某個座 談會，若特殊元素和特殊位置優(yōu)先策略例1.由0,1,2,3,4,5可以組成多少個沒有重復數字 五位奇數. 解:由于末位和首位有特殊要求,應該優(yōu)先安 排,以免不合要求的元素占了這兩個位置先排末位共有_ 然后排首位共有_最后排其它位置共有_由分步計數原理得=288回目錄 牛牛文庫文檔分享特殊元素和特殊位置優(yōu)先策略例1.由0,1,2,3,4,5可以特殊元素（或位置）優(yōu)先安排例 將5列車停在5條不同的軌道上，其中a列車不停在第一軌道上，b列車不停在第二軌道上，那么不同的停放方法有（ ）（A）120種 （B）96種 （C）78種 （D）72種解： 牛牛文庫文檔分享

8、特殊元素（或位置）優(yōu)先安排例 將5列車停在5條不同的軌道上，（1）(2005 北京文)五個工程隊承建某項工程的5個不同的子項目，每個工程隊承建1項，其中甲工程隊不能承建1號子項目，則不同的承建方案共有（ ）種。（2）(2005 全國II 理)在由數字0，1，2，3，4，5所組成的沒有重復數字的四位數中，不能被整除的數共有_個 192 牛牛文庫文檔分享（1）(2005 北京文)五個工程隊承建某項工程的5個不相鄰相間問題 牛牛文庫文檔分享相鄰相間問題 牛牛文庫文檔分享相鄰元素捆綁策略例. 7人站成一排 ,其中甲乙相鄰且丙丁相 鄰, 共有多少種不同的排法.甲乙丙丁由分步計數原理可得共有種不同的排法=

9、480解：可先將甲乙兩元素捆綁成整體并看成 一個復合元素，同時丙丁也看成一個 復合元素，再與其它元素進行排列， 同時對相鄰元素內部進行自排。 回目錄 牛牛文庫文檔分享相鄰元素捆綁策略例. 7人站成一排 ,其中甲乙相鄰且丙丁相甲某人射擊8槍，命中4槍，4槍命中恰好有3槍連在一起的情形的不同種數為（ ）練習題20回目錄 牛牛文庫文檔分享某人射擊8槍，命中4槍，4槍命中恰好有3槍連在一起的情形的不不相鄰問題插空策略例3.一個晚會的節(jié)目有4個舞蹈,2個相聲,3個 獨唱,舞蹈節(jié)目不能連續(xù)出場,則節(jié)目的出 場順序有多少種？解:分兩步進行第一步排2個相聲和3個獨唱共 有 種，第二步將4舞蹈插入第一步排好的6

10、個元素中間包含首尾兩個空位共有種 不同的方法 由分步計數原理,節(jié)目的不同順序共有 種相相獨獨獨回目錄 牛牛文庫文檔分享不相鄰問題插空策略例3.一個晚會的節(jié)目有4個舞蹈,2個相聲,不相鄰問題插空法 對于某幾個元素不相鄰得排列問題，可先將其它元素排好，然后再將不相鄰的元素在已排好的元素之間及兩端的空隙之間插入即可。例5 7人站成一排照相，要求甲，乙，丙三人不相鄰，分別有多少種站法？分析：可先讓其余4人站好，共有 種排法，再在這4人之間及兩端的5個“空隙”中選三個位置讓甲、乙、丙插入，則有 種方法，這樣共有 種不同的排法?；啬夸?牛牛文庫文檔分享不相鄰問題插空法 對于某幾個元素不相鄰得排列問（1）三

11、個男生，四個女生排成一排，男生、女生各站一起，有幾種不同方法？（2）三個男生，四個女生排成一排，男生之間、女生之間不相鄰，有幾種不同排法？捆綁法：插空法：（3）(2005 遼寧)用、組成沒有重復數字的八位數，要求與相鄰，與相鄰，與相鄰，而與不相鄰，這樣的八位數共有_個（用數字作答） 練 習回目錄 牛牛文庫文檔分享（1）三個男生，四個女生排成一排，男生、女生各站一起，有幾種(3)(2005 遼寧)用、組成沒有重復數字的八位數，要求與相鄰，與相鄰，與相鄰，而與不相鄰，這樣的八位數共有_個（用數字作答） 將與，與，與捆綁在一起排成一列有 種，再將、插入4個空位中的兩個有 種，故有 種 引申:用、組成

12、沒有重復數字的六位數，要求與相鄰，與相鄰，與相鄰，現將7、8 插進去，仍要求與相鄰，與相鄰，與相鄰，那么插法共有_種（用數字作答） 回目錄 牛牛文庫文檔分享(3)(2005 遼寧)用、將“相鄰”用“捆綁”，“不鄰”就“插空”例 七人排成一排，甲、乙兩人必須相鄰，且甲、乙都不與丙相鄰，則不同的排法有（ ）種960種 （B）840種 （C）720種 （D）600種解：另解：回目錄 牛牛文庫文檔分享“相鄰”用“捆綁”，“不鄰”就“插空”例 七人排成一排，甲、練習 某城新建的一條道路上有12只路燈，為了節(jié)省用電而不影響正常的照明，可以熄滅其中三盞燈，但兩端的燈不能熄滅，也不能熄滅相鄰的兩盞燈，可以熄滅

13、的方法共有（ ）（A） 種（B） 種 （C） 種 （D） 種解：回目錄 牛牛文庫文檔分享練習 某城新建的一條道路上有12只路燈，為了節(jié)省用電而不影響定序問題倍縮空位插入策略定序問題 牛牛文庫文檔分享定序問題倍縮空位插入策略定序問題 例6 有4名男生，3名女生。3名女生高矮互不等，將7名學生排成一行，要求從左到右，女生從矮到高排列，有多少種排法？順序固定問題用“除法” 對于某幾個元素順序一定的排列問題，可先將這幾個元素與其它元素一同進行排列，然后用總的排列數除以這幾個元素的全排列數.所以共有 種。 分析：先在7個位置上作全排列，有 種排法。其中3個女生因要求“從矮到高”排，只有一種順序故 只對應

14、一種排法，回目錄 牛牛文庫文檔分享例6 有4名男生，3名女生。3名女生高矮互不等，順序定序問題倍縮空位插入策略例4.7人排隊,其中甲乙丙3人順序一定共有多 少不同的排法解:(倍縮法)對于某幾個元素順序一定的排列問題,可先把這幾個元素與其他元素一起進行排列,然后用總排列數除以這幾個元素之間的全排列數,則共有不同排法種數是： （空位法）設想有7把椅子讓除甲乙丙以外的四人就坐共有 種方法，其余的三個位置甲乙丙共有 種坐法，則共有 種 方法 1思考:可以先讓甲乙丙就坐嗎?回目錄 牛牛文庫文檔分享定序問題倍縮空位插入策略例4.7人排隊,其中甲乙丙3人順序一分房問題又名：住店法，重排問題求冪策略 牛牛文庫

15、文檔分享分房問題又名：住店法，重排問題求冪策略www.niuwk.c住店法解決“允許重復排列問題”要注意區(qū)分兩類元素： 一類元素可以重復，另一類不能重復，把不能重復的元素看作“客”，能重復的元素看作“店”，再利用乘法原理直接求解。例10 七名學生爭奪五項冠軍，每項冠軍只能由一人獲得，獲得冠軍的可能的種數有（ ）A. B. C D.分析：因同一學生可以同時奪得n項冠軍，故學生可重復排列，將七名學生看作7家“店”，五項冠軍看作5名“客”，每個“客”有7種住宿法，由乘法原理得 種。注：對此類問題，常有疑惑，為什么不是 呢？用分步計數原理看，5是步驟數，自然是指數?；啬夸?牛牛文庫文檔分享住店法解決“

16、允許重復排列問題”要注意區(qū)分兩類元素： 重排問題求冪策略例.把6名實習生分配到7個車間實習,共有 多少種不同的分法解:完成此事共分六步:把第一名實習生分配 到車間有 種分法.7把第二名實習生分配 到車間也有7種分法，依此類推,由分步計數原理共有 種不同的排法回目錄 牛牛文庫文檔分享重排問題求冪策略例.把6名實習生分配到7個車間實習,共有解:多排問題直排策略例7.8人排成前后兩排,每排4人,其中甲乙在 前排,丁在后排,共有多少排法解:8人排前后兩排,相當于8人坐8把椅子,可以 把椅子排成一排.先在前4個位置排甲乙兩個特殊元素有_種,再排后4個位置上的特殊元素有_種,其余的5人在5個位置上任意排列

17、有_種,則共有_種.前排后排一般地,元素分成多排的排列問題,可歸結為一排考慮,再分段研究.回目錄 牛牛文庫文檔分享多排問題直排策略例7.8人排成前后兩排,每排4人,其中甲乙在小集團問題 牛牛文庫文檔分享小集團問題 牛牛文庫文檔分享小集團問題先整體局部策略例9.用1,2,3,4,5組成沒有重復數字的五位數 其中恰有兩個偶數夾1,在兩個奇數之 間,這樣的五位數有多少個？解：把,當作一個小集團與排隊共有_種排法，再排小集團內部共有_種排法，由分步計數原理共有_種排法.31524小集團小集團排列問題中，先整體后局部，再結合其它策略進行處理?；啬夸?牛牛文庫文檔分享小集團問題先整體局部策略例9.用1,2

18、,3,4,5組成沒有重.計劃展出10幅不同的畫,其中1幅水彩畫,幅油畫,幅國畫, 排成一行陳列,要求同一品種的必須連在一起，并且水彩畫不在兩端，那么共有陳列方式的種數為_2. 5男生和女生站成一排照像,男生相鄰,女生也相鄰的排法有_種回目錄 牛牛文庫文檔分享.計劃展出10幅不同的畫,其中1幅水彩畫,2. 5男生和元素相同問題隔板策略應用背景：相同元素的名額分配問題 不定方程的正整數解問題隔板法的使用特征：相同的元素分成若干部分，每部分至少一個 牛牛文庫文檔分享元素相同問題隔板策略應用背景：相同元素的名額分配問題隔板法的元素相同問題隔板策略例.有10個運動員名額，在分給7個班，每班至少一個,有多

19、少種分配方案？ 解：因為10個名額沒有差別，把它們排成一排。相鄰名額之間形成個空隙。在個空檔中選個位置插個隔板，可把名額分成份，對應地分給個班級，每一種插板方法對應一種分法共有_種分法。一班二班三班四班五班六班七班將n個相同的元素分成m份（n，m為正整數）,每份至少一個元素,可以用m-1塊隔板，插入n個元素排成一排的n-1個空隙中，所有分法數為回目錄 牛牛文庫文檔分享元素相同問題隔板策略例.有10個運動員名額，在分給7個班，每練 習（1）將10個學生干部的培訓指標分配給7個不同的班級，每班至少分到一個名額，不同的分配方案共有 （ ）種。（2）不定方程 的正整數解共有（ ）組回目錄 牛牛文庫文檔

20、分享練 習（1）將10個學生干部的培訓指標分配給7個不同的班級，平均分組問題除法策略“分書問題” 牛牛文庫文檔分享平均分組問題除法策略“分書問題” 平均分組問題除法策略例12. 6本不同的書平均分成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)一種分法,故共 有 種分法?；啬夸?牛牛

21、文庫文檔分享平均分組問題除法策略例12. 6本不同的書平均分成3堆,每堆1 將13個球隊分成3組,一組5個隊,其它兩組4 個隊, 有多少分法？2.10名學生分成3組,其中一組4人, 另兩組3人 但正副班長不能分在同一組,有多少種不同 的分組方法 （1540）3.某校高二年級共有六個班級，現從外地轉 入4名學生，要安排到該年級的兩個班級且每班安排2名，則不同的安排方案種數為_ 回目錄 牛牛文庫文檔分享1 將13個球隊分成3組,一組5個隊,其它兩組42.10名分清排列、組合、等分的算法區(qū)別例 (1)今有10件不同獎品,從中選6件分給甲一件,乙二件和丙三件,有多少種分法? (2) 今有10件不同獎品

22、, 從中選6件分給三人,其中1人一件1人二件1人三件, 有多少種分法?(3) 今有10件不同獎品, 從中選6件分成三份,每份2件, 有多少種分法? 解：（1） （2）(3)回目錄 牛牛文庫文檔分享分清排列、組合、等分的算法區(qū)別例 (1)今有10件不同獎品練習 (1)今有10件不同獎品,從中選6件分成三份, 二份各1件,另一份4件, 有多少種分法?(2) 今有10件不同獎品,從中選6件分給甲乙丙三人,每人二件有多少種分法?解: (1)(2)回目錄 牛牛文庫文檔分享練習解: (1)(2)回目錄 牛先選后排問題 牛牛文庫文檔分享先選后排問題 牛牛文庫文檔分享八.排列組合混合問題先選后排策略例.有5個

23、不同的小球,裝入4個不同的盒內, 每盒至少裝一個球,共有多少不同的裝 法.解:第一步從5個球中選出2個組成復合元共 有_種方法.再把5個元素(包含一個復合 元素)裝入4個不同的盒內有_種方法.根據分步計數原理裝球的方法共有_解決排列組合混合問題,先選后排是最基本的指導思想.此法與相鄰元素捆綁策略相似嗎?回目錄 牛牛文庫文檔分享八.排列組合混合問題先選后排策略例.有5個不同的小球,裝入4練習題一個班有6名戰(zhàn)士,其中正副班長各1人現從中選4人完成四種不同的任務,每人完成一種任務,且正副班長有且只有1人參加,則不同的選法有_ 種192回目錄 牛牛文庫文檔分享練習題一個班有6名戰(zhàn)士,其中正副班長各1人

24、192回目錄www3 名醫(yī)生和 6 名護士被分配到 3 所學校為學生體檢,每校分配 1 名醫(yī)生和 2 名護士,不同的分配方法共有多少種?先選后排問題的處理方法 解法一：先組隊后分校（先分堆后分配）回目錄 牛牛文庫文檔分享3 名醫(yī)生和 6 名護士被分配到 3 所學校為學生體檢,每 為支援西部開發(fā),有3名教師去銀川市三所學校任教,每校分配1人,不同的分配方法共有_種(用數字作答).練習改為4名教師？改為5名教師？回目錄 牛牛文庫文檔分享 為支援西部開發(fā),有3名教師去銀川市三所學校任教,每校分配1有甲、乙、丙三項任務,甲需2人承擔,乙、丙各需1人承擔.從10人中選派4人承擔這三項任務,不同的選法共有多少種?回目錄 牛牛文庫文檔分享有甲、乙、丙三項任務,甲需2人承擔,乙、丙各需1人承擔.從11、有甲、乙、丙三項工程，甲需要 2 人承擔，乙、丙各需 1 人承擔，從 10 人中選派 4 人承擔這三項任務，不同的承擔方法共有_種；2、某辦公室有 5 人辦公，現要排一個周輪值表，每人至少一天，其中甲不能在周六和周日，且甲肯定值兩天，則不同的排表方