排列組合的二十種解法(最全的排列組合方法總結(jié))

1、第一講：排列組合的二十種策略教學(xué)目標(biāo)1. 進一步理解和應(yīng)用分步計數(shù)原理和分類計數(shù)原理。2. 掌握解決排列組合問題的常用策略 ; 能運用解題策略解決簡單的綜合應(yīng)用題。提高學(xué)生解決問題分析問題的能力3. 學(xué)會應(yīng)用數(shù)學(xué)思想和方法解決排列組合問題.復(fù)習(xí)鞏固1. 分類計數(shù)原理 ( 加法原理 )完成一件事，有n 類辦法， 在第 1 類辦法中有 m1 種不同的方法，在第2 類辦法中有 m2 種不同的方法， ，在第n 類辦法中有 mn 種不同的方法，那么完成這件事共有：N m1 m2 L mn種不同的方法2. 分步計數(shù)原理（乘法原理）完成一件事， 需要分成 n 個步驟， 做第 1 步有 m1 種不同的方法，

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

3、合綜合性問題，往往類與步交叉，因此必須掌握一些常用的解題策略一. 特殊元素和特殊位置優(yōu)先策略例 1. 由 0,1,2,3,4,5可以組成多少個沒有重復(fù)數(shù)字五位奇數(shù).解: 由于末位和首位有特殊要求, 應(yīng)該優(yōu)先安排 ,以免不合要求的元素占了這兩個位置.先排末位共有 C31然后排首位共有C41最后排其它位置共有A43由分步計數(shù)原理得C41C31 A43288131C4A 4C3位置分析法和元素分析法是解決排列組合問題最常用也是最基本的方法, 若以元素分析為主 , 需先安排特殊元素, 再處理其它元素 . 若以位置分析為主, 需先滿足特殊位置的要求, 再處理其它位置。若有多個約束條件，往往是考慮一個約束

4、條件的同時還要兼顧其它條件練習(xí)題 :7 種不同的花種在排成一列的花盆里, 若兩種葵花不種在中間，也不種在兩端的花盆里，問有多少不同的種法？二. 相鄰元素捆綁策略例 2. 7 人站成一排 ,其中甲乙相鄰且丙丁相鄰, 共有多少種不同的排法 .解：可先將甲乙兩元素捆綁成整體并看成一個復(fù)合元素，同時丙丁也看成一個復(fù)合元素，再與其它元素進行排列，同時對相鄰元素內(nèi)部進行自排。由分步計數(shù)原理可得共有A55 A22 A22480 種不同的排法甲 乙丙 丁睿思數(shù)學(xué)計數(shù)原理和概率要求某幾個元素必須排在一起的問題,可以用捆綁法來解決問題.即將需要相鄰的元素合并為一個元素 ,再與其它元素一起作排列,同時要注意合并元素

5、內(nèi)部也必須排列.練習(xí)題 : 某人射擊 8 槍，命中 4 槍， 4 槍命中恰好有3 槍連在一起的情形的不同種數(shù)為20三. 不相鄰問題插空策略例 3. 一個晚會的節(jié)目有4 個舞蹈 ,2個相聲 ,3 個獨唱 , 舞蹈節(jié)目不能連續(xù)出場 , 則節(jié)目的出場順序有多少種？解: 分兩步進行第一步排2 個相聲和3 個獨唱共有 A55種，第二步將4 舞蹈插入第一步排好的6 個元素中間包含首尾兩個空位共有種A64不同的方法,由分步計數(shù)原理, 節(jié)目的不同順序共有A55A64種元素相離問題可先把沒有位置要求的元素進行排隊再把不相鄰元素插入中間和兩練習(xí)題：某班新年聯(lián)歡會原定的5 個節(jié)目已排成節(jié)目單，開演前又增加了兩個新節(jié)

6、目. 如果將這兩個新節(jié)目插入原節(jié)目單中，且兩個新節(jié)目不相鄰，那么不同插法的種數(shù)為30四. 定序問題倍縮空位插入策略例 4.7 人排隊 , 其中甲乙丙 3 人順序一定共有多少不同的排法解:( 倍縮法 ) 對于某幾個元素順序一定的排列問題, 可先把這幾個元素與其他元素一起進行排列, 然后用總排列數(shù)除以這幾個元素之間的全排列數(shù), 則共有不同排法種數(shù)是：A 77/ A33( 空位法 )設(shè)想有 7把椅子讓除甲乙丙以外的四人就坐共有A 74種方法，其余的三個位置甲乙丙共有 1 種坐法，則共有A 74 種方法。思考 : 可以先讓甲乙丙就坐嗎?（插入法 ) 先排甲乙丙三個人 , 共有 1種排法 , 再把其余

