排列組合-課件

《排列組合-課件》由會員分享，可在線閱讀，更多相關(guān)《排列組合-課件（37頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,解排列組合問題的十七種常用策略,1,解排列組合問題的十七種常用策略1,解決排列組合綜合性問題的一般過程如下,:,1.,認(rèn)真審題弄清要做什么事,2.,怎樣做才能完成所要做的事,即采取分步還,是分類,或是分步與分類同時進(jìn)行,確定分多,少步及多少類。,3.,確定每一步或每一類是排列問題,(,有序,),還是,組合,(,無序,),問題,元素總數(shù)是多少及取出多,少個元素,.,解決排列組合綜合性問題，往往類與步交,叉，因此必須掌握一些常用的解題策略,2,解決排列組合綜合性問題的一般過程如下:1.認(rèn)真審題弄清要做什,一,.

2、,特殊元素和特殊位置優(yōu)先策略,例,1.,由,0,1,2,3,4,5,可以組成多少個沒有重復(fù)數(shù)字,五位奇數(shù),.,解,:,由于末位和首位有特殊要求,應(yīng)該優(yōu)先安,排,以免不合要求的元素占了這兩個位置,先排末位共有,_,然后排首位共有,_,最后排其它位置共有,_,由分步計數(shù)原理得,=288,位置分析法和元素分析法是解決排列組合問題最常用也是最基本的方法,若以元素分析為主,需先安排特殊元素,再處理其它元素,.,若以位置分析為主,需先滿足特殊位置的要求,再處理其它位置。若有多個約束條件，往往是考慮一個約束條件的同時還要兼顧其它條件,3,一.特殊元素和特殊位置優(yōu)先策略例1.由0,1,2,3,4,5,7,種不

3、同的花種在排成一列的花盆里,若兩種葵花不種在中間，也不種在兩端的花盆里，問有多少不同的種法？,練習(xí)題,4,7種不同的花種在排成一列的花盆里,若兩種葵花不種在中間，也不,二,.,相鄰元素捆綁策略,例,2.7,人站成一排,其中甲乙相鄰且丙丁相,鄰,共有多少種不同的排法,.,甲,乙,丙,丁,由分步計數(shù)原理可得共有,種不同的排法,=480,解：可先將甲乙兩元素捆綁成整體并看成,一個復(fù)合元素，同時丙丁也看成一個,復(fù)合元素，再與其它元素進(jìn)行排列，,同時對相鄰元素內(nèi)部進(jìn)行自排。,要求某幾個元素必須排在一起的問題,可以用,捆綁法來解決問題,.,即將需要相鄰的元素合并,為一個元素,再與其它元素一起作排列,同時,

4、要注意合并元素內(nèi)部也必須排列,.,5,二.相鄰元素捆綁策略例2.7人站成一排,其中甲乙相鄰且丙,三,.,不相鄰問題插空策略,例,3.,一個晚會的節(jié)目有,4,個舞蹈,2,個相聲,3,個,獨(dú)唱,舞蹈節(jié)目不能連續(xù)出場,則節(jié)目的出,場順序有多少種？,解,:,分兩步進(jìn)行第一步排,2,個相聲和,3,個獨(dú)唱共,有,種，,第二步將,4,舞蹈插入第一步排,好的,6,個元素中間包含首尾兩個空位共有,種,不同的方法,由分步計數(shù)原理,節(jié)目的,不同順序共有,種,相,相,獨(dú),獨(dú),獨(dú),元素相離問題可先把沒有位置要求的元素進(jìn)行排隊再把不相鄰元素插入中間和兩端,6,三.不相鄰問題插空策略例3.一個晚會的節(jié)目有4個舞蹈,2個相,

5、某班新年聯(lián)歡會原定的,5,個節(jié)目已排成節(jié)目單，開演前又增加了兩個新節(jié)目,.,如果將這兩個新節(jié)目插入原節(jié)目單中，且兩個新節(jié)目不相鄰，那么不同插法的種數(shù)為（）,30,練習(xí)題,某人射擊,8,槍，命中,4,槍，,4,槍命中恰好有,3,槍連在一起的情形的不同種數(shù)為（）,20,7,某班新年聯(lián)歡會原定的5個節(jié)目已排成節(jié)目單，開演前又增加了兩個,四,.,定序問題倍縮空位插入策略,例,4.7,人排隊,其中甲乙丙,3,人順序一定共有多,少不同的排法,解,:,(,倍縮法,),對于某幾個元素順序一定的排列,問題,可先把這幾個元素與其他元素一起,進(jìn)行排列,然后用總排列數(shù)除以這幾個元,素之間的全排列數(shù),則共有不同排法種數(shù)

