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

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

頁)-CAL-FENGHAI.-(YICAI)-CompanyOnel-CAL-本頁僅作為文檔封面，使用請直接刪除

排列組合問題的常見解法一.元素相同問題隔板策略例1.有10個運動員名額，分給7個班，每班至少一個,有多少種分配方案？解：因為10個名額沒有差別，把它們排成一排.相鄰名額之間形成9個空隙.在9個空檔中選6個位置插個隔板，可把名額分成7份，對應(yīng)地分給7個班級，每一種插板方法對應(yīng)一種分法共有C6種分法._9_注：這和投信問題是不同的，投信問題的關(guān)鍵是信不同，郵筒也不同，而這里的問題是郵筒不同，但信是相同的.即班級不同，但名額都是一樣的.練習(xí)題：1.10個相同的球裝5個盒中,每盒至少一個有多少裝法C4_9_2.x+y+z+w=100求這個方程組的自然數(shù)解的組數(shù) C3103二.環(huán)排問題直排策略所以N=A如果在圓周上m個不同的位置編上不同的號碼，那么從n個不同的元素的中選取m個不同的元素排在圓周上不同的位置，這種排列和直線排列是相同的；如果從n個不同的元素的中選取m個不同的元素排列在圓周上，位置沒有編號，元素間的相對位置沒有改變，不計順逆方向，這種排列和直線排列是不同的，這就是環(huán)形排列的問題.一個m個元素的環(huán)形排列，相當(dāng)于一個有m個頂點的多邊形，沿相鄰兩個點的弧線剪斷，再拉直就是形成一個直線排列，即一個m個元素的環(huán)形排列對應(yīng)著m個直線排列，設(shè)從n個元素中取出m個元素組成的環(huán)形排列數(shù)為N個，則對應(yīng)的直線排列數(shù)為mN個，又因為從n所以N=A排成一排的排列數(shù)為Am個，所以mN=Amnn即從n個元素中取出m個元素組成的環(huán)形排列數(shù)為N=聖mn個元素的環(huán)形排列數(shù)為N=A=也=(n-1)!nn例2.8人圍桌而坐,共有多少種坐法?解：圍桌而坐與坐成一排的不同點在于，坐成圓形沒有首尾之分，所以固定一人A4并從此4位置把圓形展成直線其余7人共有(8-1)!=7!種排法，即7!=7x6x5x4x3x2x1=840種-(XXXXXXXWABCDEFGHA-(XXXXXXXWABCDEFGHA練習(xí)題：6顆顏色不同的鉆石，可穿成幾種鉆石圈120三.多排例3.8人排4人,其在后排,共解:8班班班三.多排例3.8人排4人,其在后排,共解:8班班班七班問題直排策略排成前后兩排,每中甲乙在前排,丙有多少排法人排前后兩排,相當(dāng)于8人坐8把椅子,可以把椅子排成一排?先排前4個位置，2個特殊元素有A2種排法，再排后4個位置上_4_的特殊元素丙有Ai種,其余的5人在5個位置上任意排列有A5種,則共有A2AiA5種_￡ _￡ 445排法?（排好后，按前4個為前排，后4人為后排分成兩排即可）練習(xí)題：有兩排座位，前排11個座位，后排12個座位，現(xiàn)安排2人就座規(guī)定前排中間的3個座位不能坐，并且這2人不左右相鄰，那么不同排法的種數(shù)是摯解：由于甲乙二人不能相鄰，所以前排第1,4,8,11四個位置和后排第1,12位置是排甲乙中的一個時，與它相鄰的位置只能排除一個，而其它位置要排除3個，所以共有排列C1C1+C1C1二108+238二3466 18 14 17四?排列組合混合問題先選后排策略例4.有5個不同的小球，裝入4個不同的盒內(nèi)，每盒至少裝一個球，共有多少不同的裝法.解:第一步從5個球中選出2個組成復(fù)合元共有C2種方法.再把4個元素（包含一個復(fù)合元素）裝入4個不同的盒內(nèi)有A4種方法，根據(jù)分步計數(shù)原理裝球的方法共有C2A4_5 4練習(xí)題：一個班有6名戰(zhàn)士，其中正副班長各1人現(xiàn)從中選4人完成四種不同的任務(wù),每人完成一種任務(wù)，且正副班長有且只有1人參加，則不同的選法有192種小集團問題先整體后局部策略例5.用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進行排列）．解：把1,5,2,4當(dāng)作一個小集團與3排隊共有A2種排法，再排小集團內(nèi)部共有 2-A2A2種排法，由分步計數(shù)原理共有A2A2A2種排法.22222練習(xí)題：1.計劃展出10幅不同的畫,其中1幅水彩畫,4幅油畫,5幅國畫,排成一行陳列,要求同

一品種的必須連在一起，并且水彩畫不在兩端，那么共有陳列方式的種數(shù)為A2A5A42 5 45男生和5女生站成一排照像，男生相鄰,女生也相鄰的排法有A2A5A5種2 5 5正難則反總體淘汰策略例6.從0,1,2,3,4,5,6,7,8,9這十個數(shù)字中取出三個數(shù)，使其和為不小于10的偶數(shù),不同的取法有多少種？解：這問題中如果直接求不小于10的偶數(shù)很困難,可用總體淘汰法．這十個數(shù)字中有5個偶數(shù)5個奇數(shù)，所取的三個數(shù)含有3個偶數(shù)的取法有C3，只含有1個偶數(shù)的取法有C1C2，和為偶數(shù)的取法共有C1C2+C3?再淘汰和小于10的偶數(shù)共9種，符合條件的取5 5 5 5 5法共有C1C2+C3-95 5 5練習(xí)題：我們班里有43位同學(xué)，從中任抽5人，正、副班長、團支部書記至少有一人在內(nèi)的抽法有多少種?平均分組問題除法策略例7.6本不同的書平均分成3堆,每堆2本共有多少分法？解：分三步取書得C2C2C2種方法，但這里出現(xiàn)重復(fù)計數(shù)的現(xiàn)象,不妨記6本書為ABCDEF,6 4 2若第一步取AB,第二步取CD,第三步取EF該分法記為（AB,CD,EF）,則C2C2C2中還有6 4 2(AB,EF,CD),(CD,AB,EF),(CD,EF,AB)(EF,CD,AB),(EF,AB,CD)共有A3種取法，而這些分法3僅是（AB,CD,EF）僅是（AB,CD,EF）一種分法,故共有罟*12種分法.平均分成的組，不管它們的順序如何,都是一種情況，所以分組后要一定要除以An（nn為均分的組數(shù)）避免重復(fù)計數(shù)。練習(xí)題：1將13個球隊分成3組,一組5個隊,其它兩組4個隊,有多少分法（C5C4C4—138~A22.10名學(xué)生分成3組,其中一組4人,另兩組3人但正副班長不能分在同一組,有多少種不同的分組方法（1540）C2CC2C2A24 2_6A22=90)排2名，則不同的安排方案種數(shù)為 合理分類與分步策略例8.在一次演唱會上共10名演員,其中8人能能唱歌,5人會跳舞,現(xiàn)要演出一個2人唱歌2人伴舞的節(jié)目,有多少選派方法解：10演員中有5人只會唱歌，2人只會跳舞3人為全能演員．選上唱歌人員為標(biāo)準(zhǔn)進行研究只會唱的5人中沒有人選上唱歌人員共有C2C2種，只會唱的5人中只有1人選上唱TOC\o"1-5"\h\z3 3歌人員C1C1C2種，只會唱的5人中只有2人選上唱歌人員有C2C2種，由分類計數(shù)5 3 4 5 5原理共有C2C2+C1C1C2+C2C2種.3 3 5 3 4 5 5

例9.馬路上有編號為1,2,3,4,5,6,7,8,9的九只路燈,現(xiàn)要關(guān)掉其中的3盞,但不能關(guān)掉相鄰的2盞或3盞,也不能關(guān)掉兩端的2盞,求滿足條件的關(guān)燈方法有多少種？解：把此問題當(dāng)作一個排隊模型在6盞亮燈的5個空隙中插入3個不亮的燈有C3種一些不易理解的排列組合題如果能轉(zhuǎn)化為非常熟悉的模型，如占位填空模型，排隊模型，裝盒模型等，可使問題直觀解決練習(xí)題：某排共有10個座位，若4人就坐，每人左右兩邊都有空位，那么不同的坐法有多少種（120）十.實際操作窮舉策略例10.設(shè)有編號1,2,3,4,5的五個球和編號1,2,3,4,5的五個盒子,現(xiàn)將5個球投入這五個盒子內(nèi),要求每個盒子放一個球，并且恰好有兩個球的編號與盒子的編號相同,有多少投法解：從5個球中取出2個與盒子對號有C2種還剩下3球3盒序號不能對應(yīng)，利用實際操5作法，如果剩下3,4,5號球，3,4,5號盒,3號球只能裝入4號或5號盒,共兩種裝法,當(dāng)3號球裝4號盒時，則4,5號球只有1種裝法，同理3號球裝5號盒時,4,5號球有也只有1種裝法，由分步計數(shù)原理有2C2種.5練習(xí)題：同一寢室4人,每人寫一張賀年卡集中起來,然后每人各拿一張別人的賀年卡，則四張賀年卡不同的分配方式有多少種（9）給圖中區(qū)域涂色,要求相鄰區(qū)域不同色,現(xiàn)有4種可選顏色,則不同的著色方法有72種十一.分解與合成策略例16.30030能被多少個不同的偶數(shù)整除分析：先把30030分解成質(zhì)因數(shù)的乘積形式30030=2X3X5X7X11X13依題意可知偶因數(shù)必先取2,再從其余5個因數(shù)中任取若干個組成乘積所有的偶因數(shù)為：C1+C2+C3+C4+C55 5 5 5 5練習(xí):正方體的8個頂點可連成多少對異面直線.（是連成異面直線,所以包括對角線）解：我們先從8個頂點中任取4個頂點構(gòu)成四體共有體共C4-12二58,每個四面體有83對異面直線，正方體中的8個頂點可連成3x58=174對異面直線分解與合成策略是排列組合問題的一種最基本的解題策略,把一個復(fù)雜問題分解成幾個小問題逐一解決,然后依據(jù)問題分解后的結(jié)構(gòu),用分類計數(shù)原理和分步計數(shù)原理將問題合成,從而得到問題的答案,每個比較復(fù)雜的問題都要用到這種解題策略十二.化歸策略例12.25人排成5X5方陣，現(xiàn)從中選3人，要求3人不在同一行也不在同一列，不同的選法有多少種？解：將這個問題退化成9人排成3X3方陣，現(xiàn)從中選3人，要求3人不在同一行也不在同一列,有多少選法.這樣每行必有1人從其中的一行中選取1人后,把這人所在的行列都劃掉，如此繼續(xù)下去?從3X3方隊中選3人的方法有CiCiCi種?再從53 2 1X5方陣選出3X3方陣便可解決問題.從5X5方隊中選取3行3列有C3C3選法所5 5以從5X5方陣選不在同一行也不在同一列的3人有C3C3C1C1C1選法.從3x3方陣中任取3個5 5 3 2 1人時，因這三人不在同一行同一列，所以每行必有一人,據(jù)此,從每行任了練習(xí)題:某城市的街區(qū)由12個全等的矩形區(qū)組成，其中實線表示馬路，從A走到B的最短路徑有多少種（C3二35）7十三.數(shù)字排序問題查字典策略例13.由0，1，2，3，4，5六個數(shù)字可以組成多少個沒有重復(fù)的比324105大的數(shù)？解：N二2A沒有重復(fù)的比324105大的數(shù)？解：N二2A5+2A45 4數(shù)字排序問題可用據(jù)分類計文出其總數(shù),2,3,4,5這六個|A3+卅2+Ai3查字2由法根數(shù)原理求練習(xí):用0,旳1卩二297 Q查字典的法應(yīng)從高爭唆字組成沒有重復(fù)的向4次求出其符合要求的個數(shù),位偶數(shù)，?將這些數(shù)字從小到大排列起來,第71個數(shù)是3140十四.樹圖策略例14.3人相互傳球,由甲開始發(fā)球,并作為第一次傳球,經(jīng)過5次傳求后,球仍回到甲的手中,則不同的傳球方式有 N=10對于條件比較復(fù)雜的排列組合問題，不易用公式進行運算，樹圖會收到意想不到的結(jié)果二五.復(fù)雜分類問題表格策略例15．有紅、黃、蘭色的球各5只,分別標(biāo)有A、B、C、D、E五個字母,現(xiàn)從中取5只,要求各字母均有且三色齊備,則共有多少種不同的取法紅111223黃123121蘭321211取法C1C1C1C2C1C3C2C1C2C2C3C15454545 35 35 2一些復(fù)雜的分類選取題,要滿足的條件比較多,無從入手,經(jīng)常出現(xiàn)重復(fù)遺漏的情況,用表格法,則分類明確,能保證題中須滿足的條件,能達到好的效果.小結(jié)本節(jié)課，我們對有關(guān)排列組合的幾種常見的解題策略加以復(fù)習(xí)鞏固.排列組合歷來是學(xué)習(xí)中的難點，通過我們平時做的練習(xí)題，不難發(fā)現(xiàn)排列組合題的特點是條件隱晦，不易挖掘，題目多變，解法獨特，數(shù)字龐大，難以驗證.同學(xué)們只有對基本的解題策略熟練掌握.根據(jù)它們的條件,我們就可以選取不同的技巧來解決問題.對于一些比較復(fù)雜的問題,我們可以將幾種策略結(jié)合起來應(yīng)用把復(fù)雜的問題簡單化，舉一反三，觸類旁通，進而為后續(xù)學(xué)習(xí)打下堅實的基礎(chǔ)．解含有約束條件的排列組合問題，可按元素的性質(zhì)進行分類，按事件發(fā)生的連續(xù)過程分步做到標(biāo)