排列組合問題解法總結(jié)

1、二十種排列組合問題的解法排列組合問題聯(lián)系實際生動有趣，但題型多樣，思路靈活，因此解決排列組合問題，首先要認真審題,弄清楚是排列問題、組合問題還是排列與組合綜合問題；其次要抓住問題的本質(zhì)特征，采用合理恰當?shù)姆?法來處理.教學(xué)目標1. 進一步理解和應(yīng)用分步計數(shù)原理和分類計數(shù)原理.2. 掌握解決排列組合問題的常用策略；能運用解題策略解決簡單的綜合應(yīng)用題提高學(xué)生解決問題分析問題的能力3. 學(xué)會應(yīng)用數(shù)學(xué)思想和方法解決排列組合問題 復(fù)習鞏固1. 分類計數(shù)原理（加法原理）完成一件事，有n類辦法，在第1類辦法中有 mi種不同的方法，在第2類辦法中有 m2種不同的方法，- 在第n類辦法中有 mn種不同的方法，那

2、么完成這件事共有：N m m2 - m種不同的方法.2. 分步計數(shù)原理（乘法原理）完成一件事，需要分成 n個步驟，做第1步有m,種不同的方法，做第 2步有m,種不同的方法，做第n步有m種不同的方法，那么完成這件事共有：Nmij m -mn種不同的方法.3. 分類計數(shù)原理分步計數(shù)原理區(qū)別分類計數(shù)原理方法相互獨立，任何一種方法都可以獨立地完成這件事.分步計數(shù)原理各步相互依存，每步中的方法完成事件的一個階段，不能完成整個事件.解決排列組合綜合性問題的一般過程如下：1. 認真審題弄清要做什么事2. 怎樣做才能完成所要做的事，即采取分步還是分類，或是分步與分類同時進行，確定分多少步及多少類.3. 確定每

3、一步或每一類是排列問題（有序）還是組合（無序）問題，元素總數(shù)是多少及取出多少個元素.4. 解決排列組合綜合性問題，往往類與步交叉，因此必須掌握一些常用的解題策略一.特殊元素和特殊位置優(yōu)先策略例1.由0,1,2,3,4,5可以組成多少個沒有重復(fù)數(shù)字五位奇數(shù).解:由于末位和首位有特殊要求，應(yīng)該優(yōu)先安排，以免不合要求的元素占了這兩個位置.C：種排法；A種排法;31A4C3先排末位，從1,3,5三個數(shù)中任選一個共有 C3排法； 然后排首位，從2,4和剩余的兩個奇數(shù)中任選一個共有 最后排中間三個數(shù)，從剩余四個數(shù)中任選3個的排列數(shù)共有由分步計數(shù)原理得 C；C；a3288練習題：7種不同的花種在排成一列的花

4、盆里 ，若兩種葵花不種在中間，也不種在兩端的花盆里，問有多少不同的 種法？解：先種兩種不同的葵花在不受限限制的四個花盒中共有a2不同種法，再其它葵花有 A5不同種法，所以共有不同種法 a2a512 120 1440種不同的種法.二.相鄰元素捆綁策略例2. 7人站成一排，其中甲乙相鄰且丙丁相鄰，共有多少種不同的排法.解：可先將甲乙兩元素捆綁成整體并看成一個復(fù)合元素，同時丙丁也看成一個復(fù)合元素，再與其它元素進 行排列，同時對相鄰元素內(nèi)部進行自排.由分步計數(shù)原理可得共有a5a2a2 480種不同的排法.練習題：某人射擊8槍，命中4槍，4槍命中恰好有3槍連在一起的情形的不同種數(shù)為20解：命中的三槍捆綁

5、成一槍，與命中的另一槍插入未命中的四槍的空位，共有A2 20種不的情形.三不相鄰問題插空策略例3. 一晚會的節(jié)目有4個舞蹈,2個相聲,3個獨唱，舞蹈節(jié)目不能連續(xù)出場，則節(jié)目的出場順序有多少種？ 解：分兩步進行第一步排 2個相聲和3個獨唱共有A5種，第二步將4舞蹈插入第一步排好的 6個元素中間包含首尾兩個空位共有種 a6不同的方法,由分步計數(shù)原理,節(jié)目的不同順序共有 a5a4練習題：某班新年聯(lián)歡會原定的 5個節(jié)目已排成節(jié)目單，開演前又增加了兩個新節(jié)目.如果將這兩個新節(jié)目插入原節(jié)目單中，且兩個新節(jié)目不相鄰，那么不同插法的種數(shù)為30四. 定序問題倍縮空位插入策略例4. 7人排隊，其中甲乙丙3人順序一