6、,是：,（,空位法）設(shè)想有,7,把椅子讓除甲乙丙以外,的四人就坐共有,種方法，其余的三個,位置甲乙丙共有,種坐法，則共有,種,方法,1,思考,:,可以先讓甲乙丙就坐嗎,?,8,四.定序問題倍縮空位插入策略例4.7人排隊,其中甲乙丙3人順,（插入法,),先排甲乙丙三個人,共有,1,種排法,再,把其余,4,四人依次插入共有,方法,定序問題可以用倍縮法，還可轉(zhuǎn)化為占位插,空模型處理,練習(xí)題,10,人身高各不相等,排成前后排，每排,5,人,要,求從左至右身高逐漸增加，共有多少排法？,4*5*6*7,9,（插入法)先排甲乙丙三個人,共有1種排法,再定序問題可以用倍,大家學(xué)習(xí)辛苦了，還是要堅持,繼續(xù)保持安

7、靜,10,大家學(xué)習(xí)辛苦了，還是要堅持繼續(xù)保持安靜10,五,.,重排問題求冪策略,例,5.,把,6,名實(shí)習(xí)生分配到,7,個車間實(shí)習(xí),共有,多少種不同的分法,解,:,完成此事共分六步,:,把第一名實(shí)習(xí)生分配,到車間有,種分法,.,7,把第二名實(shí)習(xí)生分配,到車間也有,7,種分法，,依此類推,由分步計,數(shù)原理共有 種不同的排法,允許重復(fù)的排列問題的特點(diǎn)是以元素為研究,對象，元素不受位置的約束，可以逐一安排,各個元素的位置，一般地,n,不同的元素沒有限,制地安排在,m,個位置上的排列數(shù)為 種,n,m,11,五.重排問題求冪策略例5.把6名實(shí)習(xí)生分配到7個車間實(shí)習(xí),共,某,8,層大樓一樓電梯上來,8,名乘

8、客,他們,到各自的一層下電梯,下電梯的方法,（）,練習(xí)題,12,某8層大樓一樓電梯上來8名乘客,他們練習(xí)題12,六,.,多排問題直排策略,例,7.8,人排成前后兩排,每排,4,人,其中甲乙在,前排,丁在后排,共有多少排法,解,:8,人排前后兩排,相當(dāng)于,8,人坐,8,把椅子,可以,把椅子排成一排,.,先在前,4,個位置排甲乙兩,個特殊元素有,_,種,再排后,4,個位置上的,特殊元素有,_,種,其余的,5,人在,5,個位置,上任意排列有,_,種,則共有,_,種,.,前排,后排,一般地,元素分成多排的排列問題,可歸結(jié)為一排考慮,再分段研究,.,13,六.多排問題直排策略例7.8人排成前后兩排,每排

9、4人,其中甲,七,.,排列組合混合問題先選后排策略,例,8.,有,5,個不同的小球,裝入,4,個不同的盒內(nèi),每盒至少裝一個球,共有多少不同的裝,法,.,解,:,第一步從,5,個球中選出,2,個組成復(fù)合元共,有,_,種方法,.,再把,5,個元素,(,包含一個復(fù)合,元素,),裝入,4,個不同的盒內(nèi)有,_,種方法,.,根據(jù)分步計數(shù)原理裝球的方法共有,_,解決排列組合混合問題,先選后排是最基本,的指導(dǎo)思想,.,此法與,相鄰元素捆綁策略相似,嗎,?,14,七.排列組合混合問題先選后排策略例8.有5個不同的小球,裝入,練習(xí)題,一個班有,6,名戰(zhàn)士,其中正副班長各,1,人,現(xiàn)從中選,4,人完成四種不同的任務(wù)

10、,每人,完成一種任務(wù),且正副班長有且只有,1,人,參加,則不同的選法有,_,種,192,15,練習(xí)題一個班有6名戰(zhàn)士,其中正副班長各1人19215,八,.,小集團(tuán)問題先整體局部策略,例,9.,用,1,2,3,4,5,組成沒有重復(fù)數(shù)字的五位數(shù),其中恰有兩個偶數(shù)夾,1,這兩個奇數(shù)之,間,這樣的五位數(shù)有多少個？,解：把,當(dāng)作一個小集團(tuán)與排隊,共有,_,種排法，再排小集團(tuán)內(nèi)部共有,_,種排法，由分步計數(shù)原理共有,_,種排法,.,3,1245,小集團(tuán),小集團(tuán)排列問題中，先整體后局部，再結(jié)合其它策略進(jìn)行處理。,16,八.小集團(tuán)問題先整體局部策略例9.用1,2,3,4,5組成沒,.,計劃展出,10,幅不同的

11、畫,其中,1,幅水彩畫,幅油畫,幅國畫,排成一行陳列,要求同一,品種的必須連在一起，并且水彩畫不在兩,端，那么共有陳列方式的種數(shù)為,_,2.5,男生和女生站成一排照像,男生相鄰,女,生也相鄰的排法有,_,種,17,.計劃展出10幅不同的畫,其中1幅水彩畫,2.5男生和,九,.,元素相同問題隔板策略,例,10.,有,10,個運(yùn)動員名額，在分給,7,個班，每,班至少一個,有多少種分配方案？,解：因為,10,個名額沒有差別，把它們排成,一排。相鄰名額之間形成個空隙。,在個空檔中選個位置插個隔板，,可把名額分成份，對應(yīng)地分給個,班級，每一種插板方法對應(yīng)一種分法,共有,_,種分法。,一班,二班,三班,四

