第80煉排列組合的常見模型

1、第 80 煉 排列組合的常見模型一、基礎(chǔ)知識：（一）處理排列組合問題的常用思路：1、特殊優(yōu)先：對于題目中有特殊要求的元素，在考慮步驟時優(yōu)先安排，然后再去處理無要求的元素。例如：用 0,1,2,3,4 組成無重復(fù)數(shù)字的五位數(shù)，共有多少種排法？解：五位數(shù)意味著首位不能是0，所以先處理首位，共有4 種選擇，而其余數(shù)位沒有要求，只需將剩下的元素全排列即可，所以排法總數(shù)為N4A4496 種2、尋找對立事件：如果一件事從正面入手，考慮的情況較多，則可以考慮該事的對立面，再用全部可能的總數(shù)減去對立面的個數(shù)即可。例如：在 10 件產(chǎn)品中，有7 件合格品， 3 件次品。從這10 件產(chǎn)品中任意抽出3 件，至少有一

2、件次品的情況有多少種解：如果從正面考慮，則“至少1 件次品”包含1 件， 2 件， 3 件次品的情況，需要進行分類討論， 但如果從對立面想，則只需用所有抽取情況減去全是正品的情況即可，列式較為簡單。 NC103C7385 （種）3、先取再排 （先分組再排列） ：排列數(shù)Anm 是指從n 個元素中取出m 個元素， 再將這m 個元素進行排列。 但有時會出現(xiàn)所需排列的元素并非前一步選出的元素，所以此時就要將過程拆分成兩個階段，可先將所需元素取出，然后再進行排列。例如： 從 4 名男生和3 名女生中選3 人，分別從事 3 項不同的工作， 若這 3 人中只有一名女生，則選派方案有多少種。解：本題由于需要先

3、確定人數(shù)的選取，再能進行分配（排列），所以將方案分為兩步，第一步：確定選哪些學(xué)生，共有C42 C31 種可能，然后將選出的三個人進行排列：A33。所以共有C42 C13 A33108種方案（二）排列組合的常見模型1、捆綁法（整體法） ：當(dāng)題目中有“相鄰元素”時，則可將相鄰元素視為一個整體，與其他元素進行排列，然后再考慮相鄰元素之間的順序即可。例如： 5 個人排隊，其中甲乙相鄰，共有多少種不同的排法解：考慮第一步將甲乙視為一個整體，與其余3 個元素排列，則共有A44 種位置，第二步考慮甲乙自身順序，有 A22 種位置，所以排法的總數(shù)為NA44 A2248種2、插空法：當(dāng)題目中有“不相鄰元素”時，

4、則可考慮用剩余元素“搭臺”，不相鄰元素進行“插空”，然后再進行各自的排序注：（ 1）要注意在插空的過程中是否可以插在兩邊（ 2）要從題目中判斷是否需要各自排序例如：有 6 名同學(xué)排隊，其中甲乙不相鄰，則共有多少種不同的排法解：考慮剩下四名同學(xué) “搭臺”，甲乙不相鄰， 則需要從5 個空中選擇2 個插入進去， 即有 C52種選擇，然后四名同學(xué)排序，甲乙排序。所以NC52A44 A22480種3、錯位排列：排列好的n 個元素，經(jīng)過一次再排序后，每個元素都不在原先的位置上，則稱為這 n 個元素的一個錯位排列。例如對于a,b, c, d ，則 d,c,a, b 是其中一個錯位排列。3個元素的錯位排列有2

5、 種，4 個元素的錯位排列有9 種，5 個元素的錯位排列有44 種。以上三種情況可作為結(jié)論記住例如：安排 6 個班的班主任監(jiān)考這六個班，則其中恰好有兩個班主任監(jiān)考自己班的安排總數(shù)有多少種？解：第一步先確定那兩個班班主任監(jiān)考自己班，共有C62 種選法，然后剩下4 個班主任均不監(jiān)考自己班，則為4 個元素的錯位排列，共9 種。所以安排總數(shù)為NC6291354、依次插空：如果在n 個元素的排列中有m 個元素保持相對位置不變，則可以考慮先將這m 個元素排好位置，再將nm 個元素一個個插入到隊伍當(dāng)中（注意每插入一個元素，下一個元素可選擇的空1）例如：已知A,B,C,D, E,F6個人排隊，其中A, B,C

6、相對位置不變，則不同的排法有多少種解：考慮先將 A,B,C 排好，則 D 有 4 個空可以選擇，D 進入隊伍后， E 有 5 個空可以選擇，以此類推， F 有 6 種選擇，所以方法的總數(shù)為N456120種5、不同元素分組：將n 個不同元素放入m 個不同的盒中6、相同元素分組：將n 個相同元素放入m 個不同的盒內(nèi)，且每盒不空，則不同的方法共有Cnm 11 種。解決此類問題常用的方法是“擋板法” ，因為元素相同，所以只需考慮每個盒子里所含元素個數(shù)，則可將這n 個元素排成一列，共有n 1個空，使用 m 1 個“擋板”進入空檔處，則可將這 n 個元素劃分為 m 個區(qū)域，剛好對應(yīng)那m 個盒子。例如：將

