排列組合-課件

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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