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

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

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

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

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

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

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

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

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

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

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

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

12、同一 品種的必須連在一起，并且水彩畫不在兩端，那么共有陳列方式的種數(shù)為A22A55A 442. 5 男生和女生站成一排照像 ,男生相鄰 ,女生也相鄰的排法有 A22A55A55種十. 元素相同問題隔板策略 例 10. 有 10 個運(yùn)動員名額，分給 7 個班，每班至少一個 , 有多少種分配方案？解：因?yàn)?10 個名額沒有差別，把它們排成一排。相鄰名額之間形成個空隙。在個空檔中選 個位置插個隔板，可把名額分成份，對應(yīng)地分給個班級，每一種插板方法對應(yīng)一種分法 6共有 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ù)C1303十一 .正難則反總體淘汰策略例 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ù)的取1 23 1 2

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

15、CD, 第 三 步 取 EF 該 分 法 記 為 (AB,CD,EF), 則 C62C42C22 中 還 有3 (AB,EF,CD),(CD,AB,EF),(CD,EF,AB)(EF,CD,AB),(EF,AB,CD)共有 A33 種取法 , 而這些分法僅是(AB,CD,EF) 一種分法 ,故共有 C62C42C22 / A 33種分法。平均分成的組 ,不管它們的順序如何 ,都是一種情況 ,所以分組后要一定要除以Ann ( n為均分的組數(shù) )避免重復(fù)計(jì)數(shù)。練習(xí)題：1 將 13 個球隊(duì)分成 3組, 一組 5個隊(duì),其它兩組 4個隊(duì), 有多少分法？( C153C84C44 / A22)2.10 名學(xué)

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

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

18、船只能乘 1人,他們?nèi)芜x 2 只船 或 3 只船 , 但小孩不能單獨(dú)乘一只船 , 這 3 人共有多少乘船方法 . （ 27） 本題還有如下分類標(biāo)準(zhǔn)：*以 3個全能演員是否選上唱歌人員為標(biāo)準(zhǔn)*以 3個全能演員是否選上跳舞人員為標(biāo)準(zhǔn)*以只會跳舞的 2 人是否選上跳舞人員為標(biāo)準(zhǔn)都可經(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)燈方法有多少種？3 解：把此問題當(dāng)作一個排隊(duì)模型在 6 盞亮燈的 5 個空隙中插入 3 個不亮的燈有 C53

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

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

21、整除分析：先把 30030 分解成質(zhì)因數(shù)的乘積形式 30030=2× 3×5 × 7 ×11×13 依題意可知偶因數(shù)必先取 2, 再從其余 5 個因數(shù)中任取若干個組成乘積， 所有的偶因數(shù)為： C51 C52 C53 C54 C55練習(xí) : 正方體的 8 個頂點(diǎn)可連成多少對異面直線解：我們先從 8個頂點(diǎn)中任取 4 個頂點(diǎn)構(gòu)成四體共有體共 C84 12 58 ,每個四面體有3 對異面直線 , 正方體中的 8 個頂點(diǎn)可連成 3 58 174 對異面直線 分解與合成策略是排列組合問題的一種最基本的解題策略,把一個復(fù)雜問題分解成幾個小問題逐一解決 ,然后

22、依據(jù)問題分解后的結(jié)構(gòu) ,用分類計(jì)數(shù)原理和分步計(jì)數(shù)原理將問題合成,從而得到問題的答案 ,每個比較復(fù)雜的問題都要用到這種解題策略十七 .化歸策略例 17. 25 人排成 5× 5 方陣 , 現(xiàn)從中選 3 人 , 要求 3 人不在同一行也不在同一列 , 不同的選法有多少種？ 解：將這個問題退化成 9 人排成 3× 3方陣,現(xiàn)從中選 3人, 要求 3人不在同一行也不在同一列 有多少選法 . 這樣每行必有 1 人從其中的一行中選取 1 人后 , 把這人所在的行列都劃掉，如 111此繼續(xù)下去 . 從 3× 3方隊(duì)中選 3 人的方法有 C31C21C11種。再從 5×

23、 5方陣選出 3×3 方陣便可33A 走到 B 的最短路徑有多少解決問題 . 從 5×5方隊(duì)中選取 3行 3 列有 C53 C53選法所以從 5×5方陣選不在同一行也不在3 3 1 1 1同一列的 3 人有 C53C53C31C21C11選法。處理復(fù)雜的排列組合問題時(shí)可以把一個問題退化成一個簡 要的問題， 通過解決這個簡要的問題的解決找到解題方法， 從而進(jìn)下一步解決原來的問題練習(xí)題 :某城市的街區(qū)由 12 個全等的矩形區(qū)組成其中實(shí)線表示馬路，從 種？( C73 35)十八 .數(shù)字排序問題查字典策略324105 大的數(shù)？例 18由 0，1，2，3，4，5 六個數(shù)字可以組成多少個沒有重復(fù)的比 解: N 2A55 2A44 A3