6、定共有多少不同的排法 解：（倍縮法）對于某幾個元素順序一定的排列問題，可先把這幾個元素與其他元素一起進行排列，然后用總排列數(shù)除以這幾個元素之間的全排列數(shù)，則共有不同排法種數(shù)是：空A（空位法）設(shè)想有7把椅子讓除甲乙丙以外的四人就坐共有A；種方法，其余的三個位置甲乙丙共有1種坐法，則共有 A；種方法.（七個空位坐了四人，剩下3個空位按一定順序坐下甲，乙，丙）思考:可以先讓甲乙丙就坐嗎S（插入法）先排甲乙丙三個人，共有1種排法，再把其余4四人依次插入共有 C；A方法.（先選三個座位坐下甲，乙，丙共有C；種選法，余下四個空位排其它四人共有A種排法，所以共有C；兀種方法.）練習題：10人身高各不相等，排

7、成前后排，每排 5人，要求從左至右身高逐漸增加，共有多少排法？C；。五. 重排問題求幕策略例5.把6名實習生分配到 7個車間實習，共有多少種不同的分法解:完成此事共分六步：把第一名實習生分配到車間有7_種分法.把第二名實習生分配到車間也有7種分依此類推，由分步計數(shù)原理共有 76種不同的排法練習題：1. 某班新年聯(lián)歡會原定的 5個節(jié)目已排成節(jié)目單，開演前又增加了兩個新節(jié)目.如果將這兩個節(jié)目插入原節(jié)目單中，那么不同插法的種數(shù)為422. 某8層大樓一樓電梯上來 8名乘客人，他們到各自的一層下電梯，下電梯的方法78六. 環(huán)排問題直排策略如果在圓周上 m個不同的位置編上不同的號碼，那么從n個不同的元素的

8、中選取 m個不同的元素排在圓周上不同的位置，這種排列和直線排列是相同的；如果從n個不同的元素的中選取 m個不同的元素排列在圓周上，位置沒有編號，元素間的相對位置沒有改變，不計順逆方向，這種排列和直線排列是不同的，這就是環(huán)形排列的問題.一個m個元素的環(huán)形排列，相當于一個有m個頂點的多邊形，沿相鄰兩個點的弧線剪斷，再拉直就是形成一個直線排列，即一個m個元素的環(huán)形排列對應(yīng)著 m個直線排列，設(shè)從 n個元素中取出 m個元素組成的環(huán)形排列數(shù)為 N個，則對應(yīng)的直線排列數(shù)為mN個，又因為從n個元素中取一 Am出m個元素的排成一排的排列數(shù)為Am個，所以mN Am，所以N 二.mAm即從n個元素中取出 m個元素組

9、成的環(huán)形排列數(shù)為N -.mAn n!n個元素的環(huán)形排列數(shù)為 N -（n 1）!n n例6. 8人圍桌而坐，共有多少種坐法？解：圍桌而坐與坐成一排的不同點在于，坐成圓形沒有首尾之分，所以固定一人A：并從此位置把圓形展成直線其余7人共有（8 1）!7!種排法，即7!7 6 5 4 3 2 1840種CKXXXXXXHDABCDEFGHA練習題：6顆顏色不同的鉆石，可穿成幾種鉆石圈 120七. 多排問題直排策略例7.8人排成前后兩排，每排4人，其中甲乙在前排，丙在后排，共有多少排法解：8人排前后兩排，相當于8人坐8把椅子，可以把椅子排成一排先排前4個位置，2個特殊元素有a4種排法，再排后4個位置上的

10、特殊元素丙有a4種,其余的5人在5個位置上任意排列有 a5種,則共有a4a；a：種排法.（排好后，按前4個為前排，后4人為后排分成兩排即可）練習題：有兩排座位，前排11個座位，后排12個座位，現(xiàn)安排2人就座規(guī)定前排中間的 3個座位不能坐，并且這2人不左右相鄰，那么不同排法的種數(shù)是346解：由于甲乙二人不能相鄰，所以前排第1,4,8,11四個位置和后排第1 ,12位置是排甲乙中的一個時，與它相鄰的位置只能排除一個，而其它位置要排除3個，所以共有排列c6c；8108 238 346八. 排列組合混合問題先選后排策略例8.有5個不同的小球，裝入4個不同的盒內(nèi)，每盒至少裝一個球，共有多少不同的裝法.解