7、4四人依次插入共有方法定序問題可以用倍縮法，還可轉(zhuǎn)化為占位插練習(xí)題 :10 人身高各不相等 , 排成前后排，每排5 人 , 要求從左至右身高逐漸增加，共有多少排法？C105五. 重排問題求冪策略例 5. 把 6 名實習(xí)生分配到7 個車間實習(xí) , 共有多少種不同的分法解 : 完成此事共分六步 : 把第一名實習(xí)生分配到車間有 7 種分法 . 把第二名實習(xí)生分配到車間也有 7 種分依此類推 , 由分步計數(shù)原理共有 76 種不同的排法允許重復(fù)的排列問題的特點是以元素為研究對象，元素不受位置的約束，可以逐一安排各個元素的位置，一般地 n 不同的元素沒有限制地安排在m 個位置上的排列數(shù)為mn 種練習(xí)題：1

8、 某班新年聯(lián)歡會原定的5 個節(jié)目已排成節(jié)目單，開演前又增加了兩個新節(jié)目. 如果將這兩個節(jié)目插入原節(jié)目單中，那么不同插法的種數(shù)為422. 某 8 層大樓一樓電梯上來8 名乘客人 , 他們到各自的一層下電梯 , 下電梯的方法 78六. 環(huán)排問題線排策略例 6. 8 人圍桌而坐 , 共有多少種坐法 ?A44解：圍桌而坐與坐成一排的不同點在于，坐成圓形沒有首尾之分，所以固定一人并從此位置把圓形展成直線其余7 人共有（ 8-1 ）！種排法即7 ！睿思數(shù)學(xué)計數(shù)原理和概率CDBEAABCDEFGHAFHG一般地 ,n 個不同元素作圓形排列,共有 (n-1)! 種排法 .如果從n 個不同元素中取出m 個元素作

9、圓1m形排列共有A n練習(xí)題： 6 顆顏色不同的鉆石，可穿成幾種鉆石圈120七. 多排問題直排策略例 7.8 人排成前后兩排 , 每排 4人 , 其中甲乙在前排 , 丙在后排 , 共有多少排法解 :8 人排前后兩排 , 相當(dāng)于 8 人坐 8 把椅子 , 可以把椅子排成一排 . 個特殊元素有 A42種,再排后 4個位置上的特殊元素丙有A14 種 , 其余的 5 人在 5 個位置上任意排列有A55種, 則共有 A 42 A14 A 55種前 排后 排一般地 ,元素分成多排的排列問題,可歸結(jié)為一排考慮,再分段研練習(xí)題：有兩排座位，前排11 個座位，后排12 個座位，現(xiàn)安排 2 人就座規(guī)定前排中間的3

10、 個座位不能坐，并且這 2 人不左右相鄰，那么不同排法的種數(shù)是346八. 排列組合混合問題先選后排策略例 8. 有 5 個不同的小球 , 裝入 4 個不同的盒內(nèi) , 每盒至少裝一個球, 共有多少不同的裝法 .解 : 第一步從 5 個球中選出2 個組成復(fù)合元共有C52 種方法 . 再把 4 個元素 ( 包含一個復(fù)合元素 ) 裝入 4 個不同的盒內(nèi)有A 44 種方法，根據(jù)分步計數(shù)原理裝球的方法共有C52 A44解決排列組合混合問題,先選后排是最基本的指導(dǎo)思想.此法與相鄰元素捆綁策略相似嗎?練習(xí)題：一個班有 6 名戰(zhàn)士 , 其中正副班長各1 人現(xiàn)從中選4 人完成四種不同的任務(wù) , 每人完成一種任務(wù)

11、, 且正副班長有且只有1 人參加 , 則不同的選法有192種九. 小集團問題先整體后局部策略例 9. 用 1,2,3,4,5 組成沒有重復(fù)數(shù)字的五位數(shù)其中恰有兩個偶數(shù)夾1, 在兩個奇數(shù)之間, 這樣的五位數(shù)有多少個？解：把 , , , 當(dāng)作一個小集團與排隊共有A22 種排法，再排小集團內(nèi)部共有 A 22 A 22 種排法，由分步計數(shù)原理共有A22 A 22A 22 種排法 .15243小集團排列問題中，先整體后局部，再結(jié)合其它策略進行處理。練習(xí)題： . 計劃展出 10 幅不同的畫, 其中 1 幅水彩畫 , 幅油畫 , 幅國畫 ,排成一行陳列, 要求同一品種的必須連在一起，并且水彩畫不在兩端，那么

