排列組合問題解法

排列組合問題的求解策略楊昌葉求解排列組合的綜合問題，一般是先選元素（組合），后排列，按元素的性質(zhì)“分類”和按事件發(fā)生連續(xù)性過程“分步”，在計(jì)數(shù)時(shí)注意不重復(fù)，不遺漏。常見的解題策略有以下幾種：特殊位置（或元素）優(yōu)先安排例1.從6人中選4人分別到巴黎、倫敦、悉尼、莫斯科四個(gè)城市游覽，要求每個(gè)城市有一人游覽，每人只游覽一個(gè)城市，且這6人中，甲、乙兩人不去巴黎游覽，則不同的選擇方案共有（）A.300種B.240種C.144種D.96種（05年福建卷）解析：因?yàn)榧?、乙不去巴黎，故從其?人選1人去巴黎有q種方法，再從剩余5人中選3人去其余3市，有A|種方法，所以共有方案q人；=240（種），故選（B）。合理分類與準(zhǔn)確分步例2.從集合｛O,P，Q，R，S｝與｛0，1，2，3,4，5，6,7，8，9｝中各任取2個(gè)元素排成一排（字母和數(shù)字均不能重復(fù)），每排中字母P、Q和數(shù)字0至多只出現(xiàn)一個(gè)的不同排法種數(shù)是（用數(shù)字作答）。（05年浙江卷）解析：（1）每排中只有數(shù)字0的排法有C9C2A4；（2）每排中只有字母P或Q的排法都有C1C92A4；（3）每排中無數(shù)字0，字母P、Q的排法有C2C2A4。所以不同的排法種數(shù)共有：（C1C2+2C1C2+C2C2）A4=84249339394排列、組合混合問題先選元（組合）后排列例3.四個(gè)不同的小球放入編號(hào)為1，2,3,4的四個(gè)盒子中，則恰有一個(gè)空盒的放法共種（用數(shù)字作答）。（全國高考）解析：先將4個(gè)球分成3組，每組至少1個(gè)（即必有一組為2個(gè)），分法有C2種，然后4再將這3組球放入4個(gè)盒子中每盒最多裝一組，則恰有一個(gè)空盒的放法種數(shù)為C：A3=144（種）。正難則反、等價(jià)轉(zhuǎn)化例4.在由數(shù)字0，1，2,3,4,5所組成的沒有重復(fù)數(shù)字的四位數(shù)中，不能被5整除的數(shù)共有個(gè)。（05年全國卷）解析：用排除法解決。（1）總的四位數(shù)有C1A3；55（2）個(gè)位數(shù)字為0的四位數(shù)有A3；5（3）個(gè)位數(shù)字為5的四位數(shù)有C：A2。所以符合條件的四位數(shù)個(gè)數(shù)共有：CiA3-A3-C1A2=300-60-48=192另解：直接求有4x4xA2法（想一想，為什么？）相鄰問題捆綁處理例5.四棱錐的8條棱代表8種不同的化工產(chǎn)品，有公共頂點(diǎn)的兩條棱代表的化工產(chǎn)品放在同一倉庫是危險(xiǎn)的，沒有公共頂點(diǎn)的兩條棱代表的化工產(chǎn)品放在同一倉庫是安全的，現(xiàn)打算用編號(hào)為①、②、③、④的4個(gè)倉庫存放這8種化工產(chǎn)品，那么安全存放的不同放法種數(shù)為（）A,96B.48C.24D.0（05年江蘇卷）解析：在四棱錐S-ABCD中（1）先把安全的產(chǎn)品捆綁在一起有2種方法（SA，CD），（SB，AD），（SC，AB），（SD，BC）；（SA，BC），（SB，CD），（SC，AD），（SD，AB）。（2）四組產(chǎn)品放在4個(gè)編號(hào)不同的倉庫里有A：種，所以安全存放的方法共有：2A4=2x24=48（種）。4故選（B）。不相鄰問題插空處理例6.用1，2,3,4,5,6,7,8組成沒有重復(fù)數(shù)字的八位數(shù)，要求1與2相鄰，3與4相鄰，5與6相鄰，而7與8不相鄰，這樣的八位數(shù)共有個(gè)（用數(shù)字作答）。（05年遼寧卷）解析：此題是捆綁法和插空法的綜合應(yīng)用問題。把相鄰的兩個(gè)數(shù)捆成一捆，分成四個(gè)空，然后再將7與8插進(jìn)空中有A：種插法；而相鄰的三捆都有A；種排法，再它們之間又有A33種排序方法。故這樣的八位數(shù)共有：A2A2A2A3A2=8x6x12=576（個(gè)）22234定序問題排除處理例7.在7名運(yùn)動(dòng)員中選4名運(yùn)動(dòng)員組成接力隊(duì)，參加4x100接力賽，那么甲、乙兩人都不跑中間兩棒的安排方法共有多少種？解析：先從7人中任選4人接力有A；種方法，排除甲和乙跑中間棒的2A；A3種方法，中小學(xué)教育網(wǎng)www.ehappystudy.^^mhfzp://www.ehappys/快樂學(xué)習(xí)，盡在中小學(xué)教育網(wǎng)TOC\o"1-5"\h\z但甲、乙二人都跑中間的減了兩次，故再加上二人都跑中間棒的A2A2種方法，即25A4-2AiA3+A2A2=400（種）另解：直接求有A|A2法（想一想，為什么？）分排問題直接處理例8.有兩排座位，前排11個(gè)座位，后排12個(gè)座位，現(xiàn)安排2人就座，規(guī)定前排中間的3個(gè)座位不能坐，并且這2人不左右相鄰，那么不同排法的種數(shù)是（）A.234B.346C.350D.363（04年遼寧卷）解析：在排列問題中，站若干排與站一排一樣，故一共可坐的位子有20個(gè)，2個(gè)人就座方法數(shù)為A2，還需排除兩人左右相鄰的情況，把可坐的20座位排成連續(xù)一行（一排末位B20與二排首位C相接），任兩個(gè)座位看成一個(gè)整體，即相鄰的坐法有A19A2，但這其中包括B、C相鄰與E、F（前排中間3座的左E、右F）相鄰，而這種相鄰在實(shí)際中是不相鄰的，還應(yīng)再加上2A;。所以不同排法的種數(shù)為：A20-A19A;+2A;=346故選B。構(gòu)造模型例9.6本不同的書，按照以下要求處理，各有幾種方法？（1）一堆一本，一堆兩本，一堆三本；（2）甲得一本，乙得兩本，丙得三本；（3）一人得一本，一人得二本，一人得三本；（4）平均分給甲、乙、丙三人；（5）平均分成三堆。解析：本問題中的每一小題都提出了一種類型問題，要搞清類型的歸屬。（1）屬非均勻分組問題，先在6本書中任取一本，作為一堆，有C1種取法，再從余下的5本書中任取2本作為一堆，有C5種取法，最后余下的3本作為一堆有C3種取法，故共有分法：C1C2C3=60（種）653（2）屬非均勻定向分配問題，與（1）同解，因每種分組方法僅對(duì)應(yīng)一種分配方法，故也共有分法60種。（3）屬非均勻不定向分配問題，由（1）知分成三堆有60種，但每一種分組方法又有A33種不同的分配方案，故共有分法60A3=360（種）。（4）屬均勻定向分配問題，3個(gè)人一個(gè)一個(gè)地來取書，甲取有亳種，乙再去取有C2種，最后余下的歸丙有C2種，故共有2C2C2C2=90（種）642（5）屬均勻分組問題，把6本不同的書分成三堆，每堆2本與把6本不同的書分給甲、乙、丙三，每人2本的區(qū)別在于后者相當(dāng)于把6本不同的書，平均分成三堆后再把分得的三堆書分給甲、乙、丙三個(gè)人，因此設(shè)把6本不同的書平均分成三堆的方法有x種，由（4）知把6本不同的書分給甲、乙、丙三人，每人2本的方法有C2C2C2種。642所以xA3=C2C2C23642則x=15（種）10.用“樹型”圖處理例10.設(shè)ABCDEF為正六邊形，一只青蛙開始在頂點(diǎn)A處，它每次可隨意地跳到相鄰兩個(gè)頂點(diǎn)之一，若在5次之內(nèi)跳到D點(diǎn)，則停止跳動(dòng)，若在5次之內(nèi)不能到達(dá)D點(diǎn)，則跳完5次也停止跳動(dòng)，那么這只青蛙從開始到停止，可能出現(xiàn)的不同跳法的種數(shù)是（）B.8A.6

C.1