1、排列組合問題的 20 種解法排列組合問題聯系實際生動有趣，但題型多樣，思路靈活，因此解決排列組合問題，首 先要認真審題， 弄清楚是排列問題、 組合問題還是排列與組合綜合問題； 其次要抓住問題的 本質特征，采用合理恰當的方法來處理。復習鞏固 分類計數原理 （ 加法原理 ）完成一件事， 有 n類辦法， 在第 1類辦法中有 m1種不同的方法， 在第 2 類辦法中有 m2 種不同的方法，在第 n類辦法中有 mn 種不同的方法，那么完成這件事共有：N m1 m2mn種不同的方法2. 分步計數原理（乘法原理）完成一件事， 需要分成 n個步驟，做第 1步有 m1種不同的方法， 做第 2步有 m2種不同的方法

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

3、常用的解題策略一 . 特殊元素和特殊位置優先策略 例 1. 由 0,1,2,3,4,5 可以組成多少個沒有重復數字五位奇數, 應該優先安排以免不合要求的元素占了這兩個位置14A34解: 由于末位和首位有特殊要求 先排末位共有 C13 然后排首位共有 C14 最后排其它位置共有 A43由分步計數原理得 C41C13A43 288 位置分析法和元素分析法是解決排列組合問題最常用也是最基本的方法 , 若以元素分析為主 , 需 先安排特殊元素 , 再處理其它元素 .若以位置分析為主 ,需先滿足特殊位置的要求 , 再處理其它位練習題 :7 種不同的花種在排成一列的花盆里 , 若兩種葵花不種在中間， 也不

4、種在兩端的花盆 里，問有多少不同的種法二. 相鄰元素捆綁策略例 2. 7 人站成一排 , 其中甲乙相鄰且丙丁相鄰 , 共有多少種不同的排法 . 解：可先將甲乙兩元素捆綁成整體并看成一個復合元素， 同時丙丁也看成一個復合元素， 再 與其它元素進行排列，同時對相鄰元素內部進行自排。由分步計數原理可得共有522A55 A22 A22 480 種不同的排法要求某幾個元素必須排在一起的問題, 可以用捆綁法來解決問題 . 即將需要相鄰的元素合并 練習題 : 某人射擊 8 槍，命中 4 槍， 4 槍命中恰好有 3 槍連在一起的情形的不同種數為 20三. 不相鄰問題插空策略例 3. 一個晚會的節目有 4 個舞

5、蹈 ,2 個相聲 ,3 個獨唱 , 舞蹈節目不能連續出場 , 則節目的出場 順序有多少種解: 分兩步進行第一步排 2 個相聲和 3個獨唱共有 A55種，第二步將 4 舞蹈插入第一步排好的6 個元素中間包含首尾兩個空位共有種A 46不同的方法 ,由分步計數原理 , 節目的不同順序共有 A 55A 46種元素相離問題可先把沒有位置要求的元素進行排隊再把不相鄰元素插入中間和兩練習題：某班新年聯歡會原定的 5 個節目已排成節目單，開演前又增加了兩個新節目.如果將這兩個新節目插入原節目單中，且兩個新節目不相鄰，那么不同插法的種數為30四. 定序問題倍縮空位插入策略例人排隊 ,其中甲乙丙 3 人順序一定共

6、有多少不同的排法解:（ 倍縮法 ）對于某幾個元素順序一定的排列問題, 可先把這幾個元素與其他元素一起進行, 則共有不同排法種數排列, 然后用總排列數除以這幾個元素之間的全排列數是： A77/A33（空位法 ）設想有 7 把椅子讓除甲乙丙以外的四人就坐共有A74 種方法，其余的三個位置甲乙丙共有 1 種坐法，則共有 A47 種方法。思考: 可以先讓甲乙丙就坐嗎插入法 ）先排甲乙丙三個人 ,共有 1種排法 , 再把其余 4四人依次插入共有 方 法定序問題可以用倍縮法，還可轉化為占位插練習題 :10 人身高各不相等 ,排成前后排，每排 5 人,要求從左至右身高逐漸增加，共有多少 排法C150五. 重

