排列組合方法

捆綁法：（相鄰問題）在特定要求的條件下，將幾個相關(guān)元素當(dāng)作一個元素來考慮，待整體排好之后再考慮它們“局部”的排列?它主要用于解決“元素相鄰問題”，例如，一般地，n個不同元素排成一列，要求其中某m（m-n）個元素必相鄰的排列有An：mtl■Am個?其中An-m+l Amn-m+1是一個“整體排列”，而Am則是“局部排列”.又例如①有n個不同座位，A、B兩個不能相鄰，則有排列法種數(shù)為ATA?-1■AI?有n件不同商品，若其中A、B排在一起有An-l■AI?有n件不同商品，若其中有二件要排在一起有An■An-l?注：①區(qū)別在于①是確定的座位，有AI種；而③的商品地位相同，是從n件不同商品任取的2個，有不確定性.例16名同學(xué)排成一排，其中甲、乙兩人必須排在一起的不同排法有（ ）種A.720 B.360 C.240 D.120A5解：因甲、乙兩人要排在一起，故將甲、乙兩人捆在一起視作一人，與其余四人進行全排列有5種排法;A2 A5A2甲、乙兩人之間有2種排法。由分步計數(shù)原理可知，共有5 2=240種不同排法，選C。插空法：（不相鄰問題/固定順序）先把一般元素排列好，然后把待定元素插排在它們之間或兩端的空檔中，此法主要解決“元素不相鄰問題”.An—m■Am例如：n個元素全排列，其中m個元素互不相鄰，不同的排法種數(shù)為多少？n-mn-m+1（插空法），當(dāng)n+1n-m+1>m,即ms2時有意義.例2要排一張有6個歌唱節(jié)目和4個舞蹈節(jié)目的演出節(jié)目單，任何兩個舞蹈節(jié)目不得相鄰，有多少不同的排法？（只要求寫出式子，不必計算）A6解：先將6個歌唱節(jié)目排好，其不同的排法為6種；這6個歌唱節(jié)目的空隙及兩端共7個位置中再排4A4 A4A6個舞蹈節(jié)目，有7種排法。由分步計數(shù)原理可知，任何兩個舞蹈節(jié)目不得相鄰的排法為7 6種。占位法：從元素的特殊性上講，對問題中的特殊元素應(yīng)優(yōu)先排列，然后再排其他一般元素；從位置的特殊性上講，對問題中的特殊位置應(yīng)優(yōu)先考慮，然后再排其他剩余位置?即采用“先特殊后一般”的解題原則.例5.7人排成一行，分別求出符合下列要求的不同排法的種數(shù)。