11、：第一步從5個球中選出2個組成復(fù)合元共有 C；種方法.再把4個元素（包含一個復(fù)合元素）裝入4個不同的盒內(nèi)有a4種方法，根據(jù)分步計數(shù)原理裝球的方法共有g(shù)2a4練習題：一個班有 6名戰(zhàn)士，其中正副班長各1人現(xiàn)從中選4人完成四種不同的任務(wù)，每人完成一種任務(wù)， 且正副班長有且只有 1人參加，則不同的選法有192種九小集團問題先整體后局部策略例9.用1,2,3,4,5 組成沒有重復(fù)數(shù)字的五位數(shù)其中恰有兩個偶數(shù)在1, 5在兩個奇數(shù)之間，這樣的五位數(shù)有多少個？（注：兩個偶數(shù)2,4在兩個奇數(shù)1,5之間，這是題意，說這個結(jié)構(gòu)不能被打破，故3只能排這個結(jié)構(gòu) 的外圍，也就是說要把這個結(jié)構(gòu)看成一個整體與3進行排列）解

12、：把1 , 5 , 2 , 4當作一個小集團與3排隊共有A2種排法，再排小集團內(nèi)部共有a2a2種排法，由分步計數(shù)原理共有 a2a2 a2種排法.練習題：1 .計劃展出10幅不同的畫，其中1幅水彩畫，4幅油畫，5幅國畫，排成一行陳列，要求同一品種的必須連在一起，并且水彩畫不在兩端，那么共有陳列方式的種數(shù)為a2a；a：2. 5男生和5女生站成一排照像，男生相鄰，女生也相鄰的排法有 a2a5a5種十.元素相同問題隔板策略例10.有10個運動員名額，分給 7個班，每班至少一個，有多少種分配方案？解：因為10個名額沒有差別，把它們排成一排相鄰名額之間形成9個空隙在9個空檔中選6個位置插個隔板，可把名額分

13、成7份，對應(yīng)地分給7個班級，每一種插板方法對應(yīng)一種分法共有C；種分法.注：這和投信問題是不同的，投信問題的關(guān)鍵是信不同，郵筒也不同，而這里的問題是郵筒不同，但信是 相同的即班級不同，但名額都是一樣的.o|o ololo ololo olo 練習題：10個相同的球裝5個盒中，每盒至少一有多少裝法？C；2. x y z w 100求這個方程組的自然數(shù)解的組數(shù)g3）3十一.正難則反總體淘汰策略例11.從0,123,4,5,6,7,8,9這十個數(shù)字中取出三個數(shù)，使其和為不小于10的偶數(shù),不同的取法有多少種？解：這問題中如果直接求不小于10的偶數(shù)很困難，可用總體淘汰法.這十個數(shù)字中有5個偶數(shù)5個奇數(shù)，所

14、取的三個數(shù)含有3個偶數(shù)的取法有c3 ,只含有1個偶數(shù)的取法有c5c2 ,和為偶數(shù)的取法共有123123C5C5C5再淘汰和小于10的偶數(shù)共9種，符合條件的取法共有C5C5C59練習題：我們班里有 43位同學(xué)，從中任抽5人，正、副班長、團支部書記至少有一人在內(nèi)的 抽法有多少種？ 十二.平均分組問題除法策略例12. 6本不同的書平均分成 3堆,每堆2本共有多少分法？解：分三步取書得CfCC；種方法，但這里出現(xiàn)重復(fù)計數(shù)的現(xiàn)象，不妨記6本書為ABCDEF若第一步取 AB,第二步取CD,第三步取EF該分法記為（AB,CD,EF）,則CfcfC；中還有共有a3種取法，而這些分法僅是（AB,CD,EF） 種

15、分法，故共有cfcfc；種分法.(AB,EF,CD),(CD,AB,EF),(CD,EF,AB)(EF,CD,AB),(EF,AB,CD)平均分成的組，不管它們的順序如何，都是一種情況，所以分組后要一定要除以 An（ n為均分的 組數(shù)）避免重復(fù)計數(shù)。練習題：1將13個球隊分成3組,一組5個隊,其它兩組4個隊，有多少分法?544C13C8C42.10名學(xué)生分成3組,其中一組4人，另兩組3人但正副班長不能分在同一組，有多少種不同的分組方法（1540）3. 某校高二年級共有六個班級，現(xiàn)從外地轉(zhuǎn)排2名，則不同的安排方案種數(shù)為 入4名學(xué)生，要安排到該年級的兩個班級且每班安C：C；A90)十三.合理分類與

16、分步策略 例13.在一次演唱會上共10名演員，其中8人能能唱歌,5人會跳舞，現(xiàn)要演出一個2人唱歌2人伴舞的節(jié)目,有多少選派方法解：10演員中有5人只會唱歌，2人只會跳舞3人為全能演員.選上唱歌人員為標準進行研究只會唱的5人中沒有人選上唱歌人員共有種，只會唱的5人中只有1人選上唱歌人員c5c3c2種,只會唱的5人中只有2人選上唱歌人員有 C5C5種，由分類計數(shù)原理共有c|c|c5c3c：cfcf 種.解含有約束條件的排列組合問題，可按元素的性質(zhì)進行分類，按事件發(fā)生的連續(xù)過程分步，做到標準明確。分步層次清楚，不重不漏，分類標準一旦確定要貫穿于解題過程的始終。本題還有如下分類標準：以3個全能演員是否