7、排問題求冪策略 榆林教學資源網 例 5.把 6名實習生分配到 7個車間實習 , 共有多少種 不同的分法解:完成此事共分六步 : 把第一名實習生分配到車間有 7 種分法 .把第二名實習生分配到車 間也有 7 種分依此類推 , 由分步計數原理共有 76 種不同的排法允許重復的排列問題的特點是以元素為研究對象，元素不受位置的約束，可以逐一安排各個元素 的位置，一般地 n 不同的元素沒有限制地安排在 m個位置上的排列數為 mn 種 練習題：1 某班新年聯歡會原定的 5 個節目已排成節目單，開演前又增加了兩個新節目 . 如果將這 兩個節目插入原節目單中，那么不同插法的種數為 422. 某 8 層大樓一樓

8、電梯上來 8 名乘客人 , 他們到各自的一層下電梯 , 下電梯的方法 78六. 環排問題線排策略例 6. 8 人圍桌而坐 , 共有多少種坐法解：圍桌而坐與坐成一排的不同點在于，坐成圓形沒有首尾之分，所以固定一人A44 并從此位置把圓形展成直線其余 7 人共有（ 8-1 ）！種排法即 7 ！ABCDEFGHA一般地 ,n 個不同元素作圓形排列 , 共有（n-1）! 種排法 . 如果從 n 個不同元素中取出 m個元素作1 圓形排列共有 3A榆nm林教學資源網第 3 頁 共 10 頁n練習題： 6 顆顏色不同的鉆石，可穿成幾種鉆石圈 120七. 多排問題直排策略例人排成前后兩排 ,每排 4人,其中甲

9、乙在前排 ,丙在后排 ,共有多少排法解:8 人排前后兩排 ,相當于 8人坐 8把椅子 ,可以把椅子排成一排 .個特殊元素有 A24種,再排后 4個位置上的特殊元素丙有 A14種,其余的 5人在 5個位置上任意排列有 A55種,2 1 5 則共有 A24A14 A55種前 排 后 排般地 ,元素分成多排的排列問題 , 可歸結為一排考慮 , 再分段研練習題：有兩排座位，前排 11 個座位，后排 12 個座位，現安排 2 人就座規定前排中間的 3 個座位不能坐，并且這 2 人不左右相鄰，那么不同排法的種數是346八. 排列組合混合問題先選后排策略例 8. 有 5 個不同的小球 , 裝入 4 個不同的

10、盒內 , 每盒至少裝一個球 , 共有多少不同的裝法 . 解:第一步從 5個球中選出 2個組成復合元共有 C52種方法 .再把 4個元素 （包含一個復合元素）裝入 4 個不同的盒內有 A44種方法，根據分步計數原理裝球的方法共有C52 A 44解決排列組合混合問題 ,先選后排是最基本的指導思想 . 此法與相鄰元素捆綁策略相似嗎練習題：一個班有 6 名戰士 , 其中正副班長各 1 人現從中選 4 人完成四種不同的任務 , 每人完 成一種任務 , 且正副班長有且只有 1 人參加 , 則不同的選法有 192 種九. 小集團問題先整體后局部策略例 9. 用 1,2,3,4,5 組成沒有重復數字的五位數其

11、中恰有兩個偶數夾 1, 在兩個奇數之間 , 這樣的五位數有多少個2解：把 , , 當作一個小集團與排隊共有A 22種排法，再排小集團內部共有2 2 2 2 2A 22 A 22種排法，由分步計數原理共有 A22A22A22種排法 .小集團排列問題中，先整體后局部，再結合其它策略進行處理。練習題：.計劃展出 10幅不同的畫 ,其中 1幅水彩畫 ,幅油畫 ,幅國畫 , 排成一行陳列 ,要求同一 品種的必須連在一起，并且水彩畫不在兩端，那么共有陳列方式的種數為A22A55A 442 5 5 2. 5 男生和女生站成一排照像 ,男生相鄰 ,女生也相鄰的排法有 A22A55A55種十. 元素相同問題隔板

