排列組合問題的基本類型及解題方法

1、精選優(yōu)質(zhì)文檔-傾情為你奉上精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)專心-專注-專業(yè)精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)排列組合問題的基本類型及解題方法解決排列組合問題要講究策略，首先要認(rèn)真審題，弄清楚是排列(有序)還是組合(無序)，還是排列與組合混合問題。其次，要抓住問題的本質(zhì)特征，準(zhǔn)確合理地利用兩個(gè)基本原則進(jìn)行“分類與分步”。加法原理的特征是分類解決問題，分類必須滿足兩個(gè)條件：類與類必須互斥(不相容)，總類必須完備(不遺漏)；乘法原理的特征是分步解決問題，分步必須做到步與步互相獨(dú)立，互不干擾并確保連續(xù)性。分類與分步是解決排列組合問題的最基本的思想策略，在實(shí)際操作中往往是“步”與“類”

2、交叉，有機(jī)結(jié)合，可以是類中有步，也可以是步中有類。 以上解題思路分析，可以用順口溜概括為：審明題意，排（組）分清；合理分類，用準(zhǔn)加乘；周密思考，防漏防重；直接間接，思路可循；元素位置，特殊先行；一題多解，檢驗(yàn)真?zhèn)巍?（一）特殊元素的“優(yōu)先安排法”對于特殊元素的排列組合問題，一般先考慮特殊元素，再考慮其他元素的安排。在操作時(shí)，針對實(shí)際問題，有時(shí)“元素優(yōu)先”，有時(shí)“位置優(yōu)先”。 例1：這五個(gè)數(shù)字，組成沒有重復(fù)數(shù)字的三位數(shù)，其中偶數(shù)共有幾個(gè)？ 解法一：(元素優(yōu)先)分兩類：第一類，含，在個(gè)位有種，在十位有種；第二類，不含，有種。 故共有種。 注：在考慮每一類時(shí)，又要優(yōu)先考慮個(gè)位。 解法二：(位置優(yōu)先)

3、分兩類：第一類，在個(gè)位有種；第二類，不在個(gè)位，先從兩個(gè)偶數(shù)中選一個(gè)放個(gè)位，再選一個(gè)放百位，最后考慮十位，有種。 故共有 （二）總體淘汰法對于含有否定詞語的問題，還可以從總體中把不符合要求的除去，此時(shí)應(yīng)注意既不能多減也不能少減，例如在例中也可以用此法解答：個(gè)數(shù)字組成三位數(shù)的全排列為，排好后發(fā)現(xiàn)不能在首位，而且和不能排在末尾，這兩種不合題意的排法要除去，故有個(gè)偶數(shù)（三）合理分類與準(zhǔn)確分步解含有約束條件的排列組合問題，應(yīng)按元素的性質(zhì)進(jìn)行分類，事情的發(fā)生的連續(xù)過程分步，做到分類標(biāo)準(zhǔn)明確，分布層次清楚，不重不漏例2：個(gè)人從左到右站成一排，甲不站排頭，乙不站第二個(gè)位置，不同的站法有解：由題意，可先安排甲，

4、并按其進(jìn)行分類討論：（1）若甲在第二個(gè)位置上，則剩下的四人可自由安排，有種方法；（2）若甲在第三個(gè)或第四個(gè)位置上，則根據(jù)分布計(jì)數(shù)原理不同的站法有種站法；再根據(jù)分類計(jì)數(shù)原理，不同的站法共有：種（四）相鄰問題：捆綁法對于某些元素要求相鄰排列的問題，可先將相鄰元素捆綁成整體并看作一個(gè)元素再與其它元素進(jìn)行排列，同時(shí)對相鄰元素內(nèi)部進(jìn)行自排。例3：個(gè)男生個(gè)女生排成一列，要求女生排一起，共有幾種排法？ 解：先把個(gè)女生捆綁為一個(gè)整體再與其他個(gè)男生全排列。同時(shí)，個(gè)女生自身也應(yīng) 全排列。由乘法原理共有種。 （五）不相鄰問題用“插空法”對于某幾個(gè)元素不相鄰的排列問題，可先將其他元素排好，再將不相鄰的元素在已排好的元