（1）甲排中間；（2）甲不排兩端；（3）甲，乙相鄰；（4）甲在乙的左邊（不要求相鄰）；（5）甲，乙，丙連排；（6）甲，乙，丙兩兩不相鄰。解：（1）甲排中間屬“特元特位”，優(yōu)先安置，只有一種站法，其余6人任意排列，故共有：1xA6/6=720種不同排法。（2） 甲不排兩端，亦屬于“特元特位”問題，優(yōu)先安置甲在中間五個位置上任何一個位置則有5種，其余6人可任意排列有種，故共有C1/5xA6/6=3600種不同排法。（3） 甲、乙相鄰，屬于'捆綁法”，將甲、乙合為一個'元素”，連同其余5人共6個元素任意排列，再由甲、乙組內(nèi)排列，故共有A6/6xA2/2=1440種不同的排法。（4） 甲在乙的左邊?？紤]在7人排成一行形成的所有排列中：“甲在乙左邊”與“甲在乙右邊”的排法是 對應(yīng)的，在不要求相鄰時，各占所有排列的一半，故甲在乙的左邊的不同排法共有A7/7/2=2520種。（5） 甲、乙、丙連排，亦屬于某些元素必須在一起的排列，禾U用“捆綁法”，先將甲、乙、丙合為一個“元素”,連同其余4人共5個“元素”任意排列，現(xiàn)由甲、乙、丙交換位置，故共有A3/3xA5/5=360種不同排法。（6） 甲、乙、丙兩兩不相鄰，屬于某些元素必須不在一起的分離排列，用“插空法”，先將甲、乙、丙外的4人排成一行，形成左、右及每兩人之間的五個“空”。再將甲、乙、丙插入其中的三個“空”，故共有A4/4xA5/3=1440種不同的排法。調(diào)序法：當(dāng)某些元素次序一定時，可用此法?解題方法是：先將n個元素進行全排列有An種，m（mYn）個元Am素的全排列有Am種，由于要求m個元素次序一定，因此只能取其中的某一種排法，可以利用除法起到去An n—調(diào)序的作用，即若n個元素排成一列，其中m個元素次序一定，共有Am種排列方法.例如：n個元素全排列，其中m個元素順序不變，共有多少種不同的排法？n/解法一：（逐步插空法）（m+1）（m+2）...n=n！/m!；解法二：（比例分配法）nm.平均法:若把kn若把kn個不同元素平均分成k組，每組n個，共有Cn-Cn…Cn kn (k1)n nAkkC4=3例如：從1,2,3,4中任取2個元素將其平均分成2組有幾種分法？有2!（平均分組就用不著管組與組之間的順序問題了）182C10/2!、20C8C2182C10/2!、20又例如將20名運動員平均分成兩組，其中兩名種子選手必在一組的概率是多少？（注意：分組與插空綜合.例如：n個元素全排列，其中某m個元素互不相鄰且順序不變，共有多少種排法？An一m?A m/Am -有n-mn-m+1m，當(dāng)n-m+1>m,即ms2時有意義.隔板法：常用于解有幾組正整數(shù)解的問題.>0例如：Xi+X2+X3+X4=12的正整數(shù)解的組數(shù)就可建立組合模型將12個完全相同的球排成一列，在它們之XXXX間形成11個空隙中任選三個插入3塊摸板，把球分成4個組?每一種方法所得球的數(shù)目依次為1'2’3’4顯然X1+X2+X3+X4=12，故（"1顯2’X3'X4）是方程的一組解?反之，方程的任何一組解（Y1'Y2’Y3’Y4），對應(yīng)著惟一的一種在12個球之間插入隔板的方式（如圖所示） ?卜?*!???X1X2 X3X4故方程的解和插板的方法 對應(yīng).即方程的解的組數(shù)等于插隔板的方法數(shù)C13?注意：若為非負數(shù)解（>=0）的x個數(shù)，即用A1叫”叫中AI等于X+1，有X1+X2+x3…+Xn=A=A1一1+A2一1+…an一1=A，進而轉(zhuǎn)化為求a的正整數(shù)解的個數(shù)為CA+N?定位問題：從n個不同元素中每次取出k個不同元素作排列，規(guī)定某r個元素都包含在內(nèi)，并且都排在某r個指定ArAk-r位置則有rN-r?例如：從n個不同元素中，每次取出m個元素的排列，其中某個元素必須固定在（或不固定在）某一位置上，共有多少種排法？AM~1 AM—Am-1Am+A1?Am-1固定在某一位置上：N-1；不在某一位置上：NN-1或N-1M-1N-1（一類是不取出特殊元素AMa,有N-1，一類是取特殊元素a,有從m-1個位置取一個位置，然后再從n-1個元素中取m-1，這與用插空法解決是一樣的）指定元素排列組合問題.從n個不同元素中每次取出k個不同的元素作排列（或組合），規(guī)定某r個元素都包含在內(nèi)。先C后A策略，排列；組合C；CN-R?從n個不同元素中每次取出k個不同元素作排列（或組合），規(guī)定某r個元素都不包含在內(nèi)。先C后ACkAk Ck策略，排列Cn-rK;組合CN-r?

