排列組合問題解法大全

1、學(xué)習(xí)好資料歡迎下載排列組合問題解法大全一.相鄰問題捆綁法：題目中規(guī)定相鄰的幾個元素捆綁成一個組，當(dāng)作一個大元素參與排列例1. A, B,C, D,E五人并排站成一排，如果 A, B必須相鄰且B在A的右邊，那么不同的排法種數(shù)有C 6C 2C 1=15（種）。結(jié)論1: 一般地，n個不同的元素分成 P組，各組內(nèi)元素數(shù)目分別為 m.，m1 ， 2m P，其中k組內(nèi)元素數(shù)目相等，那么分A、60 種 B 、48 種C 、36 種 D 、24 種解析：把 A, B視為一人，且B固定在A的右邊，則本題相當(dāng)于 4人的全排列，A44 =24種。二.相離問題插空法:元素相離（即不相鄰）問題，可先把無位置要求的幾個元

2、素全排列，再把規(guī)定的相離的幾個元素插入上述幾個元素的空位和兩端例2.七人并排站成一行，如果甲乙兩個必須不相鄰，那么不同的排法種數(shù)是A、1440 種 B 、3600 種 C 、4820 種 D 、4800 種解析：除甲乙外，其余5個排列數(shù)為a5種，再用甲乙去插6個空位有A種，不同的排法種數(shù)是 A5a =3600種，選B.三.特殊兀素或特殊位置優(yōu)限法：優(yōu)先解決帶限制條件的元素或位置，或說先解決特殊元素或特殊位置”例3.1名老師和4名獲獎同學(xué)排成一排照相留念，若老師不站兩端則有不同的排法有多少種?解析：老師在中間三個位置上選一個有A種，4名同學(xué)在其余4個位置上有A4種方法；所以共有A3A44 = 7

3、2種.四.分組分配：n個不同元素按照某些條件分配給 k個不同得對象，稱為 分配問題，分定向分配和不定向分配兩種問題;將n個不同元素按照某些條件分成 k組，稱為分組問題.分組問題有不平均分組、平均分組、和部分平均分組三種情況。分組問題和分配問題是有區(qū)別的，前者組與組之間只要元素個數(shù)相同是不區(qū)分的；而后者即使2組元素個數(shù)相同，但因?qū)ο蟛煌?，仍然是可區(qū)分的.對于后者必須先分組后排列。1.基本的分組問題例4六本不同的書，分為三組，求在下列條件下各有多少種不同的分配方法?（1）每組兩本.（2） 組一本，一組二本，一組三本（3） 組四本，另外兩組各一本分析：（1）分組與順序無關(guān)，是組合問題。分組數(shù)是cCc

4、2 2 =90（種），這90種分組實際上重復(fù)了6次。我們不妨把六本不同的書寫上1、2、3、4、5、6六個號碼，考察以下兩種分法：（1, 2）（3，4）（5, 6）與（3，4）（1，2）（5，6），由于書是均勻分組的，三組的本數(shù)一樣，又與順序無關(guān)，所以這兩種分法是同一種分法。以上的分組方法實際上加入了組的順序，因此還應(yīng)取消分組的順序,C 2 C 2C 2即除以組數(shù)的全排列數(shù) A3，所以分法是C 6C 4C 2 =15（種）。先分組，方法是 cCc2 3，那么還要不要除以 A3 ?我們發(fā)現(xiàn),A 3由于每組的書的本數(shù)是不一樣的，因此不會出現(xiàn)相同的分法，即共有cCc23=60（種）分法。（3）分組方法