5、素之間及兩端的空隙之間插入即可（注意有時(shí)候兩端的空隙的插法是不符合題意的）.例4：個(gè)男生個(gè)女生排成一列，要求女生不相鄰且不可排兩頭，共有幾種排法？ 解：先排無限制條件的男生，女生插在個(gè)男生間的個(gè)空隙，由乘法原理共有種。 注意：分清“誰插入誰”的問題。要先排無限制條件的元素，再插入必須間隔的元素；數(shù)清可插的位置數(shù)；插入時(shí)是以組合形式插入還是以排列形式插入要把握準(zhǔn)。 例5： 馬路上有編號為的盞路燈，現(xiàn)要關(guān)掉其中的三盞，但不能同時(shí)關(guān)掉相鄰的兩盞或三盞，也不能關(guān)兩端的路燈，則滿足要求的關(guān)燈方法有幾種？ 解：由于問題中有盞亮盞暗，又兩端不可暗，故可在盞亮的個(gè)間隙中插入個(gè)暗的即可，有種。 （六）順序固定問

6、題用“除法”或選位不排或先定后插對于某幾個(gè)元素順序一定的排列問題，可先把這幾個(gè)元素與其他元素一起進(jìn)行排列，然后用總排列數(shù)除以這幾個(gè)元素之間的全排列數(shù)。或先在總位置中選出順序一定元素的位置而不參加排列，然后對其它元素進(jìn)行排列。也可先放好順序一定元素，再一一插入其它元素。 例6： 人參加百米跑，若無同時(shí)到達(dá)終點(diǎn)的情況，則甲比乙先到有幾種情況？ 解法一：先人全排有種，由于全排中有甲、乙的全排種數(shù)，而這里只有種是符合要求的，故要除以定序元素的全排列種，所以有種。 解法二：先在個(gè)位置中選個(gè)位置放定序元素(甲、乙)有種，再排列其它人有，由乘法原理得共有種。 解法三：先固定甲、乙，再插入另三個(gè)中的第一人有種

7、方法，接著插入第二人有種方法，最后插入第三人有種方法。由乘法原理得共有種。 （七）“小團(tuán)體”排列，先“團(tuán)體”后整體對于某些排列問題中的某些元素要求組成“小團(tuán)體”時(shí)，可先按制約條件“組團(tuán)”并視為一個(gè)元素再與其它元素排列。 例7:四名男歌手與兩名女歌手聯(lián)合舉行一場演唱會(huì)，演出的出場順序要求兩名女歌手之間有兩名男歌手，則出場方案有幾種？ 解：先從四名男歌手中選人排入兩女歌手之間進(jìn)行“組團(tuán)”有種，把這個(gè)“女男男女”小團(tuán)體視為人再與其余男進(jìn)行排列有種，由乘法原理，共有種 （八）分排問題用“直排法”把個(gè)元素排成若干排的問題，若沒其他的特殊要求，可用統(tǒng)一排成一排的方法來處理例8：個(gè)人坐兩排座位，第一排坐人，

8、第二排坐人，則有種排法解：個(gè)人，可以在前后兩排隨意就座，沒有其他的限制條件，故兩排可以看成一排來處理，所以不同的坐法有(九)逐步試驗(yàn)法 如果題中附加條件增多,直接解決困難,用試驗(yàn)法尋找規(guī)律有時(shí)也是行之有效的方法例9：將數(shù)字填入標(biāo)號為的四個(gè)方格內(nèi)，每個(gè)方格填一個(gè)，則每個(gè)方格的標(biāo)號與所填的數(shù)字均不相同的填法種數(shù)有種。解：此題考查排列的定義，由于附加條件較多，解法較為復(fù)雜，可用試驗(yàn)法逐步解決第一方格內(nèi)可填或或如填，則第二方格內(nèi)可填或或若第二方格內(nèi)填,則第三方格內(nèi)只能填，第四方格內(nèi)填若第二方格填，則第三方格應(yīng)填，第四方格應(yīng)填同理，若第二方格填，則第三、四方格應(yīng)分別填，。因而第一方格填共有種方法。同理，

