丙丁史上最全的排列組合難題大總結(jié)丙丁一.特殊元素和特殊位置優(yōu)先策略4,5可以組成多少個沒有重復(fù)數(shù)字五位奇數(shù).解:由于末位和首位有特殊要求,應(yīng)該優(yōu)先安排,以免不合要求的元素占了這兩個位置.先排末位共有C13然后排首位共有C144A344A3434分步計數(shù)原理得C1C1A3=288434位置分析法和元素分析法是解決排列組合問題最常用也是最基本的方法,若以元素分析為主,需先安排特殊元素,再處理其它元素.若以位置分析為主,需先滿足特殊位置的要求,再處理其它位置。若有多個約束條件，往往是考慮一端的花盆里，問有多少不同的種法二.相鄰元素捆綁策略例2.7人站成一排,其中甲乙相鄰且丙丁相鄰,共有多少種不同的排法.解：可先將甲乙兩元素捆綁成整體并看成一個復(fù)合元素，同時丙丁也看成一個復(fù)合元素，再與其它元素進(jìn)行排列，同時對相鄰元素內(nèi)部進(jìn)行自排。由分步計數(shù)原理可得共有A5A2A2=480種不同的排法522甲甲乙要求某幾個元素必須排在一起的問題,可以用捆綁法來解決問題.即將需 數(shù)為20 三.不相鄰問題插空策略目的出場順序有多少種5步排好的6個元素中間包含首尾兩個空位共有種A4不同的方法,由分步計數(shù)原6理,節(jié)目的不同順序共有A5A4種元素相離問題可先把沒有位置要求的元素進(jìn)行排隊再把不相鄰元練習(xí)題：某班新年聯(lián)歡會原定的5個節(jié)目已排成節(jié)目單，開演前又增加了兩個新節(jié)目.如果將這兩個新節(jié)目插入原節(jié)目單中，且兩個新節(jié)目不相鄰，那么不同 插法的種數(shù)為30 四.定序問題倍縮空位插入策略例人排隊,其中甲乙丙3人順序一定共有多少不同的排法解:(倍縮法)對于某幾個元素順序一定的排列問題,可先把這幾個元素與其他元素一起進(jìn)行排列,然后用總排列數(shù)除以這幾個元素之間的全排列數(shù),則同排法種數(shù)是：A7/A373(空位法)設(shè)想有7把椅子讓除甲乙丙以外的四人就坐共有A4種方法，其余的7三個位置甲乙丙共有1種坐法，則共有A4種方法。7思考:可以先讓甲乙丙就坐嗎(插入法)先排甲乙丙三個人,共有1種排法,再把其余4四人依次插入共有方法定序問題可以用倍縮法，還可轉(zhuǎn)化高逐漸增加，共有多少排法5五.重排問題求冪策略解:完成此事共分六步:把第一名實習(xí)生分配到車間有7種分法.把第二名實習(xí)生分配到車間也有7種分依此類推,由分步計數(shù)原理共有76種不同的排法允允許重復(fù)的排列問題的特點是以元素為研究對象，元素不受位置的約束，可以排各個元素的位置，一般地n不同的元素沒有限制地安排在m個位置上1．某班新年聯(lián)歡會原定的5個節(jié)目已排成節(jié)目單，開演前又增加了兩個新節(jié)目. 如果將這兩個節(jié)目插入原節(jié)目單中，那么不同插法的種數(shù)為42 方法 六.環(huán)排問題線排策略4并從此位置把圓形展成直線其余7人共有(8-1)！種排法即7！CDBABCDEFGHAG一般地,一般地,n個不同元素作圓形排列,共有(n-1)!種排法.如果從n個不同元素nnn七.多排問題直排策略例人排成前后兩排,每排4人,其中甲乙在前排,丙在后排,共有多少排法4 54455前排4 后排一一般地,元素分成多排的排列問題,可歸結(jié)為一排考前排中間的3個座位不能坐，并且這2人不左右相鄰，那么不同排法的種數(shù)是346八.排列組合混合問題先選后排策略裝法.5一個復(fù)合元素)裝入4個不同的盒內(nèi)有A4種方法，根據(jù)分步計數(shù)原理裝球4的方法共有C2A454解決排列組合混合問題,先選后排是最基本的指導(dǎo)思想.此法與相鄰元素務(wù),每人完成一種任務(wù),且正副班長有且只有1人參加,則不同的選法有192種九.小集團(tuán)問題先整體后局部策略個奇數(shù)之間,這樣的五位數(shù)有多少個解：把1,5,2,4當(dāng)作一個小集團(tuán)與3排隊共有A2種排法，再排小集團(tuán)內(nèi)部2共有A2A2種排法，2共有A2A2種排法，2 222 小集團(tuán)排列問題中，先整體后局部，再結(jié)合其它策要求同一品種的必須連在一起，并且水彩畫不在兩端，那么共有陳列 254 255 十.元素相同問題隔板策略解：因為10個名額沒有差別，把它們排成一排。相鄰名額之間形成9個空隙。在9個空檔中選6個位置插個隔板，可把名額分成7份，對應(yīng)地分給7個班級，每一種插板方法對應(yīng)一種分法共有C6種分法。9一班五班二班三班六班七班一班五班二班三班六班七班四四班將將n個相同的元素分成m份(n，m為正整數(shù)),每份至少一個元素,可xyz+w=100求這個方程組的自然數(shù)解的組數(shù)十一.正難則反總體淘汰策略493偶數(shù),不同的取法有多少種解：這問題中如果直接求不小于10的偶數(shù)很困難,可用總體淘汰法。這十個5C55555數(shù)共9種，符合條件的取法共有C1C2+C39555有有些排列組合問題,正面直接考慮比較復(fù)雜,而它的反面往往比較人在內(nèi)的抽法有多少種十二.平均分組問題除法策略解:分三步取書得C2C2C2種方法,但這里出現(xiàn)重復(fù)計數(shù)的現(xiàn)象,不妨記6本書為 則中還有(AB,EF,CD),(CD,AB,EF),(CD,EF,AB)(EF,CD,AB),(EF,AB,CD)共有A3種取3法,而這些分法僅是(AB,CD,EF)一種分法,故共有C2C2C2/A3種分法。3平平均分成的組,不管它們的順序如何,都是一種情況,所以分組后要一定要除以An(n為均分的組數(shù))避免重復(fù)計數(shù)。n種不同的分組方法(1540)3.某校高二年級共有六個班級，現(xiàn)從外地轉(zhuǎn)個班級且每班安十三.合理分類與分步策略入4名學(xué)生，要安排到該年級的兩4262為標(biāo)準(zhǔn)進(jìn)行研究 33 53455種，由分類計數(shù)原理共有3353455男生又有女生，則不同的選法共有34方法.(27)下分類標(biāo)準(zhǔn)：否選上跳舞人員為標(biāo)準(zhǔn)都可經(jīng)得到正確結(jié)果十四.構(gòu)造模型策略不能關(guān)掉相鄰的2盞或3盞,也不能關(guān)掉兩端的2盞,求滿足條件的關(guān)燈方法有多少種5 種一一些不易理解的排列組合題如果能轉(zhuǎn)化為非常熟悉的模型，如占位填空模坐法有多少種(120)十五.實際操作窮舉策略投入這五個盒子內(nèi),要求每個盒子放一個球，并且恰好有兩個球的編號與盒子的編號相同,有多少投法分解成幾個小問題逐一解決,然后依據(jù)問題分解后的結(jié)構(gòu),用分類計數(shù)原理分解成幾個小問題逐一解決,然后依據(jù)問題分解后的結(jié)構(gòu),用分類計數(shù)原理十七.化歸策略5裝法,由分步計數(shù)原理有2C2種5534對對于條件比較復(fù)雜的排列組合問題，不易用公式進(jìn)行運(yùn)算，往往利用窮舉法1.同一寢室4人,每人寫一張賀年卡集中起來,然后每人各拿一張別人的賀年卡，則四張賀年卡不同的分配方式有多少種(9)2.給圖中區(qū)域涂色,要求相鄰區(qū)域不同色,現(xiàn)有4種可選顏色,則不同的著色方法11425十六.分解與合成策略依題意可知偶因數(shù)必先取2,再從其余5個因數(shù)中任取若干個組成乘C1+C2+C3+C4+C555555個頂點可連成多少對異面直線 8 面體有分分解與合成策略是排列組合問題的一種最基本的解題策略,把一個復(fù)雜問題同的選法有多少種化成一個簡要的問題，通過解決這個簡要的問化成一個簡要的問題，通過解決這個簡要的問:行必有1人從其中的一行中選取1繼續(xù)下去.從3×3方隊中選3人的 1 55 55321處處理復(fù)雜的排列組合問題時可以把一個問題退練習(xí)題:某城市的街區(qū)由12個全等的矩形區(qū)組成其中實線表示馬路，從A走到B的最短路徑有多少種(C3=35)7BA十八.數(shù)字排序問題查字典策略數(shù)解:N=2A5+2A4+A3+A2+A1=29754321數(shù)字排序問題可用查字典法,查字典的法應(yīng)從高位向低位查,依次求出其符合要求的個數(shù),根據(jù)分類計練習(xí):用0,1,2,3,4,5這六個數(shù)字組成沒有重復(fù)的四位偶數(shù),將這些數(shù)字從小到大 十九.樹圖策略例19．3人相互傳球,由甲開始發(fā)球,并作為第一次傳球,經(jīng)過5次傳求后,球仍回到對于條件比較復(fù)雜的排列組合問的不同坐法有多少種N=44二十.復(fù)雜分類問題表格策略5只,要求各字母均有且三色齊備,則共有多少種不同的取法紅紅黃蘭取法53221311212122131113532545454一一些復(fù)雜的分類選取題,要滿足的條件比較多,無從入手,二十一：住店法策略解決“允許重復(fù)排列問題”要注意區(qū)分兩類元素：一類元素可以重復(fù)，另一類不能重復(fù)，把不能重復(fù)的元素看作“客”，能重復(fù)的元素看作“店”，再利用乘法原理直接求解.家“店”，五項冠軍看作5名“客”，每個“客”有7種住宿法，由乘法原理得75種.染色問題的計數(shù)方法根據(jù)乘法原理，對各個區(qū)域分步染色，這是處理這類問題的基本的要用四種顏色給四川、青藏、西藏、云南四省(區(qū))的地圖染色(圖1)每一省(區(qū))一種顏色，只要求相鄰的省(區(qū))不同色，則不同染色的方法有多少種西藏根據(jù)乘法原理，不同的染色方法共有4×3×2×2＝48種2.根據(jù)共用了多少種顏色分類討論，分別計算出各種情形的種數(shù)，再用加法原理求出不同年拾方法種數(shù)。544例2(2003年全國高考題)如圖2，一個地區(qū)分為5個行政區(qū)域，現(xiàn)給地圖著色，要求相鄰區(qū)域不得使用同一顏色，現(xiàn)有4種顏色可供選擇，則不同的著色方法共有多少種23154圖2分析依題意至少要選用3種顏色。4444由加法原理可知滿足題意的著色方法共有A3＋2A4＝24＋2×24＝72種。443.根據(jù)某兩個不相鄰區(qū)域是否同色分類討論，從某兩個不相鄰區(qū)域同色與不例3用紅、黃、藍(lán)、白、黑五種顏色涂在“田”字形的四個小方格內(nèi)(圖3)，每格涂一種顏色，相鄰的兩格涂不同的顏色，如果顏色可以反復(fù)使用，共有多少種不同的涂色方法2134(1)四格涂不同的顏色，方法數(shù)為A4；5(2)有且僅有兩格涂相同的顏色，即只有一組對角小方格涂相同顏色，涂(1)兩組對角小方格涂相同顏色，涂法種數(shù)為A2。因此，所求的涂法種數(shù)5為A4＋2C1A2＋A2＝260種55453.根據(jù)相間區(qū)域使用顏色的種類分類討論著色，要求同一區(qū)域染同一種顏色，相鄰的兩個區(qū)域不得使用FFABEDC同一顏色，現(xiàn)有4種不同的顏色可供選擇，則有多少種不同的著色方法。44(1)當(dāng)相間區(qū)域A、C、E著三種不同顏色時，有A3種著色方法，此時B、D、44＋192＝732種方法二點染色問題點染色問題，要注意對各點依次染色，主要方法有:(1)根據(jù)共用了多少種顏色分類討論；(2)根據(jù)相對頂點是否同色分類討論。種顏色，并使同一條棱的兩端點異色，如果有5種顏色可供使用，那么不同的染色方法SSDCA序序色這總數(shù)是多少解法1滿足題設(shè)條件的染色至少要用三種顏色(1)若恰用三種顏色，可先從五種顏色中任選一種染頂點S，再從余下的(1)若恰用四種顏色，可先從五種顏色中任選一種染頂點S，再從余下的四種顏色中任選兩種染A與B，由于A、B顏色可以交換，故有A2種染法；45422(1)若恰用五種顏色，有A5＝120種染法。綜上，滿足題意的染色方法數(shù)5SSDCA原理，總的染色方法數(shù)是60×7＝420種的兩個問題，盡管與例5表述方式不同，但具有相同的數(shù)學(xué)模型，所以都可(1)用五種顏色給圖中的5個車站的候DC車牌A、B、C、D、E染色，要求相鄰兩個車站間E的候車牌的顏色不同，有多少種不同的染色方AB法(圖6)著色，要求相鄰的區(qū)域不同色，共有多少種方案三、線段染色問題，要注意對各條線段依次討論，主要方法有：(1)根據(jù)共用了多少種顏色分類討論；(2)根據(jù)相對的線段是否同色分類討論。例5用紅、黃、藍(lán)、白、四種顏色染矩形ABCD的四條邊，每條邊只染一種顏色，且使相鄰兩邊染不同的顏色，如果顏色可能反復(fù)使用，共有多少種不同的染色方法(圖8)解法1(1)使用四種顏色有A4種；4(2)使用三種顏色染色，則必須將一組對染成同色，故有C1C1A2種；423(3)使用兩種顏色時，則兩組對邊必須分CCADB邊別同色，有A2種。4因此，所求的染色方法數(shù)為A4＋C1C1A2＋A2＝84種44234由乘法原理，總的染色方法數(shù)為12×7＝84種。利用相同的方法可解決例7同種顏色的服裝，且相鄰兩個區(qū)域的顏色不同，不相鄰區(qū)域顏色相同與否不14受限制，那么不同的著色方法共有多少種例7用六種顏色給正四面體A－BCD的每條棱染色，要求每條棱只能染一種顏色且共頂點的棱染不同的顏色，問有多少種不同的染色方法(圖染色至少要用三種顏色。解(1)若恰用三種顏色染色，則每組對棱必須染同一顏色，而這三組間的顏色不同，故有A3種方法。6(2)若恰用四種顏色染色，則三組對棱中有兩組對棱