5、是cCc2 1 =30（種），那么其中有沒有重復(fù)的分法呢？我們發(fā)現(xiàn)，其中兩組的書的本數(shù)都是一本，因此這兩組有了順序，而與四本書的那一組，由于書的本數(shù)不一樣，不可能重復(fù)。所以實際分法是通過以上三個小題的分析，我們可以得出分組問題的一般方法。學(xué)習(xí)好資料歡迎下載Cu種，故化+X2十+X5）10的展開式中共有014項。Vm2C n C n _m1組方法數(shù)是c 叫 c mp C n_mi _m2C mp7k。Ak2.基本的分配的問題定向分配問題例5六本不同的書,分給甲、乙、丙三人，求在下列條件下各有多少種不同的分配方法?分析:甲兩本、甲一本、甲四本、乙兩本、乙兩本、乙一本、由于分配給三人,丙兩本丙三本丙

6、一本每人分幾本是一定的,屬分配問題中的定向分配問題,由分布計數(shù)原理不難解出：分別有C 2C 2C 2 =90（種）,cC& 3 =60（種），C 6C 2C1 =30（種）。（2）不定向分配問題 例6六本不同的書，分給甲、乙、丙三人，求在下列條件下各有多少種不同的分配方法?（1）每人兩本.（2）人一本、一人兩本、一人三本（3） 人四本、一人一本、一人一本同一本書給不同的人是不同的分法,，因此只要將分組方法數(shù)再乘以分析：此組題屬于分配中的不定向分配問題，是該類題中比較困難的問題。由于分配給三人, 所以是排列問題。實際上可看作“分為三組，再將這三組分給甲、乙、丙三人”222411C6C4C2a3=

7、90（種）,cCc23A3=360（種）C 6C ；C1A3=90（種）o結(jié)論2. 般地，如果把不同的元素分配給幾個不同對象，并且每個不同對象可接受的元素個數(shù)沒有限制，那么實際上是先分組后排列的問題，即分組方案數(shù)乘以不同對象數(shù)的全排列數(shù)。通過以上分析不難得出解不定向分配題的一般原則:先分組后排列。三組呢？有三類分法,2 2 2+cCc2A 3分析：恰有一個空盒，則另外三個盒子中小球數(shù)分別為1 , 1 ,2。實際上可轉(zhuǎn)化為先將四個不同的小球分為三組，兩組各1個，另例7六本不同的書，分給甲、乙、丙三人，每人至少一本，有多少種分法?分析：六本書和甲、乙、丙三人都有“歸宿”，即書要分完，人不能空手。因

8、此，考慮先分組，后排列。先分組，六本書怎么分為（1）每組兩本（2）分別為一本、二本、三本（3）兩組各一本，另一組四本。所以根據(jù)加法原理，分組法是C 4 C 1C 13+ C6C2C1 =90（種）。再考慮排列，即再乘以A3。所以一共有540種不同的分法。3.分配問題的變形問題例8四個不同的小球放入編號為 1, 2 , 3, 4的四個盒子中，恰有一個空盒的放法有多少種?C1C1C2一組2個，分組方法有C 4C 2C 2 （種），然后將這三組（即三個不同元素）分配給四個小盒（不同對象）中的3個的排列問題，即共有A 2例9有甲、乙、丙三項任務(wù)，甲需 2人承擔(dān)，乙、丙各需1人承擔(dān)，從10人中選派4人承

9、擔(dān)這三項任務(wù)，不同的選法有多少種?1 1 2分析：先考慮分組，即10人中選4人分為三組，其中兩組各一人，另一組二人，共有C10C；C 8 （種）分法。再考慮排列，甲任務(wù)A 2需2人承擔(dān)，因此2人的那個組只能承擔(dān)甲任務(wù)，而一個人的兩組既可承擔(dān)乙任務(wù)又可承擔(dān)丙任務(wù)，所以共有1 1 2C10C；C 8 A2 =2520（種）不同的選法。A 2例10設(shè)集合A=1 , 2, 3, 4, B=6 , 7, 8, A為定義域，B為值域，則從集合 A到集合B的不同的函數(shù)有多少個?分析：由于集合 A為定義域，B為值域，即集合 A、B中的每個元素都有“歸宿”，而集合B的每個元素接受集合 A中對應(yīng)的元素的數(shù)目不限，