7、6 個相同的小球放入到 4 個不同的盒子里，那么6 個小球5 個空檔，選擇 3 個位置放“擋板” ，共有C5320 種可能7、涂色問題：涂色的規(guī)則是“相鄰區(qū)域涂不同的顏色”，在處理涂色問題時，可按照選擇顏色的總數(shù)進行分類討論，每減少一種顏色的使用，便意味著多出一對不相鄰的區(qū)域涂相同的顏色（還要注意兩兩不相鄰的情況），先列舉出所有不相鄰區(qū)域搭配的可能，再進行涂色即可。例如：最多使用四種顏色涂圖中四個區(qū)域，不同的涂色方案有多少種？解：可根據(jù)使用顏色的種數(shù)進行分類討論（1）使用 4種顏色，則每個區(qū)域涂一種顏色即可：N1 A44（2）使用 3種顏色，則有一對不相鄰的區(qū)域涂同一種顏色，首先要選擇不相鄰的

8、區(qū)域：用列舉法可得：I,IV不相鄰所以涂色方案有：N2A43（3）使用 2 種顏色，則無法找到符合條件的情況，所以討論終止總計 SA44A4348 種二、典型例題：例 1：某電視臺邀請了6 位同學(xué)的父母共12 人，請 12 位家長中的4 位介紹對子女的教育情況，如果這4 位中恰有一對是夫妻，則不同選擇的方法種數(shù)有多少思路：本題解決的方案可以是：先挑選出一對夫妻，然后在挑選出兩個不是夫妻的即可。第一步：先挑出一對夫妻：C16第二步：在剩下的10 個人中選出兩個不是夫妻的，使用間接法：C1025所以選擇的方法總數(shù)為 N C61 C1025240 （種）答案： 240 種例 2：某教師一天上 3 個

9、班級的課， 每班上 1 節(jié)，如果一天共 9 節(jié)課，上午 5 節(jié)，下午 4 節(jié)，并且教師不能連上 3 節(jié)課（第 5 節(jié)和第 6 節(jié)不算連上），那么這位教師一天的課表的所有不同排法有（）A.474種B.77種C.462種D.79種思路：本題如果用直接法考慮，則在安排的過程中還要考慮兩節(jié)連堂，并且會受到第5,6節(jié)課連堂的影響，分類討論的情形較多，不易求解。如果使用間接法則更為容易。首先在無任何特殊要求下，安排的總數(shù)為A93 。不符合要求的情況為上午連上3 節(jié)：A43 和下午連上三節(jié)：A33 ，所以不同排法的總數(shù)為：A93A43A33474 （種）答案：A例 3： 2 位男生和3 位女生共5 位同學(xué)站

10、成一排，若男生甲不站兩端，3 位女生中有且只有兩位女生相鄰，則不同排法的種數(shù)是（）A.60B.48C.42D.36思路：首先考慮從3 位女生中先選中相鄰的兩位女生，從而相鄰的女生要與另一女生不相鄰，則可插空， 讓男生搭架子， 因為男生甲不站兩端，所以在插空的過程中需有人站在甲的邊上，再從剩下的兩個空中選一個空插入即可。第一步：從三位女生中選出要相鄰的兩位女生：C32第二步：兩位男生搭出三個空，其中甲的邊上要進入女生，另外兩個空中要選一個空進女生，所以共有 C12 種選法。第三步：排列男生甲，乙的位置：A22 ，排列相鄰女生和單個女生的位置：A22 ，排列相鄰女生相互的位置：A22所以共有 NC

11、32 C12 A22 A22 A22 48 種答案： B例 4：某班班會準(zhǔn)備從甲，乙等7 名學(xué)生中選派4 名學(xué)生發(fā)言，要求甲，乙兩名同學(xué)至少有一人參加， 且若甲乙同時參加，則他們發(fā)言時不能相鄰， 那么不同的發(fā)言順序種數(shù)為 （）A. 360B.520C.600D.720思路：因為選人的結(jié)果不同會導(dǎo)致安排順序的不同，所以考慮“先取再排”，分為“甲乙”同時選中和“甲乙只有一人選中”兩種情況討論：若甲乙同時被選中，則只需再從剩下5人中選取 2 人即可： C52 ，在安排順序時， 甲乙不相鄰則 “插空”，所以安排的方式有： A32A22 ，從而第一種情況的總數(shù)為：N1C52 A32 A22120（種），

12、若甲乙只有一人選中，則首先先從甲乙中選一人，有C21 ，再從剩下 5 人中選取三人，有C53 ，安排順序時則無要求，所以第二種情況的總數(shù)為：N2C12 C53 A44480 （種），從而總計 600 種答案： C例 5：從單詞“ equation ”中選取 5 個不同的字母排成一排，含有“qu”（其中“ qu”相連且順序不變）的不同排列共有_種思路：從題意上看，解決的策略要分為兩步：第一步要先取出元素，因為“qu”必須取出，所以另外 3 個元素需從剩下的6 個元素中取出，即 C63 種，然后在排列時，因為要求“qu”相連，所以采用 “捆綁法”，將 qu 視為一個元素與其它三個元素進行排列：A4