17、選上唱歌人員為標準；以3個全能演員是否選上跳舞人員為標準；CD以只會跳舞的2人是否選上跳舞人員為標準；都可經(jīng)得到正確結(jié)果練習題：1. 從4名男生和3名女生中選出4人參加某個座談會，若這4人中必須既有男生又有女生，則不同的選法共有342. 3成人2小孩乘船游玩,1號船最多乘3人，2號船最多乘2人,3號船只能乘1人,他們?nèi)芜x2只船或3只船，但小孩不能單獨乘一只船，這3人共有多少乘船方法（ 27）十四構(gòu)造模型策略例14.馬路上有編號為123,4,5,6,7,8,9的九只路燈，現(xiàn)要關(guān)掉其中的3盞，但不能關(guān)掉相鄰的2盞或3盞,也不能關(guān)掉兩端的2盞,求滿足條件的關(guān)燈方法有多少種？解：把此問題當作一個排隊模

18、型在6盞亮燈的5個空隙中插入3個不亮的燈有 C；種一些不易理解的排列組合題如果能轉(zhuǎn)化為非常熟悉的模型，如占位填空模型，排隊模型，耳盒模型等，可 使問題直觀解決練習題：某排共有10個座位，若4人就坐，每人左右兩邊都有空位，那么不同的坐法有多少種？（120）十五實際操作窮舉策略例15.設(shè)有編號1,2,3,4,5的五個球和編號1,2,3,4,5 的五個盒子，現(xiàn)將5個球投入這五個盒子內(nèi)，要求每個盒子放一個球，并且恰好有兩個球的編號與盒子的編號相同，有多少投法解：從5個球中取出2個與盒子對號有 C；種還剩下3球3盒序號不能對應(yīng)，利用實際操作法，如果剩下3,4,5號球,3,4,5 號盒,3號球只能裝入4號

19、或5號盒,共兩種裝法，當3號球裝4號盒時，則4,5號球只有1種裝法，同理3號球裝5號盒時,4,5號球有也只有 種練習題：1. 同一寢室4人,每人寫一張賀年卡集中起來，然后每人各拿一張別人的賀年卡，則四張賀年卡不同的分配方式有多少種？（9）2. 給圖中區(qū)域涂色，要求相鄰區(qū) 域不同色，現(xiàn)有4種可選顏色， 則不同的著色方法有 72種十六.分解與合成策略例16. 30030能被多少個不同的偶數(shù)整除分析：先把30030分解成質(zhì)因數(shù)的乘積形式30030=2X 3X 5 X 7 X 11 X 13依題意可知偶因數(shù)必先取2,再從其余5個因數(shù)中任取若干個組成乘積,所有的偶因數(shù)為：c5c； c； c；練習：正方體

20、的8個頂點可 連成多少對異面直線.（是連成異面直線，所以包括對角線） 解：我們先從8個頂點中任取4個頂點構(gòu)成四體共有體共 C； 12 58,每個四面體有 3對異面直線，正方體中的8個頂點可連成3 58174對異面直線分解與合成策略是排列組合問題的一種最基本的解題策略，把一個復(fù)雜問題分解成幾個小問題逐一解決，然后依據(jù)問題分解后的結(jié)構(gòu)，用分類計數(shù)原理和分步計數(shù)原理將問題合成，從而得到問題的答案，每個比較復(fù)雜的問題都要用到這種解題策略十七.化歸策略例17. 25人排成5X 5方陣，現(xiàn)從中選3人，要求3人不在同一行也不在同一列，不同的選法有多少種？解：將這個問題退化成9人排成3 X 3方陣，現(xiàn)從中選3

21、人，要求3人不在同一行也不在同一列，有多少選法.這樣每行必有1人從其中的一行中選取1人后，把這人所在的行列都劃掉，如此繼續(xù)下去.從3 X 3方隊中選3人的方法有C3C；C；種再從5X 5方陣選出3 X 3方陣便可解決問題.從5X 5方隊中選取3行3列有CfCl選法所以從5 X 5方陣選不在同一行也不在同一列的3人有c53c53c3c2c11選法.從3 3方陣中任取3個人時，因這三人不在同一行同一列 所以每行必有一人,據(jù)此,從每行任了練習題：某城市的街區(qū)由12個全等的矩形區(qū)組成，其中實線表示馬路，從A走到B的最短路徑有多少種？( C； 35)十八數(shù)字排序問題查字典策略例18.由0, 1, 2, 3, 4, 5六個數(shù)字可以組成多少個沒有重復(fù)的比324105大的數(shù)？解:N 2