12、共有陳列方式的種數(shù)為A22A55 A442. 5 男生和女生站成一排照像, 男生相鄰 , 女生也相鄰的排法有A22 A55 A55 種睿思數(shù)學(xué)計數(shù)原理和概率十. 元素相同問題隔板策略例 10. 有 10 個運動員名額，分給7 個班，每班至少一個, 有多少種分配方案？解：因為 10 個名額沒有差別，把它們排成一排。相鄰名額之間形成個空隙。在個空檔中選個位置插個隔板，可把名額分成份，對應(yīng)地分給個班級，每一種插板方法對應(yīng)一種分法共有 C96 種分法。一二三四五六七班班班班班班班將 n 個相同的元素分成m 份（ n， m 為正整數(shù)） ,每份至少一個元素 ,可以用 m-1塊隔板，插入 n 個元素排成一排

13、的n-1 個空隙中，所有分法數(shù)為 Cnm11練習(xí)題：1 10 個相同的球裝5 個盒中 , 每盒至少一有多少裝法？C942 . x y z w 100 求這個方程組的自然數(shù)解的組數(shù)C1033十一 . 正難則反總體淘汰策略例 11. 從 0,1,2,3,4,5,6,7,8,9這十個數(shù)字中取出三個數(shù)，使其和為不小于10的偶數(shù) , 不同的取法有多少種？解：這問題中如果直接求不小于10的偶數(shù)很困難 , 可用總體淘汰法。這十個數(shù)字中有5個偶數(shù)5 個奇數(shù) , 所取的三個數(shù)含有3 個偶數(shù)的取法有 C53,只含有 1個偶數(shù)的取法有C51C52, 和為偶數(shù)的取法共有 C51C52C53。再淘汰和小于10 的偶數(shù)共

14、9 種，符合條件的取法共有C51C52C539有些排列組合問題, 正面直接考慮比較復(fù)雜 ,而它的反面往往比較簡捷,可以先求出它的反面 ,再從整體中淘汰 .練習(xí)題：我們班里有43 位同學(xué) , 從中任抽5 人 , 正、副班長、團支部書記至少有一人在內(nèi)的抽法有多少種 ?十二 . 平均分組問題除法策略例 12.6本不同的書平均分成3 堆 , 每堆 2 本共有多少分法？解 :分三步取書得 C62 C42C22種方法 , 但這里出現(xiàn)重復(fù)計數(shù)的現(xiàn)象, 不妨記 6 本書為 ABCDEF，若第一步取 AB,第二步取CD, 第 三 步 取 EF 該 分 法 記 為 (AB,CD,EF),則 C62C42C22中

15、還 有(AB,EF,CD),(CD,AB,EF),(CD,EF,AB)(EF,CD,AB),(EF,AB,CD)共有 A33種取法 , 而這些分法僅是 (AB,CD,EF) 一種分法 , 故共有 C62C42C22 / A33 種分法。平均分成的組 ,不管它們的順序如何,都是一種情況 ,所以分組后要一定要除以A nn ( n 為均分的組數(shù) )避免重復(fù)計數(shù)。練習(xí)題：1 將 13 個球隊分成 3 組 , 一組 5 個隊 , 其它兩組 4 個隊 , 有多少分法？（ C135C84C44 / A 22 ）2.10 名學(xué)生分成 3 組 , 其中一組 4人 ,另兩組 3 人但正副班長不能分在同一組, 有多

16、少種不同的分組方法 （1540 ）3. 某校高二年級共有六個班級，現(xiàn)從外地轉(zhuǎn)入 4 名學(xué)生，要安排到該年級的兩個班級且每班安排 2名，則不同的安排方案種數(shù)為_（ C42 C22 A62 / A22 90 ）十三 .合理分類與分步策略睿思數(shù)學(xué)計數(shù)原理和概率例 13. 在一次演唱會上共 10 名演員 , 其中 8 人能能唱歌 ,5 人會跳舞 , 現(xiàn)要演出一個 2 人唱歌 2 人伴舞的節(jié)目 , 有多少選派方法解： 10 演員中有5 人只會唱歌，2 人只會跳舞3 人為全能演員。選上唱歌人員為標(biāo)準進行研究只會唱的5 人中沒有人選上唱歌人員共有C32C32 種,只會唱的5 人中只有 1 人選上唱歌人員C5

17、1C31C42種 , 只會唱的 5 人中只有2 人選上唱歌人員有C52C52種，由分類計數(shù)原理共有C32C32C51C31C42C52C52 種。解含有約束條件的排列組合問題， 可按元素的性質(zhì)進行分類， 按事件發(fā)生的連續(xù)過程分步， 做到標(biāo)準明確。分步層次清楚，不重不漏，分類標(biāo)準一旦確定要貫穿于解題過程的始終。練習(xí)題：1. 從 4 名男生和 3 名女生中選出 4 人參加某個座 談會，若這 4 人中必須既有男生又有女生， 則不同的選法共有 342. 3 成人 2 小孩乘船游玩,1 號船最多乘3 人, 2 號船最多乘2 人 ,3 號船只能乘1 人 , 他們?nèi)芜x2 只船或 3 只船 , 但小孩不能單獨