13、4 ，因為“ qu”順序不變，所以不需要再對qu 進行排列。綜上，共有：C63 A44480 種答案： 480例 6：設(shè)有編號 1,2,3,4,5 的五個茶杯和編號為1,2,3,4,5 的五個杯蓋，將五個杯蓋蓋在五個茶杯上，至少有兩個杯蓋和茶杯的編號相同的蓋法有（）A. 30種B. 31種C. 32種D. 36種思路： 本題可按照相同編號的個數(shù)進行分類討論，有兩個相同時，要先從 5 個里選出哪兩個相同，有 C52 種選法，則剩下三個為錯位排列，有2 種情況，所以N1C522 ，有三個相同時，同理，剩下兩個錯位排列只有一種情況（交換位置），所以 N2C53 1，有四個相同時則最后一個也只能相同，

14、所以N3 1，從而 SC52 2C531131（種）答案： B例 7：某人上10 級臺階，他一步可能跨1 級臺階，稱為一階步，也可能跨2 級臺階，稱為二階步； 最多能跨 3 級臺階， 稱為三階步， 若他總共跨了6 步，而且任何相鄰兩步均不同階，則此人所有可能的不同過程的種數(shù)為（）A.6B.8C.10D.12答案： A思路：首先要確定在這 6 步中，一階步，二階步，三階步各有幾步，分別設(shè)為x, y, zN ，x4x3x2xyz6則有，解得：y0,y2,y4 ，因為相鄰兩步不同階，所以符合x2 y3z10z2z1z0x3要求的只有y2 ，下面開始安排順序，可以讓一階步搭架子，則二階步與三階步必須插

15、z1入一階步里面的兩個空中，所以共有2 種插法， 二階步與三階步的前后安排共有3 種（三二二，三二三，二三三） ，所以過程總數(shù)為N236答案： A例 8：某旅行社有導(dǎo)游9 人，其中3 人只會英語，2 人只會日語，其余4 人既會英語又會日語，現(xiàn)要從中選6 人，其中 3 人負責(zé)英語導(dǎo)游，另外三人負責(zé)日語導(dǎo)游，則不同的選擇方法有_種思路： 在步驟上可以考慮先選定英語導(dǎo)游， 再選定日語導(dǎo)游。 英語導(dǎo)游的組成可按只會英語的和會雙語的人數(shù)組成進行分類討論， 然后再在剩下的人里選出日語導(dǎo)游即可。 第一種情況：沒有會雙語的人加入英語導(dǎo)游隊伍，則英語導(dǎo)游選擇數(shù)為C33 ，日語導(dǎo)游從剩下6 個人中選擇，有C63

16、中，從而N0C33C63 ，第二種情況：有一個會雙語的人加入英語導(dǎo)游隊伍，從而可得N1C14C32C53 ，依次類推，第三種情況。兩個會雙語的加入英語導(dǎo)游隊伍，則N2C42C13C43 ，第四種情況，英語導(dǎo)游均為會雙語的。則N3C43C33 ，綜上所述，不同的選擇方法總數(shù)為SC33C63C41C32C53C 42C31C43C43C33216 ( 種)答案：216 種例 9：如圖，用四種不同顏色給圖中A, B,C , D , E, F 六個點涂色，要求每個點涂一種顏色，且圖中每條線段的兩個端點涂不同顏色，則不同的涂色方法有（）A.288 種B.264 種C.240 種D.168 種思路：如果用

17、四種顏色涂六個點，則需要有兩對不相鄰的點涂相同的顏色。所以考慮列舉出不相鄰的兩對點。列舉的情況如下：A,CB, D，A, CB, E， A,CD, F，A,F B,D ，A, FB, E，A, FC, E， B,DC, E，B,E D,F ，C, ED, F共九組，所以涂色方法共有9 A44216如果用三種顏色涂六個點，則需要有三對不相鄰的點涂相同的顏色，列舉情況如下：A,CB, ED, F，A, FC, EB, D 共兩組，所以涂色方法共有2A4348綜上所述，總計264 種答案：B例 10：有8 張卡片分別標(biāo)有數(shù)字1,2,3,4,5,6,7,8，從中取出6 張卡片排成3 行2 列，要求3 行中僅有中間行的兩張卡片上的數(shù)字之和為5，則不同的排法共有（）A. 1344種B. 1248種C. 1056種D. 960種思路：中間行數(shù)字和為5 只有兩種情況，即1,4 和 2,3 ，但這兩組不能同時占據(jù)兩行，若按題意思考，以1,4 占中間行為例，則在安排時既要考慮另一組2,3 是否同時被選中，還要考慮同時被選中時不能呆在同一行，情況比較復(fù)雜。 所以考慮間接法，先求出中間和為5 的所有情況，再減去兩行和為5 的情形解：先考慮中間和為5 的所有情況：第一步：先將中間行放入