12、策略例 10. 有 10 個運動員名額，分給 7 個班，每班至少一個 , 有多少種分配方案解：因為 10 個名額沒有差別，把它們排成一排。相鄰名額之間形成個空隙。 在個空檔中選個位置插個隔板，可把名額分成份，對應地分給個班級，每一種插板6 方法對應一種分法共有 C96 種分法。二班四班五班六班將 n個相同的元素分成 m份（n，m為正整數） , 每份至少一個元素 ,可以用 m-1塊隔板， 插入 n個元素排成一排的 n-1 個空隙中，所有分法數為 Cnm11練習題：1 10 個相同的球裝 5 個盒中 , 每盒至少一有多少裝法C942 . x y z w 100 求這個方程組的自然數解的組數C130

13、3十一.正難則反總體淘汰策略 例 11.從 0,1,2,3,4,5,6,7,8,9 這十個數字中取出三個數，使 其和為不小于 10 的偶數 , 不同的取法有多少種 解：這問題中如果直接求不小于 10 的偶數很困難 , 可用總體淘汰法。這十個數字中有 5 個偶數 5 個奇數 , 所取的三個數含有 3 個偶數的取法有 C53 , 只含有 1 個偶數的取法有1 2 1 2 3C15C52, 和為偶數的取法共有 C51C52 C53。再淘汰和小于 10的偶數共 9種，符合條件的 取法共有 C51C52 C53 9有些排列組合問題 , 正面直接考慮比較復雜 , 而它的反面往往比較簡捷 , 可以先求練習題