iii從n個不同元素中每次取出k個不同元素作排列（或組合），規(guī)定每個排列（或組合）都只包含某r個CsCk-sAk CsCk-s元素中的s個元素。先C后A策略，排列 rn-rk；組合rn-r.三、定序問題縮倍法例3信號兵把紅旗與白旗從上到下掛在旗桿上表示信號?，F(xiàn)有3面紅旗、2面白旗，把這5面旗都掛上去，可表示不同信號的種數(shù)是 （用數(shù)字作答）。A5解：5面旗全排列有5種掛法，由于3面紅旗與2面白旗的分別全排列均只能算作一次的掛法，故共有A5 5—A3A2不同的信號種數(shù)是3 2=10（種）。評法：在排列問題中限制某幾個元素必須保持一定順序稱為定序問題。這類問題用縮小倍數(shù)的方法求解比較方便快捷。五、有序分配問題逐分法例5有甲、乙、丙三項任務(wù)，甲需由2人承擔(dān)，乙、丙各需由1人承擔(dān)，從10人中選派4人承擔(dān)這三項任務(wù)，不同的選法共有（ ）種D.5040A.1260 B.2025 C.2520D.5040解：先從10人中選出2人承擔(dān)甲項任務(wù)，再從剩下8人中選1人承擔(dān)乙項任務(wù)，最后從剩下7人中選1C2CiCi人承擔(dān)丙項任務(wù)。根據(jù)分步計數(shù)原理可知，不同的選法共有1087=2520種，故選C。評注：有序分配問題是指把元素按要求分成若干組，常采用逐步下量分組法求解。六、多元問題分類法例6由數(shù)字0，1,2,3,4,5組成沒有重復(fù)數(shù)字的六位數(shù)，其中個位數(shù)字小于十位數(shù)字的共有（ ）A.210個 B.300個 C.464個解：按題意個位數(shù)只可能是0，1，2,3,4共5種情況,符合題意的分別有A5,5AiA1A24 3 3,A1A1A3,AiAiA3,AiA3人 人斗亠A，+AiA1A3 +A1A1A3 +AiA1A33 3 3 2 3 3 3 3個。合并總計，共有5 4 3 3 3 3 3 2 3 3+AiA33 3=300（個），故選B。評注：元素多，取出的情況也多種，可按結(jié)果要求，分成互不相容的幾類情況分別計算，最后總計。Ai另解：先排首位，不用0，有5種方法；再同時排個位和十位，由于個位數(shù)字小于十位數(shù)字，即順序固定,C2 A3 AiC2A3故有5種方法；最后排剩余三個位置，有3種排法。故共有符合要求的六位數(shù)55 3=300（個）。七、交叉問題集合法例7從6名運動員中選出4名參加4X100米接力賽，如果甲不跑第一棒，乙不跑第四棒，共有多少種不同的參賽方法？