10、所以此問題實際上還是分組后分配的問題。先考慮分組，集合A中4個元素分為三組，各組的元素數(shù)目分別為1、1、2,則共有1 1 2C4C 3C 2（種）分組方法。再考慮分配，即排列，再乘以A3，所以共有1 1 2C4C3C 2A 3 =36（個）不同的函數(shù)。五.相同元素隔板法及應(yīng)用情形1：將n件相同的物品或（名額）分配給 m個（或位置），允許若干個人或（位置）為空。將n件物品和m-1個隔板排成一排,占n+m-1個位置，從n+m-1個位置選m-1位置放隔板，有 cX-1種。情形2：將n件相同的物品或（名額）分配給m個（或位置），每個位置必須有物品，有cm；1 種。例11.把20個相同的球放入4個不同的

11、盒子，每個盒子都不空，有多少種不同方法?019把20個相同的球放入4個不同的盒子，每個盒子至少有3個小球，有多少種不同方法?C131把20個相同的球放入編號為 2，3，4, 5的4個盒子，每個盒子的小球數(shù)不少于編號數(shù),有多少種不同方法?把20個相同的球放入4個不同的盒子，盒子可以空，有多少種不同方法?C；31.指標(biāo)分配問題。例12、某校召開學(xué)生會議，要將10個學(xué)生代表名額，分配到某年級的6個班中，若每班至少1個名額，又有多少種不同分法?c52.求n項展開式的項數(shù)。例13、求（旨+X2 + ”+ X5）10展開式中共有多少項?解：用10個相同的小球代表冪指數(shù)10,用5個標(biāo)有x1、X2、Xs的5個

12、不同的盒子表示數(shù)X1、X2、Xs，將10個相同的小球放入5個不同的盒子中，把標(biāo)有 Xi （i=1,2,5 ）每個盒子得到的小球數(shù)ki （i=1，2,，5; k嚴(yán)N ），記作Xj的ki次方。這樣，將10個相同的小球放入5個不同的盒子中的每一種放法，就對應(yīng)著展開式中的每一項。由隔板法知，這樣的放法共有c：4勺3勺21=1001 （種）。4X3X2X1學(xué)習(xí)好資料歡迎下載所以，(X, +X2 +X5)10展開式中共有1001項。點評：準(zhǔn)確理解隔板法的使用條件，是使用隔板法求(X! +X2 + X5 )10展開式中的項數(shù)的理論依據(jù)。3.求n元一次方程組的非負(fù)整數(shù)解。例14、求方程x1 + X2 +- +

13、 X5=7的正整數(shù)解的個數(shù)。解：用7個相同的小球代表數(shù) 7,用5個標(biāo)有x1 X2、X5的5個不同的盒子表示未知數(shù) X1、X2、X5，要得到方程X1 + X2+-+ X5=7的正整數(shù)解的個數(shù)，可分以下兩步完成。第一步：從7個相同的小球中任取 5個放入5個不同的盒子中，僅有 1種放法;第二步：把剩余的2個小球放入5個不同的盒中，由隔板法知，此時有C；種放法。由分步計數(shù)原理知，共有 C；種不同放法。我們把標(biāo)有Xi (i=1,2,5 )的每個盒子得到的小球數(shù)ki (i=1，2,，5； ki亡N +)，記作：Xi = ki。這樣，將7個相同的小球放入5個不同的盒子中的每一種放法，就對應(yīng)著方程 x1 +

