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

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