9、第一格填或也各有種，所以一共有種方法。（十）探索規(guī)律法對于情況復(fù)雜，不易發(fā)現(xiàn)其規(guī)律的問題需要仔細(xì)分析，探索出其中規(guī)律，再予以解決。例10：從到的自然數(shù)中，每次取出不同的兩個(gè)數(shù)，使他們的和大于，則不同的取法種數(shù)有種。解：此題的數(shù)字較多，情況也不一樣，需要分析摸索其規(guī)律。為方便，兩個(gè)加數(shù)中較小的為被加數(shù)，為被加數(shù)的有種；同理，為被加數(shù)的有種；為被加數(shù)的有種；為被加數(shù)的有種；為被加數(shù)的有種；但為被加數(shù)的只有種；為被加數(shù)的只有種；為被加數(shù)的只有種，故不同的區(qū)法有：種。（十一）“住店”問題解決“允許重復(fù)排列”的問題要注意區(qū)分兩類元素：一類元素可重復(fù)，另一類元素不能重復(fù)。把不能重復(fù)的元素看著“客”，能重復(fù)

10、的元素看著“店”，再利用分步計(jì)數(shù)原理直接求解的方法稱為“住店法”。例11：名學(xué)生爭奪五項(xiàng)冠軍，獲得冠軍的可能種數(shù)是種。解：應(yīng)同一學(xué)生可同時(shí)奪得項(xiàng)冠軍，故學(xué)生可重復(fù)排列，將名學(xué)生看著家“店”，五項(xiàng)冠軍看著名“客”，每個(gè)客有種住宿方法，由分步計(jì)數(shù)原理得種。（十二）特征分析法有約束條件的排數(shù)問題，必須緊扣題中所提供的數(shù)字和結(jié)構(gòu)特征，進(jìn)行推理，分析求解。例12：由六個(gè)數(shù)可組成多少個(gè)無重復(fù)且是的倍數(shù)的五位數(shù)？解：分析數(shù)字的特征：的倍數(shù)的數(shù)既是的倍數(shù)，又是的倍數(shù)。其中的倍數(shù)又滿足“各個(gè)數(shù)位上的數(shù)字之和是的倍數(shù)”的特征。而且是的倍數(shù)，從個(gè)數(shù)字中取個(gè)，使之和還是的倍數(shù)，則所去掉的數(shù)字只能是或。因而可以分兩類討

11、論：第一類，所排的五位數(shù)不含，即由作數(shù)碼；首先從三個(gè)中任選一個(gè)作個(gè)位數(shù)字有種，然后其余個(gè)數(shù)字在其他數(shù)位上的全排列有，所以；第二類，所排的五位數(shù)不含，即由作數(shù)碼，依上法有，故種。（十三）相同元素進(jìn)盒，用檔板分隔 例13：張參觀公園的門票分給個(gè)班，每班至少張，有幾種選法？ 解：這里只是票數(shù)而已，與順序無關(guān)，故可把張票看成個(gè)相同的小球放入個(gè)不同的盒內(nèi)，每盒至少球，可先把球排成一列，再在其中個(gè)間隔中選個(gè)位置插入塊“檔板”分成格(構(gòu)成個(gè)盒子)有種方法。 注：檔板分隔模型專門用來解答同種元素的分配問題。（十四）個(gè)數(shù)不少于盒子編號數(shù)，先填滿再分隔例14：個(gè)相同的球放入編號為的盒子內(nèi)，盒內(nèi)球數(shù)不少于編號數(shù)，有