解：設(shè)全集U=｛6人中任取4人參賽的排列｝,A=｛甲跑第一棒的排列｝,B=｛乙跑第四棒的排列｝，根據(jù)求集合元素個數(shù)的公式可得參賽方法共有card(U)—card(A)—card(B)+card(AAB)=A4—A—A+A26 5 5 4=252(種)。評注：某些排列組合問題幾部分之間有交集，可用集合中求元素個數(shù)的公式：card(AUB)=card(A)+card(B)—card(AAB).._來求解。八、定位問題優(yōu)限法例8計劃展出10幅不同的畫，其中1幅水彩畫、4幅油畫、5幅國畫，排成一行陳列，要求同一品種的畫必須連在一起，并且水彩畫不放在兩端，那么不同的陳列方式有( )A.A4A54 5A.A4A54 5B.A3A4A53 4 5C.C3A4A5A2解：先把3種品種的畫看成整體，而水彩畫不能放在頭尾，故只能放在中間，則油畫與國畫有2種放法。A2A4A5再考慮油畫之間與國畫之間又可以各自全排列。故總的排列的方法為2 4 5種，故選D。評注：所謂“優(yōu)限法”，即有限制條件的元素(或位置)在解題時優(yōu)先考慮。九、多排問題單排法例9兩排座位，第一排有3個座位，第二排有5個座位，若8名學(xué)生入座(每人一座位)，則不同的坐法種數(shù)為()C5C3 A1C5C3 A5A3 A8A.88 B.288 C.8 8 D.8A8解：此題分兩排坐，實質(zhì)上就是8個人坐在8個座位上，故有8種坐法，所以選D。評注：把元素排成幾排的問題，可歸結(jié)為一排考慮。十、至少問題間接法例10從4臺甲型和5臺乙型電視機中任意取出3臺,其中至少要甲型與乙型電視機各一臺，則不同的取法共有()種A.140 B.80 C.70 I解析：在被取出的3臺中，若不含甲型或不含乙型的抽取方法均不合題意，故符合題意的取法有C3—C3—C3 井％9 4 5=70種，選C。評注：含“至多”或“至少”的排列組合問題，通常用分類法。本題所用的解法是間接法，即排除法(總體去雜)，適用于反面情況明確且易于計算的情況。十一、選排問題先取后排法例11四個不同的小球放入編號為1，2，3，4的四個盒子中，則恰有一個空盒的放法共有 種(用數(shù)字作答)。C2解：先從四個小球中取兩個放在一起，4種不同的取法；再把取出的兩個小球與另外兩個小球看作二堆,A C2A3=144并分別放入四個盒子中的三個盒子中，有4種不同的放法。依據(jù)分步計數(shù)原理，共有4 4 種不同的方法。評注：這是一道排列組合的混合應(yīng)用題目，這類問題的一般解法是先取(組合)后排(排列)。本題正確求解的關(guān)鍵是把四個小球中的兩個視為一個整體，如果考慮不周，就會出現(xiàn)重復(fù)和遺漏的錯誤。十二、部分符合條件淘汰法例12四面體的頂點及各棱中點共有10個點，在其中取4個不共面的點，不同的取法共有( )A.150種 B.147種 C.144種D.141種C4解：10個點中取4個點共有10種取法，其中同一側(cè)面內(nèi)的6個點中任取4個點必共面，這樣的面共有4個；又同一條棱上的3個點與對棱的中點也四點共面，共有6個面；再各棱中點共6個點中，取四點共面C4-4C4-6-3的平面有3個。故符合條件4個點不共面的取法共有10 6 =141(種)，故選D。評注：在選取總數(shù)中，只有一部分符合條件，可從總數(shù)中減去不符合條件的個數(shù)，即為所求。應(yīng)該指出的是，上述所介紹的適用不同要求的各種方法并不是絕對的，對于同一問題有時會有多種方法，這時要認真思考和分析，靈活選取最佳方法。[排列組合]“甲不在排頭乙不在排尾”問題通解給出“甲不在排頭乙不在排尾問題”的其中一種解法，其它解法請參考論壇中有關(guān)排列組合的帖子。為了讓大家看清楚，我就把過程寫詳細些，反正我發(fā)帖子也不多。核心思路：題目中一般要求的是甲不站在某一位，乙不站在某一位，我們偏讓這個元素站在這一位，用全排列減去這幾種情況，即為所求。公式：全排列-mx固定排列1+nX固定排列2(一般情況，n=m-1，但還是要看具體情況)其中“固定排列1”是所有固定排列的分步計算情況，“固定排列2”是所有固定排列的總計計算情況，m表示有幾種固定排列的情況(這個很重要，要得出正確結(jié)果首先要確定有幾種情況)這個公式看著繞人，用字母表示我覺的也不好記，下面我們從例題來熟悉它。例題1：將5列車停在5條不同的軌道上，其中a列車不停在第一軌道上，b列車不停在第二軌道上，那么不同的停放方法有()(A)120種(B)96種(C)78種(D)72種解析：本題有2種固定排列，即甲站第一軌，即乙站第二軌，m值取25輛車全排列，p(5,5)a站第一軌，還剩4條軌道，P(4,4)b站第二軌，還剩4條軌道，P(4,4)a站第一軌，b站第二軌，還剩3條軌道，P(3,3)列式p(5,5)-2*P(4,4))+(2-1)*P(3,3)=78注意：P(3,3)是加上多減去的情況，因為1和2同時在1,2位時重復(fù)計算了兩次，應(yīng)該加上一次例題2：7人一排，甲不在排頭或排尾，同時乙不在中間的不同排法有多少？解析：注意本題有3種固定排列，即甲站排頭，甲站排尾，乙站中間，m值取3。[1]7個人全排列，P(7,7)【2】甲站排頭，剩下6個人，P(6,6)[3]甲站排尾，剩下6個人，P(6,6)【4】乙站中間，剩下6個人，P(6,6)甲站排頭，乙站中間，剩下5個人，P(5,5)甲站排尾，乙站中間，剩下5個人，P(5,5)列式p(7,7)-3*P(6,6)+(3-1)*P(5,5)=3120例3:6個學(xué)生和2個老師排成一排照相，2個老師站中間，學(xué)生甲不站排頭，學(xué)生乙不站排尾，共有多少種不同的排法？6個學(xué)生全排列，p(6,6)甲站排頭，P(5,5)乙站排尾，P(5,5)甲站排頭，乙站排尾，P(4,4)⑸再安排老師,p(2,2)列式【p(6,6)-2*P(5,5)+(2-1)P(4,4)】*p(2,2)=1008說明：加上P(4,4)是減去兩次P(5,5)時多減去的情況例題4：8個人一排，甲不在第一位或第二位，同時乙不在第三或第四位的不同排法有多少？解析：本題有4種固定排列，甲不在第一位或第二位，乙不在第三或第四位，注意關(guān)鍵字“或”，m值取4.，8個學(xué)生全排列，p(8,8)甲站第一位，P(7,7)甲站第二位，P(7,7)乙站第三位，P(7,7)乙站第四位，P(7,7)⑹甲站第一位，乙站第三位，P(6,6)甲站第一位，乙站第四位，P(6,6)甲站第二位，乙站第三位，P(6,6)甲站第二位，乙站第四位，P(6,6)p(8,8)-4*P(7,7)+4*P(6,6)=23040說明：加上4次P(6,6)是減去4次P(7,7)時多減去的情況，所以說，具體情況還得具體分析例題5：從6人中選4人分別到巴黎、倫敦、悉尼、莫斯科四個城市游覽，要求每個城市有一人游覽，每人只游覽一個城市，且這6人中甲、乙兩人不去巴黎游覽，則不同的選擇方案共有(B)A.300種B.240種C.144種D.96種6個人選4個去旅行，C(4,6)*P(4,4)=360[注意：這當(dāng)中已經(jīng)包含了甲、乙可能出去的情況]甲去巴黎游覽，還剩3個旅游名額，C(3,5)*P(3,3)=60乙去巴黎游覽，還剩3個旅游名額，C(3,5)*P(3,3)=60C(4,6)*P(4,4)-2*C(3,5)*P(3,3)=240問題：本題為什么不加上多減去的情況呢？哈哈，因為一個城市只能去一個人，就算甲乙同時出現(xiàn)，也不會2個人都去巴黎，所以沒有多計算的情況。最后再娛樂一道題目，例1：將數(shù)字1、2、3、4填入標(biāo)號為甲、乙、丙、丁的四個方格里，每格填一個數(shù)字，其中1不在第一位，2不在第二位，3不在第三位，4不在第4位，則所填的數(shù)字都不相同的填法共有（B）A.6種B.9種C.11種D.23種大家想想吧，該怎么做？II.排列組合常見解題策略：特殊元素優(yōu)先安排策略；②合理分類與準確分步策略；③排列、組合混合問題先選后排的策略（處理排列組合綜合性問題一般是先選元素，后排列）；④正難則反，等價轉(zhuǎn)化策略；⑤相鄰問題插空處理策略；⑥不相鄰問題插空處理策略；⑦定序問題除法處理策略；⑧分排問題直排處理的策略；⑨“小集團”排