排列組合典型題常見解法.ppt

解排列組合的常用策略 從n個不同元素中 任取m個元素 按照一定的順序排成一列 叫做從n個不同元素中取出m個元素的一個排列 2 組合的定義 從n個不同元素中 任取m個元素 并成一組 叫做從n個不同元素中取出m個元素的一個組合 3 排列數公式 4 組合數公式 1 排列的定義 排列與組合的區(qū)別與聯系 與順序有關的為排列問題 與順序無關的為組合問題 一 定序問題倍縮法 空位插入法 例4 7人排隊 其中甲乙丙3人順序一定共有多少種不同的排法 解 空位法 設想有7把椅子讓除甲乙丙以外的四人就坐共有種方法 其余的三個位置甲乙丙共有種坐法 則共有種方法 1 思考 可以先讓甲乙丙就坐嗎 插入法 先排甲乙丙三個人 共有1種排法 再把其余4四人依次插入共有方法 4 5 6 7 練習題 期中安排考試科目9門 語文要在數學之前考 有多少種不同的安排順序 倍縮法 對于某幾個元素順序一定的排列問題 可先把這幾個元素與其他元素一起進行排列 然后用總排列數除以這幾個元素之間的全排列數 則共有不同排法種數是 定序問題可以用倍縮法 還可轉化為占位插入模型處理 二 重排問題求冪法 例5 把6名實習生分配到7個車間實習 共有多少種不同的分法 解 完成此事共分六步 把第一名實習生分配到車間有種分法 7 一般地n不同的元素沒有限制地安排在m個位置上的排列數為種 某8層大樓一樓電梯上來8名乘客 他們到各自的一層下電梯 下電梯的方法 練習題 三 排列組合混合問題先選后排法 例6 有5個不同的小球 裝入4個不同的盒內 每盒至少裝一個球 共有多少不同的裝法 解 第一步從5個球中任選2個捆綁一塊共有 種方法 再與其他三個球看成四個元素裝入4個不同的盒內有 種方法 根據分步計數原理裝球的方法共有 解決排列組合混合問題 先選后排是最基本的指導思想 練習題 一個班有6名戰(zhàn)士 其中正副班長各1人現從中選4人完成四種不同的任務 每人完成一種任務 且正副班長有且只有1人參加 則不同的選法有 種 192 四 相同元素隔板法 例7 有10個運動員名額 分給7個班 每班至少一個 有多少種分配方案 解 因為10個名額沒有差別 把它們排成一排 相鄰名額之間形成 個空隙 在 個空檔中選 個位置插隔板 可把名額分成 份 對應地分給 個班級 每一種插板方法對應一種分法共有 種分法 將n個相同的元素分成m份 n m為正整數 每份至少一個元素 可以用塊隔板 插入n個元素排成一排的個空隙中 所有分法數為 m 1 n 1 練習題 10個相同的球裝5個盒中 每盒至少一個 有多少裝法 五 均分問題除法策略 例8 6本不同的書平均分成3堆 每堆2本共有多少分法 解 分三步取書得種方法 但這里出現重復計數的現象 不妨記6本書為ABCDEF若第一步取AB 第二步取CD 第三步取EF該分法記為 AB CD EF 則中還有 AB EF CD CD AB EF CD EF AB EF CD AB EF AB CD 共有種取法 而這些分法僅是 AB CD EF 一種分法 故共有種分法 平均分成的組 不管它們的順序如何 都是一種情況 所以分組后要一定要除以 n為均分的組數 避免重復計數 1 將13個球隊分成3組 一組5個隊 其它兩組4個隊 有多少分法 2 某校高二年級共有六個班級 現從外地轉入4名學生 要安排到該年級的兩個班級且每班安排2名 則不同的安排方案種數為 練習題 六 多面手問題合理分類法 例9 在一次演唱會上共10名演員 其中8人能夠唱歌 5人會跳舞 現要演出一個2人唱歌2人伴舞的節(jié)目 有多少選派方法 解 10演員中有5人只會唱歌 2人只會跳舞3人為全能演員 本題還有如下分類標準 以3個全能演員是否選上唱歌人員為標準 以3個全能演員是否選上跳舞人員為標準 以只會跳舞的2人是否選上跳舞人員為標準都可經得到正確結果 從4名男生和3名女生中選出4人參加某個座談會 若這4人中必須既有男生又有女生 則不同的選法共有 34 練習題 七 構造模型法 例10 馬路上有編號為1 2 3 4 5 6 7 8 9的九只路燈 現要關掉其中的3盞 但不能關掉相鄰的2盞或3盞 也不能關掉兩端的2盞 求滿足條件的關燈方法有多少種 解 把此問題當作一個排隊模型在6盞亮燈的5個空隙中插入3個不亮的燈有 種 一些不易理解的排列組合題如果能轉化為非常熟悉的模型 如占位填空模型 排隊模型 裝盒模型等 可使問題直觀解決 練習題 某排共有10個座位 若4人就坐 每人左右兩邊都有空位 那么不同的坐法有多少種 120 八 實際操作窮舉法 例15 設有編號1 2 3 4 5的五個球和編號1 23 4 5的五個盒子 現將5個球投入這五個盒子內 要求每個盒子放一個球 并且恰好有兩個球的編號與盒子的編號相同 有多少投法 解 從5個球中取出2個與盒子對號有 種還剩下3球3盒序號不能對應 八 實際操作窮舉法 例15 設有編號1 2 3 4 5的五個球和編號1 23 4 5的五個盒子 現將5個球投入這五個盒子內 要求每個盒子放一個球 并且恰好有兩個球的編號與盒子的編號相同 有多少投法 解 從5個球中取出2個與盒子對號有 種還剩下3球3盒序號不能對應 同理3號球裝5號盒時 4 5號球有也只有1種裝法 由分步計數原理有2種 對于條件比較復雜的排列組合問題 不易用公式進行運算 往往利用窮舉法或畫出樹狀圖會收到意想不到的結果 練習題 同一寢室4人 每人寫一張賀年卡集中起來 然后每人各拿