12、幾種不同的放法？ 解：先用個(gè)球按編號數(shù)“填滿”各盒(符合起碼要求),再把個(gè)球放入個(gè)盒內(nèi)即可,可用塊檔板與個(gè)球一起排列(即為兩類元素的排列問題),有種。 （十五）不同元素進(jìn)盒，先分堆再排列對于不同的元素放入幾個(gè)不同的盒內(nèi)，當(dāng)有的盒內(nèi)有不小于個(gè)元素時(shí)，不可分批進(jìn)入，必須先分堆再排入。 例15：個(gè)老師分配到個(gè)班搞活動(dòng)，每班至少一個(gè)，有幾種不同的分法？ 解：先把位老師分堆，有兩類：分布有種和分布有種，再排列到個(gè)班里有種，故共有種。 注意：不同的老師不可分批進(jìn)入同一個(gè)班，須一次到位(否則有重復(fù)計(jì)數(shù))。即“同一盒內(nèi)的元素必須一次進(jìn)入”。 （十六）兩類元素的排列，用組合選位法例16：級樓梯，要求步走完，每步

13、可跨一級，也可跨兩級，問有幾種不同的跨法？ 解：由題意知，有步跨單級，步跨兩級，所以只要在步中任意選步跨兩級即可。故有種跨法。 注意：兩類元素的排列問題涉及面很廣，應(yīng)予重視。 例17： 沿圖中的網(wǎng)格線從頂點(diǎn)到頂點(diǎn)，最短的路線有幾條？ 解：每一種最短走法，都要走三段“|”線和四段“”線，這是兩類元素不分順序的排列問題。故有或種走法。 例18： 從個(gè)班中選人組成校籃球隊(duì)(無任何要求)，有幾種選法？ 解：這個(gè)問題與例有區(qū)別，雖仍可看成塊“檔板”將個(gè)球分成格(構(gòu)成個(gè)盒子)，是球與檔板兩類元素不分順序的排列問題。但某些盒子中可能沒有球，故塊“檔板”與個(gè)球一樣也要參與排成一列而占位置，故有種選法。 注意：

14、怎樣把問題等價(jià)轉(zhuǎn)化為“兩類元素的排列”問題是解題的關(guān)鍵。 （十七）元素交叉問題 集合法所謂集合思想，就是運(yùn)用集合的概念、邏輯語言、運(yùn)算、圖形等來解決數(shù)學(xué)問題或非純數(shù)學(xué)問題的思想方法。利用集合思想解決排列組合問題，可以使抽象的數(shù)學(xué)問題具體化，也可以防止在分類或分步的過程中出現(xiàn)重復(fù)和遺漏問題。在利用集合思想求解時(shí)，要借助于下列一組公式，它們?nèi)菀子梦氖蠄D來驗(yàn)證。1. 德摩根定律：2. 容斥原理：若用表示有限集合A中的元素的個(gè)數(shù)，則對于任意集合A、B，有=。特殊的，。下面舉例說明：例1. 從6名運(yùn)動(dòng)員中選出4名參加接力賽，如果甲不跑第一棒，乙不跑第四棒，共有多少種不同的參賽方法？解：設(shè)全集，根據(jù)容斥原理得參賽方法共有：答：共有252種不同的參賽方法。例2. 高一（3）班的學(xué)生中，參加課外語文小組的有20人，參加數(shù)學(xué)小組的有22人，既參加語文又參加數(shù)學(xué)小組的有10人，既未參加語文又未參加數(shù)學(xué)小組的有15人，問高一（3）班共有多少學(xué)生？解：設(shè)由容斥原理及德摩根定律：答：高一（3）班共有學(xué)生47人。例3. 由數(shù)字1、2、3、4、5可以組成多