18、乘一只船,這 3 人共有多少乘船方法.（ 27）本題還有如下分類標(biāo)準：* 以 3 個全能演員是否選上唱歌人員為標(biāo)準* 以 3 個全能演員是否選上跳舞人員為標(biāo)準* 以只會跳舞的 2 人是否選上跳舞人員為標(biāo)準都可經(jīng)得到正確結(jié)果十四 . 構(gòu)造模型策略例 14. 馬路上有編號為 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 個不亮的燈有 C53種一些不易理解的排列組合題如果能轉(zhuǎn)化為非常熟悉的模型，如占位填空模型， 排

19、隊模型， 裝盒模型等，可使問題直觀解決練習(xí)題：某排共有 10 個座位，若 4 人就坐，每人左右兩邊都有空位，那么不同的坐法有多少種？ （ 120）十五 . 實際操作窮舉策略例 15. 設(shè)有編號1,2,3,4,5的五個球和編號1,2,3,4,5的五個盒子 , 現(xiàn)將 5 個球投入這五個盒子內(nèi),要求每個盒子放一個球，并且恰好有兩個球的編號與盒子的編號相同, 有多少投法解：從 5 個球中取出 2 個與盒子對號有C52種還剩下3 球 3 盒序號不能對應(yīng)， 利用實際操作法， 如果剩下3,4,5 號球 , 3,4,5號盒 3號球裝 4號盒時，則 4,5號球有只有 1種裝法，同理 3號球裝 5號盒時 ,4,5

20、號球有也只有 1種裝法 ,由分步計數(shù)原理有2C52 種5343號盒4號盒5號盒對于條件比較復(fù)雜的排列組合問題，不易用公式進行運算，往往利用窮舉法或畫出樹狀圖會收到意想不到的結(jié)果練習(xí)題：1.同一寢室 4 人, 每人寫一張賀年卡集中起來, 然后每人各拿一張別人的賀年卡， 則四張賀年卡不同的分配方式有多少種？(9)2.給圖中區(qū)域涂色 , 要求相鄰區(qū)域不同色 , 現(xiàn)有 4 種可選顏色 , 則不同的著色方法有 72 種睿思數(shù)學(xué)計數(shù)原理和概率13245十六 .分解與合成策略例 16. 30030能被多少個不同的偶數(shù)整除分析：先把 30030 分解成質(zhì)因數(shù)的乘積形式 30030=2 ×3×

21、; 5 × 7 × 11× 13 依題意可知偶因數(shù)必先取 2, 再從其余 5 個因數(shù)中任取若干個組成乘積，所有的偶因數(shù)為： C51C52C53C54C55練習(xí) : 正方體的 8 個頂點可連成多少對異面直線解：我們先從 8 個頂點中任取4 個頂點構(gòu)成四體共有體共C8412 58 , 每個四面體有3 對異面直線 , 正方體中的8 個頂點可連成3 58174對異面直線分解與合成策略是排列組合問題的一種最基本的解題策略,把一個復(fù)雜問題分解成幾個小問題逐一解決 ,然后依據(jù)問題分解后的結(jié)構(gòu),用分類計數(shù)原理和分步計數(shù)原理將問題合成,從而得到問題的答案 ,每個比較復(fù)雜的問題都要用

22、到這種解題策略十七 . 化歸策略例 17.25 人排成 5× 5 方陣 , 現(xiàn)從中選3 人 , 要求 3 人不在同一行也不在同一列, 不同的選法有多少種？解：將這個問題退化成 9 人排成 3× 3 方陣 , 現(xiàn)從中選 3人,要求 3人不在同一行也不在同一列 ,有多少選法 . 這樣每行必有1 人從其中的一行中選取1 人后 , 把這人所在的行列都劃掉，如此繼續(xù)下去 . 從 3× 3 方隊中選3 人的方法有 C31C21C11種。再從5×5 方陣選出3× 3 方陣便可解決問題 . 從 5× 5 方隊中選取3 行 3 列有 C53C53選法所以從5×5 方陣選不在同一行也不在同一列的 3 人有 C53C53C31C21C11選法。處理復(fù)雜的排列組合問題時可以把一個問題退化成一個簡要的問題，通過解決這個簡要的問題的解決找到解題方法，從而進下一步解決原來的問題練習(xí)題 : 某城市的街區(qū)由12 個全等的矩形區(qū)組成其中實線表示馬路，從A 走到 B 的最短路徑有多少種？( C