14、x2+- + x5 =7的每一組解（k1, k2，k5）oCf4 =C； =15 （個）2x1所以，方程X1 + X2+- + X5 =7的正整數(shù)解共有15個。六.至多，至少問題排除法例15.從4臺甲型和5臺乙型電視機中任取 3臺，其中至少要甲型和乙型電視機各一臺，則不同的取法共有A、140 種 B 、80 種 C 、70 種 D 、35 種解析1:逆向思考，至少各一臺的反面就是分別只取一種型號，不取另一種型號的電視機，故不同的取法共有333Cg C4 C5 =70 種,選.C解析2:至少要甲型和乙 型電視機各一臺可分兩種情況：甲型1臺乙型2臺；甲型2臺乙型1臺；故不同的取法有c；ci +c5

15、c： =70 臺,選 C.例16. (1 )以正方體的頂點為頂點的四面體共有A、70 種 B 、64 種 C 、58 種 D 、52 種解析：正方體8個頂點從中每次取四點，理論上可構(gòu)成C；四面體,但6個表面和6個對角面的四個頂點共面都不能構(gòu)成四面體,所以四面體實際共有C； 12 =58個.(2)四面體的頂點和各棱中點共10點，在其中取4個不共面的點,不同的取法共有A、150 種 B 、147 種 C 、144 種 D 、141 種解析：10個點中任取4個點共有 do種，其中四點共面的有三種情況：在四面體的四個面上，每面內(nèi)四點共面的情況為C：，四個面共有4C(4個；過空間四邊形各邊中點的平行四邊

16、形共3個；過棱上三點與對棱中點的三角形共6個.所以四點不共面的情況的種數(shù)是Cw 4C4 3 6 =141種.七.綜合問題先選后排則恰有一個空盒的放法有多少種?例17. (1 )四個不同球放入編號為 1，2，3，4的四個盒中,2323解析：“先取”四個球中二個為一組，另二組各一個球的方法有C4種，“再排”在四個盒中每次排3個有幾種，故共有C4 A4 =144學(xué)習(xí)好資料歡迎下載解析：先把30030分解成質(zhì)因數(shù)的形式：30030=2X 3 X 5X 7 X 11 X 13;依題意偶因數(shù)2必取，3，5, 7，11，13這5個因數(shù)中任取(2) 9名乒乓球運動員，其中男5名，女4名，現(xiàn)在要進(jìn)行混合雙打訓(xùn)練

17、，有多少種不同的分組方法?解析：先取男女運動員各 2名,有cIc4種，這四名運動員混和雙打練習(xí)有 A中排法，故共有 c|c2a2 =120 種.八.交叉問題集合法:某些排列組合問題幾部分之間有交集，可用集合中求元素個數(shù)公式n(AUB) = n(A) +n(B) -n(AB).例18.從6名運動員中選出4人參加4 X 100米接力賽，如果甲不跑第一棒，乙不跑第四棒，共有多少種不同的參賽方案?解析：設(shè)全集= 6人中任取4人參賽的排列 ，A=甲跑第一棒的排列 ，B=乙跑第四棒的排列，根據(jù)求集合元素個數(shù)的公式得參賽方法共有:4332n(l)-n(A) - n(B) + n(AcB)=人AA =252

18、種.九.對等問題縮倍法：在排列問題中限制某幾個元素必須保持一定的順序，可用縮小倍數(shù)的方法例19. A, B, C,D, E五人并排站成一排，如果 B必須站在A的右邊(A, B可以不相鄰)那么不同的排法種數(shù)是A、24 種 B 、60 種 C 、90 種 D 、120 種1解析：B在A的右邊與B在A的左邊排法數(shù)相同，所以題設(shè)的排法只是5個元素全排列數(shù)的一半，即 丄a5 =60種，選B .2十.多排問題單排法:把元素排成幾排的問題可歸結(jié)為一排考慮，再分段處理例20. (1) 6個不同的元素排成前后兩排，每排3個元素，那么不同的排法種數(shù)是A、36 種 B 、120 種 C 、720 種 D、1440種

19、解析：前后兩排可看成一排的兩段，因此本題可看成6個不同的元素排成一排，共 A： =720種，選C .(2) 8個不同的元素排成前后兩排，每排 4個元素,其中某2個元素要排在前排，某 1個元素排在后排，有多少種不同排法?解析：看成一排，某 2個元素在前半段四個位置中選排2個，有A2種，某1個元素排在后半段的四個位置中選一個有A1種，其余5個元素任排5個位置上有A5種，故共有AAA5 =5760種排法.卜一. 圓排問題線排法:把n個不同元素放在圓周n個無編號位置上的排列，順序(例如按順時鐘)不同的排法才算不同的排列，而順序相同(即旋轉(zhuǎn)一下就可以重合)的排法認(rèn)為是相同的，它與普通排列的區(qū)別在于只計順

20、序而首位、末位之分,下列n個普通排列：a1, a2,a|(, an; a2, a3,a4 J|(, an JH; an, a1| ,an_i在圓排列中只算一種，因為旋轉(zhuǎn)后可以重合，故認(rèn)為相同，n個元素的圓排列數(shù)有 衛(wèi) 種.因此可將某個元素固定展成線排，其它的n-1元素全排列.n例21.5對姐妹站成一圈，要求每對姐妹相鄰，有多少種不同站法?解析：首先可讓5位姐姐站成一圈，屬圓排列有 A4種，然后在讓插入其間，每位均可插入其姐姐的左邊和右邊，有2種方式,故不同的安排方式 24咒25 =768種不同站法.說明：從n個不同元素中取出 m個元素作圓形排列共有 -Am 種不同排法.m十二.復(fù)雜的排列組合問

21、題1分解與合成法：例22. (1 ) 30030能被多少個不同偶數(shù)整除?若干個組成成積，所有的偶因數(shù)為學(xué)習(xí)好資料歡迎下載012345C5 + C5 +C5 +C5 +C5 +C5 =32 個.(2)正方體8個頂點可連成多少隊異面直線?解析：因為四面體中僅有 3對異面直線，可將問題分解成正方體的8個頂點可構(gòu)成多少個不同的四面體，從正方體8個頂點中任4取四個頂點構(gòu)成的四面體有 C8 12=58個，所以8個頂點可連成的異面直線有 3X 58=174對.2.構(gòu)造模型法(1)構(gòu)建方程模型例23上一個有10級臺階的樓梯，每步可上一級或兩級，共有多少種上臺階的方法?解：設(shè)X表示上一級臺階的步數(shù)，y表示上兩級

22、臺階的步數(shù)，_則 x+2y=10 (x 0, y 0, y忘Z)。當(dāng)X =2時，y =4，于是用6步走完10級臺階的方法為 c2種;同理，當(dāng)X = 0, 4, 6, 8, 10時，y的取值分別為5, 3, 2, 1, 0，則上臺階的方法分別為 C , C； , C； , C； , C；種。所以上臺階的方法共有 C； + C； + C7+C； + C8 + C11(0 =89種。點評：構(gòu)建方程模型的關(guān)鍵是找到等量關(guān)系,正確列出方程。(2)構(gòu)建立體幾何模型例24如圖1中A，B，C，D為海上四個島,AR要建三座橋，將這四個小島連接起來,則不同的建橋方案共有(A.8種B. 12 種C. 16 種D. 20 種解：如圖2,構(gòu)建三棱錐A BCD，四個頂點表示小島，六條棱表示連接任意兩島的橋梁，由題意，只需求出從六條棱中任取三條不共面的棱的不同取法,這可由間接法完成：從六條棱中任取三條棱的不同取法3C6 4 =16種，故選C項。3為C6種，任取三條共面棱的不同取法為4種，所以從六條棱中任取不共面的棱的不同取法為點評：構(gòu)建恰當(dāng)?shù)牧Ⅲw幾何模型，可以使排列組合問題顯得直觀清晰、簡潔明快。(3) 構(gòu)建隔板模型例25把20個相同的球全部裝入編號分別為1,2,3的三個盒子中，要