14、：我們班里有 43位同學 ,從中任抽 5 人,正、副班長、團支部書記至少有一人在內的 抽法有多少種十二 .平均分組問題除法策略例 12. 6 本不同的書平均分成 3堆,每堆 2 本共有多少分法解: 分三步取書得 C62C42C22種方法 , 但這里出現重復計數的現象 ,不妨記 6 本書為ABCDEF，若第一步取 AB, 第二步取 CD,第三步取 EF 該分法記為 (AB,CD,EF), 則2 2 2C6C4C2 中還有 (AB,EF,CD),(CD,AB,EF),(CD,EF,AB)(EF,CD,AB),(EF,AB,CD)共 有3 2 2 2 3A 33種取法 , 而這些分法僅是 (AB,C

15、D,EF) 一種分法 ,故共有 C62C42C22/ A33種分法。平均分成的組 ,不管它們的順序如何 ,都是一種情況 ,所以分組后要一定要除以 Ann( n為均分練習題：1 將13個球隊分成 3組,一組 5個隊,其它兩組 4個隊, 有多少分法( C153C84C44 / A22 )名學生分成 3 組, 其中一組 4人, 另兩組 3人但正副班長不能分在同一組 , 有多少種不同的 分組方法 ( 1540)3.某校高二年級共有六個班級， 現從外地轉 入 4名學生，要安排到該年級的兩個班級且每 班安排 2名，則不同的安排方案種數為 (C42C22A26/ A22 90)十三 . 合理分類與分步策略例

16、 13. 在一次演唱會上共 10 名演員 , 其中 8 人能能唱歌 ,5 人會跳舞 , 現要演出一個 2 人唱歌 2 人伴舞的節目 , 有多少選派方法解：10演員中有 5 人只會唱歌， 2人只會跳舞 3 人為全能演員。 選上唱歌人員為標準進 行研究22只會唱的 5 人中沒有人選上唱歌人員共有 C32C32種, 只會唱的 5 人中只有 1 人選上1 1 2 2 2唱歌人員 C51C31C42種,只會唱的 5人中只有 2 人選上唱歌人員有 C52 C52種，由分類計數原理共有C32C11C15C31C22C5 C5 種。解含有約束條件的排列組合問題， 可按元素的性質進行分類， 按事件發生的連續過程

17、分步， 做練習題：1.從 4 名男生和 3 名女生中選出 4人參加某個座 談會，若這 4人中必須既有男生又有女 生，則不同的選法共有 342. 3 成人 2小孩乘船游玩 ,1 號船最多乘 3 人, 2號船最多乘 2 人,3 號船只能乘 1 人,他們任 選 2 只船或 3 只船 ,但小孩不能單獨乘一只船 , 這 3 人共有多少乘船方法 . （27） 本題還有如下分類標準：*以 3個全能演員是否選上唱歌人員為標準*以 3個全能演員是否選上跳舞人員為標準 *以只會跳舞的 2 人是否選上跳舞人員為標準 都可經得到正確結果十四 .構造模型策略例 14. 馬路上有編號為 1,2,3,4,5,6,7,8,9

18、 的九只路燈 , 現要關掉其中的 3 盞 , 但不能關掉 相鄰的 2盞或 3盞,也不能關掉兩端的 2 盞, 求滿足條件的關燈方法有多少種 解：把此問題當作一個排隊模型在 6 盞亮燈的 5 個空隙中插入 3 個不亮的燈有 C53 種一些不易理解的排列組合題如果能轉化為非常熟悉的模型， 如占位填空模型， 排隊模型， 裝盒 練習題：某排共有 10 個座位，若 4 人就坐，每人左右兩邊都有空位，那么不同的坐法有多 少種（ 120）十五 .實際操作窮舉策略例 15. 設有編號 1,2,3,4,5 的五個球和編號 1,2,3,4,5 的五個盒子 , 現將 5 個球投入這五個 盒子內 , 要求每個盒子放一個

19、球，并且恰好有兩個球的編號與盒子的編號相同 , 有多少投 法解：從 5個球中取出 2個與盒子對號有 C52種還剩下 3球 3盒序號不能對應， 利用實際操作法，如果剩下 3,4,5 號球, 3,4,5 號盒 3號球裝 4 號盒時，則 4,5 號球有只有 1 種裝法，同理 3號球裝 5號盒時 ,4,5 號球有也只有 1種裝法 ,由分步計數原理有 2C52號盒3 號盒 4 號盒 5對于條件比較復雜的排列組合問題，不易用公式進行運算，往往利用窮舉法或畫出樹狀圖會收練習題： 1.同一寢室 4 人, 每人寫一張賀年卡集中起來 ,然后每人各拿一張別人的賀年卡， 則四張賀年卡不同的分配方式有多少種 (9)2.

20、 給圖中區域涂色 ,要求相鄰區域不同色 , 現有 4 種可選顏色 , 則不同的著色方法有 72 種14325十六 . 分解與合成策略例 16. 30030 能被多少個不同的偶數整除分析：先把 30030 分解成質因數的乘積形式 30030=2 35 7 1113依題意可知偶因數必先取 2, 再從其余 5 個因數中任取若干個組成乘積，1 23 4 5所有的偶因數為： C51 C52 C53 C54 C55練習 : 正方體的 8 個頂點可連成多少對異面直線解：我們先從 8個頂點中任取 4個頂點構成四體共有體共 C84 12 58, 每個四面體有3 對異面直線 , 正方體中的 8 個頂點可連成 3

21、58 174 對異面直線 分解與合成策略是排列組合問題的一種最基本的解題策略, 把一個復雜問題分解成幾個小問題逐一解決 ,然后依據問題分解后的結構 , 用分類計數原理和分步計數原理將問題合成 , 從而得到 十七 .化歸策略 例 17. 25 人排成 55方陣, 現從中選 3人,要求 3人不在同一行也不在同一列 , 不同的選法 有多少種解：將這個問題退化成 9人排成 33方陣, 現從中選 3人,要求 3人不在同一行也不在同一列 ,有多少選法 . 這樣每行必有 1人從其中的一行中選取 1人后, 把這人所在的行列都劃掉， 如此繼續下去 . 從 33 方隊中選 3 人的 方法有 C31C21C11種。再從 55 方陣選出 33方陣便可 解決問題 . 從 55 方隊中選取 3 行 3 列有 C53C53 選法所以從 5 5 方陣選不在同一行也不在同一列的3 人有C53C53C31C21C11選法。處理復雜的排列組合問題時可以把一個問題退化成一個簡要的問題， 通過解決這個簡要的問題的解決找到解題方法，練習題:某城市的街區由 12個全等的矩形區組成其中實線表示馬路， 從 A走到 B的最短路徑 有多少種 ( C73 35 )十八 .數字排序問題查字典策略例 18由 0，1，2，3，4