排列組合問題的解法第三計(jì).doc

每周一計(jì)第三計(jì)排列組合問題的解法解決排列組合問題要講究策略，用順口溜概括為：審明題意，排（組）分清；合理分類，用準(zhǔn)加乘；周密思考，防漏防重；直接間接，思路可循；元素位置，特殊先行；一題多解，檢驗(yàn)真?zhèn)巍?（一）.特殊元素、特殊位置的“優(yōu)先安排法”對(duì)于特殊元素的排列組合問題，一般先考慮特殊元素，再考慮其他元素的安排。在操作時(shí)，針對(duì)實(shí)際問題，有時(shí)“元素優(yōu)先”，有時(shí)“位置優(yōu)先”。 例1： 0、2、3、4、5這五個(gè)數(shù)字，組成沒有重復(fù)數(shù)字的三位數(shù)，其中偶數(shù)共有幾個(gè)？ 解法一：(元素優(yōu)先)分兩類：第一類，含0：0在個(gè)位有 種，0在十位有 種；第二類，不含0：有種。 故共有（ ）種。 注：在考慮每一類時(shí)，又要優(yōu)先考慮個(gè)位。 解法二：(位置優(yōu)先)分兩類：第一類，0在個(gè)位有 種；第二類，0不在個(gè)位，先從兩個(gè)偶數(shù)中選一個(gè)放個(gè)位，再選一個(gè)放百位，最后考慮十位，有 種。 故共有 練習(xí)：甲、乙、丙、丁、戊、己六位同學(xué)選四人組隊(duì)參加4*100m接力賽，其中甲、乙不跑最后一棒，共有多少種不同的安排方法？（此題可有元素優(yōu)先和位置優(yōu)先兩個(gè)角度兩種解法，但位置優(yōu)先則更簡單）（二）排除法 對(duì)于含有否定詞語的問題，還可以從總體中把不符合要求的除去.例：個(gè)人從左到右站成一排，甲不站排頭，乙不站第二個(gè)位置，不同的站法有=78種（三）.相鄰問題“捆綁法”對(duì)于某些元素要求相鄰排列的問題，可先將相鄰元素捆綁成整體并看作一個(gè)元素再與其它元素進(jìn)行排列，同時(shí)對(duì)相鄰元素內(nèi)部進(jìn)行自排。例3： 5個(gè)男生3個(gè)女生排成一列，要求女生排一起，共有幾種排法？ 解：先把3個(gè)女生捆綁為一個(gè)整體再與其他5個(gè)男生全排列。同時(shí)，3個(gè)女生自身也應(yīng)全排列。由乘法原理共有種。 （四）。不相鄰問題“插空法”對(duì)于某幾個(gè)元素不相鄰的排列問題，可先將其他可相鄰元素排好，再將不相鄰的元素在已排好的元素之間及兩端的空隙之間插入即可（注意有時(shí)候兩端的空隙的插法是不符合題意的）例4： 5個(gè)男生3個(gè)女生排成一列，要求女生不相鄰且不可排兩頭，共有幾種排法？ 解：先排無限制條件的男生，女生插在5個(gè)男生間的4個(gè)空隙，由乘法原理共有 種。 注意：分清“誰插入誰”的問題。要先排可相鄰的元素，再插入不相鄰的元素；數(shù)清可插的位置數(shù)；插入時(shí)是以組合形式插入還是以排列形式插入要把握準(zhǔn)。 例5： 馬路上有編號(hào)為1、2、3、9的9盞路燈，現(xiàn)要關(guān)掉其中的三盞，但不能同時(shí)關(guān)掉相鄰的兩盞或三盞，也不能關(guān)兩端的路燈，則滿足要求的關(guān)燈方法有幾種？ 解：由于問題中有6盞亮3盞暗，又兩端不可暗，故可在6盞亮的5個(gè)間隙中插入3個(gè)暗的即可，有種。 （五）。定序問題選位不排對(duì)于某幾個(gè)元素順序一定的排列問題，可先在總位置中選出順序一定元素的位置而不參加排列，然后對(duì)其它元素進(jìn)行排列。 例6： 5人參加百米跑，若無同時(shí)到達(dá)終點(diǎn)的情況，則甲比乙先到有幾種情況？ 解：先在5個(gè)位置中選2個(gè)位置放定序元素(甲、乙)有 種，再排列其它3人有 ，由乘法原理得共有 =60種。 （六）“小團(tuán)體”排列，先“團(tuán)體”后整體對(duì)于某些排列問題中的某些元素要求組成“小團(tuán)體”時(shí)，可先按制約條件“組團(tuán)”并視為一個(gè)元素再與其它元素排列。 例7:四名男歌手與兩名女歌手聯(lián)合舉行一場演唱會(huì)，演出的出場順序要求兩名女歌手之間有兩名男歌手，則出場方案有幾種？ 解：先從四名男歌手中選2人排入兩女歌手之間進(jìn)行“組團(tuán)”有 種，把這個(gè)“女男男女”小團(tuán)體視為1人再與其余2男進(jìn)行排列有 種，由乘法原理，共有 種 （七）分排問題用“直排法”把n個(gè)元素排成若干排的問題，若沒其他的特殊要求，可用統(tǒng)一排成一排的方法來處理例：7個(gè)人坐兩排座位，第一排坐3人，第二排坐4人，則有種排法解：可以在前后兩排隨意就座，故兩排可以看成一排來處理，所以不同的坐法有 (八)列舉法 如果題中附加條件增多,直接解決困難,用列舉法尋找規(guī)律有時(shí)也是行之有效的方法例9：從到的自然數(shù)中，每次取出不同的兩個(gè)數(shù)，使他們的和大于，則不同的取法有 種。解：此題的數(shù)字較多，情況也不一樣，需要分析摸索其規(guī)律。為方便，兩個(gè)加數(shù)中較小的為被加數(shù)，為被加數(shù)的有種；同理，為被加數(shù)的有種；為被加數(shù)的有種；為被加數(shù)的有種；為被加數(shù)的有種；但為被加數(shù)的只有種；為被加數(shù)的只有種；為被加數(shù)的只有種，故不同的區(qū)法有：（）（）種。（九）元素可重復(fù)的排列求冪法。解決“允許重復(fù)排列”的問題要注意區(qū)分兩類元素：一類元素可重復(fù)，另一類元素不能重復(fù)。把不能重復(fù)的元素看成“客”，能重復(fù)的元素看成“店”，再利用分步計(jì)數(shù)原理直接求解的方法稱為“住店法”。例10：名學(xué)生爭奪五項(xiàng)冠軍，獲得冠軍的可能種數(shù)是種。解：應(yīng)同一學(xué)生可同時(shí)奪得n項(xiàng)冠軍，故學(xué)生可重復(fù)排列，將名學(xué)生看成家“店”，五項(xiàng)冠軍看成名“客”，每個(gè)客有種住宿方法，由分步計(jì)數(shù)原理得75種。（十）特征分析法 有約束條件的排數(shù)問題，必須緊扣題中所提供的數(shù)字和結(jié)構(gòu)特征，進(jìn)行推理，分析求解。例11：由、六個(gè)數(shù)可組成多少個(gè)無重復(fù)且是的倍數(shù)的五位數(shù)？解：分析數(shù)字的特征：的倍數(shù)的數(shù)既是的倍數(shù)，又是的倍數(shù)。其中的倍數(shù)又滿足“各個(gè)數(shù)位上的數(shù)字之和是的倍數(shù)”的特征。而且是的倍數(shù)，從個(gè)數(shù)字中取個(gè)，使之和還是的倍數(shù)，則所去掉的數(shù)字只能是或。因而可以分兩類討論：第一類，所排的五位數(shù)不含，即由、作數(shù)碼；首先從、三個(gè)中任選一個(gè)作個(gè)位數(shù)字有 種，然后其余個(gè)數(shù)字在其他數(shù)位上的全排列有 ，所以；第二類，所排的五位數(shù)不含6，即由1、2、3、4、5作數(shù)碼，依上法有，故 種。（十一）名額分配問題用隔板法 例12： 10張參觀公園的門票分給5個(gè)班，每班至少1張，有幾種選法？ 解：這里只是票數(shù)而已，與順序無關(guān)，故可把10張票看成10個(gè)相同的小球放入5個(gè)不同的盒內(nèi)，每盒至少1球，可先把10球排成一列，再在其中9個(gè)間隔中選4個(gè)位置插入4塊“檔板”分成5格(構(gòu)成5個(gè)盒子)有 種方法。 注：檔板分隔模型專門用來解答同種元素的分配問題。（十二）個(gè)數(shù)不少于盒子編號(hào)數(shù)，先填滿再分隔例13：15個(gè)相同的球放入編號(hào)為1、2、3的盒子內(nèi)，盒內(nèi)球數(shù)不少于編號(hào)數(shù)，有幾種不同的放法？ 解：（解法一）先用6個(gè)球按編號(hào)數(shù)“填滿”各盒(符合起碼要求),再把9個(gè)球放入3個(gè)盒內(nèi)即可,可用2塊檔板與9個(gè)球一起排列(即為兩類元素的排列問題),有 種。 （解法二）先在2號(hào)盒和3號(hào)盒分別放入一個(gè)球和兩個(gè)球，則問題轉(zhuǎn)化為12個(gè)相同的球放入3個(gè)盒子內(nèi)，每個(gè)盒子至少放入一個(gè)球，有多少種不同的放法？（十三）不同元素進(jìn)盒，先分堆再排列對(duì)于不同的元素放入幾個(gè)不同的盒內(nèi)，當(dāng)有的盒內(nèi)有不小于2個(gè)元素時(shí)，不可分批進(jìn)入，必須先分堆再排入。 例14： 5個(gè)老師分配到3個(gè)班搞活動(dòng)，每班至少一個(gè)，有幾種不同的分法？ 解：先把5位老師分3堆，有兩類：3、1、1分布有 種和1、2、2分布有 種，再排列到3個(gè)班里有 種，故共有。 注意：不同的老師不可分批進(jìn)入同一個(gè)班，須一次到位(否則有重復(fù)計(jì)數(shù))。即“同一盒內(nèi)的元素必須一次進(jìn)入”。 （十四）兩類元素的排列，用組合選位法例15：10級(jí)樓梯，要求7步走完，每步可跨一級(jí)，也可跨兩級(jí)，問有幾種不同的跨法？ BA解：由題意知，有4步跨單級(jí)，3步跨兩級(jí)，所以只要在7步中任意選3步跨兩級(jí)即可。故有 種跨法。 注意：兩類元素的排列問題涉及面很廣，應(yīng)予重視。 例16： 沿圖中的網(wǎng)格線從頂點(diǎn)A到頂點(diǎn)B，最短的路線有幾條？ 解：每一種最短走法，都要走三段“|”線和四段“”線，這是兩類元素不分順序的排列問題。故有 或 種走法。 例17： 從5個(gè)班中選10人組成校籃球隊(duì)(無任何要求)，有幾種選法？ 解：這個(gè)問題與例12有區(qū)別，雖仍可看成4塊“檔板”將10個(gè)球分成5格(構(gòu)成5個(gè)盒子)，是球與檔板兩類元素不分順序的排列問題。但某些盒子中可能沒有球，故4塊“檔板”與10個(gè)球一樣也要參與排成一列而占位置，故有 種選法。 注意：怎樣把問題等價(jià)轉(zhuǎn)化為“兩類元素的排列”問題是解題的關(guān)鍵。 （十五）利用對(duì)應(yīng)思想轉(zhuǎn)化法。對(duì)應(yīng)思想是教材中滲透的一種重要的解題方法，它可以將復(fù)雜的問題轉(zhuǎn)化為簡單問題處理。例18： 長方體上任意兩頂點(diǎn)的連線段中，異面直線共有多少對(duì)？分析：任意一對(duì)異面直線必然對(duì)應(yīng)四個(gè)頂點(diǎn)，而這四個(gè)頂點(diǎn)不共面，構(gòu)成四面體，每個(gè)四面體上有3對(duì)異面直線，因此把求異面直線的問題轉(zhuǎn)化成求可以構(gòu)成多少個(gè)四面體的問題。解：例19：如圖，AOB的兩邊分別有異于O的4個(gè)點(diǎn)A1、A2、A3、A4和5個(gè)點(diǎn)B1、B2、B3、B4、B5，連接AiBj（i=1,2,3,4，j=1,2,3,4,5）構(gòu)成的線段中，有多少個(gè)交點(diǎn)在AOB內(nèi)？OABA1A2A3A4B1B2B3B4B5分析：在AOB內(nèi)相交的兩條線段對(duì)應(yīng)一個(gè)四邊形的兩對(duì)角線，所以求交點(diǎn)個(gè)數(shù)問題轉(zhuǎn)化為求四邊形個(gè)數(shù)問題。解：=60（十六）取鞋問題先雙后支例20：從五雙鞋中任取四支，恰有一雙的取法有多少種？解：先從五雙中取一雙，有種，再從余下4雙中選兩雙，從每雙的兩只中選擇1支，有。共有種。（十七）涂色問題抓住關(guān)鍵