12、班,五班,六班,七班,將,n,個相同的元素分成,m,份（,n,，,m,為正整數(shù)）,每份至少一個元素,可以用,m-1,塊隔板，插入,n,個元素排成一排的,n-1,個空隙中，所有分法數(shù)為,18,九.元素相同問題隔板策略例10.有10個運(yùn)動員名額，在分給7,練習(xí)題,10,個相同的球裝,5,個盒中,每盒至少一個，有多少裝法？,19,練習(xí)題10個相同的球裝5個盒中,每盒至少一個，有多少裝法？1,十,.,正難則反總體淘汰策略,例,11.,從,0,1,2,3,4,5,6,7,8,9,這十個數(shù)字中取出三,個數(shù)，使其和為不小于,10,的偶數(shù),不同的,取法有多少種？,解：這問題中如果直接求不小于,10,的偶數(shù)很,

13、困難,可用總體淘汰法。,這十個數(shù)字中有,5,個偶數(shù),5,個奇數(shù),所取的三個數(shù)含有,3,個偶數(shù)的取法有,_,只含有,1,個偶數(shù)的取法有,_,和為偶數(shù)的取法共有,_,再淘汰和小于,10,的偶數(shù)共,_,符合條件的取法共有,_,9,013,015,017,035,213,215,024,413,026,+,-9,+,有些排列組合問題,正面直接考慮比較復(fù)雜,而它的反面往往比較簡捷,可以先求出它的反面,再從整體中淘汰,.,20,十.正難則反總體淘汰策略例11.從0,1,2,3,4,5,6,1.,我們班里有,58,位同學(xué),從中任抽,5,人,正、,副班長、團(tuán)支部書記至少有一人在內(nèi)的,抽法有多少種,?,練習(xí)題,

14、2.,從,4,名男生和,3,名女生中選出,4,人參加某個座 談會，若這,4,人中必須既有男生又有女生，則不同的選法共有,_,34,21,1.我們班里有58位同學(xué),從中任抽5人,正、練習(xí)題2.從4名,十一,.,平均分組問題除法策略,例,12.6,本不同的書平均分成,3,堆,每堆,2,本共有,多少分法？,解,:,分三步取書得 種方法,但這里出現(xiàn),重復(fù)計數(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),

15、共有 種取法,而,這些分法僅是,(AB,CD,EF),一種分法,故共,有 種分法。,平均分成的組,不管它們的順序如何,都是一種情況,所以分組后要一定要除以,(n,為均分的組數(shù),),避免重復(fù)計數(shù)。,22,十一.平均分組問題除法策略例12.6本不同的書平均分成3堆,1,將,13,個球隊分成,3,組,一組,5,個隊,其它兩組,4,個隊,有多少分法？,2.,某校高二年級共有六個班級，現(xiàn)從外地轉(zhuǎn) 入,4,名學(xué)生，要安排到該年級的兩個班級且每班安排,2,名，則不同的安排方案種數(shù)為,_,23,1 將13個球隊分成3組,一組5個隊,其它兩組42.某校高,十二,.,合理分類與分步策略,例,13.,在一次演唱會上

16、共,10,名演員,其中,8,人能,能唱歌,5,人會跳舞,現(xiàn)要演出一個,2,人,唱歌,2,人伴舞的節(jié)目,有多少選派方法,?,解：,10,演員中有,5,人只會唱歌，,2,人只會跳舞,3,人為全能演員。,以只會唱歌的,5,人是否,選上唱歌人員為標(biāo)準(zhǔn)進(jìn)行研究,只會唱,的,5,人中沒有人選上唱歌人員共有,_,種,只會唱的,5,人中只有,1,人選上唱歌人,員,_,種,只會唱的,5,人中只有,2,人,選上唱歌人員有,_,種，由分類計數(shù),原理共有,_,種。,+,+,24,十二.合理分類與分步策略例13.在一次演唱會上共10名演員,本題還有如下分類標(biāo)準(zhǔn)：,*,以,3,個全能演員是否選上唱歌人員為標(biāo)準(zhǔn),*,以,3,個全能演員是否選上跳舞人員為標(biāo)準(zhǔn),*,以只會跳舞的,2,人是否選上跳舞人員為標(biāo)準(zhǔn),都可經(jīng)得到正確結(jié)果,解含有約束條件的排列組合問題，可按元素,的性質(zhì)進(jìn)行分類，按事件發(fā)生的連續(xù)過程分,步，做到標(biāo)準(zhǔn)明確。分步層次清楚，不重不,漏，分類標(biāo)準(zhǔn)一旦確定要貫穿于解題過程的,始終。,25,本題還有如下分類標(biāo)準(zhǔn)：解含有約束條件的排列組合問題，可按元素,練習(xí)題,2.,3,成人,2,小孩乘船游玩,1,號船最多乘,3