《排列組合的策略》PPT課件.ppt

解排列組合的策略 從n個不同元素中 任取m個元素 按照一定的順序排成一列 叫做從n個不同元素中取出m個元素的一個排列 2 組合的定義 從n個不同元素中 任取m個元素 并成一組 叫做從n個不同元素中取出m個元素的一個組合 3 排列數(shù)公式 4 組合數(shù)公式 1 排列的定義 排列與組合的區(qū)別與聯(lián)系 與順序有關(guān)的為排列問題 與順序無關(guān)的為組合問題 一 特殊元素和特殊位置優(yōu)先法 例1 由0 1 2 3 4 5可以組成多少個沒有重復(fù)數(shù)字五位奇數(shù) 解 由于末位和首位有特殊要求 應(yīng)該優(yōu)先安排 以免不合要求的元素占了這兩個位置 先排末位共有 然后排首位共有 最后排其它位置共有 位置分析法和元素分析法是解決排列組合問題最常用也是最基本的方法 7種不同的花種在排成一列的花盆里 若兩種葵花不種在中間 也不種在兩端的花盆里 問有多少不同的種法 練習(xí)題 二 相鄰元素捆綁法 例2 7人站成一排 其中甲乙相鄰且丙丁相鄰 共有多少種不同的排法 解 要求某幾個元素必須排在一起的問題 可以用捆綁法來解決問題 練習(xí)題 5個男生3個女生排成一排 3個女生要排在一起 有多少種不同的排法 共有 4320種不同的排法 三 不相鄰問題插空法 例3 一個晚會的節(jié)目有4個舞蹈 2個相聲 3個獨唱 舞蹈節(jié)目不能連續(xù)出場 則節(jié)目的出場順序有多少種 解 分兩步進行第一步排2個相聲和3個獨唱共有種 元素不相鄰問題可先把沒有位置要求的元素進行排隊再把不相鄰元素插入中間和兩端 某班新年聯(lián)歡會原定的5個節(jié)目已排成節(jié)目單 開演前又增加了兩個新節(jié)目 如果將這兩個新節(jié)目插入原節(jié)目單中 且兩個新節(jié)目不相鄰 那么不同插法的種數(shù)為 30 練習(xí)題 四 定序問題倍縮空位插入法 例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個組成復(fù)合元共有 種方法 再把5個元素 包含一個復(fù)合元素 裝入4個不同的盒內(nèi)有 種方法 根據(jù)分步計數(shù)原理裝球的方法共有 解決排列組合混合問題 先選后排是最基本的指導(dǎo)思想 練習(xí)題 一個班有6名戰(zhàn)士 其中正副班長各1人現(xiàn)從中選4人完成四種不同的任務(wù) 每人完成一種任務(wù) 且正副班長有且只有1人參加 則不同的選法有 種 192 七 元素相同問題隔板法 例7 1 有10個運動員名額 分給7個班 每班至少一個 有多少種分配方案 解 因為10個名額沒有差別 把它們排成一排 相鄰名額之間形成 個空隙 在 個空檔中選 個位置插個隔板 可把名額分成 份 對應(yīng)地分給 個班級 每一種插板方法對應(yīng)一種分法共有 種分法 將n個相同的元素分成m份 n m為正整數(shù) 每份至少一個元素 可以用塊隔板 插入n個元素排成一排的個空隙中 所有分法數(shù)為 m 1 n 1 例7 2 有10個運動員名額 分給7個班 有些班級可以把名額讓給其它班 有多少種分配方案 例7 2 有10個運動員名額 分給7個班 有些班級可以把名額讓給其它班 有多少種分配方案 將n個相同的元素分成m份 n m為正整數(shù) 每份可以沒有元素 可以用塊隔板 插入n個元素和m 1塊板共n m 1個位置中 所有分法數(shù)為 m 1 練習(xí)題 1 10個相同的球裝在5個盒中 每盒至少一個 有多少種裝法 2 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é)果 解含有約束條件的排列組合問題 可按元素的性質(zhì)進行分類 按事件發(fā)生的連續(xù)過程分步 做到標準明確 分步層次清楚 不重不漏 分類標準一旦確定要貫穿于解題過程的始終 從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)燈方法有多少種 解 把此問題當作一個排隊模型在6盞亮燈的5個空隙中插入3個不亮的燈有 種 一些不易理解的排列組合題如果能轉(zhuǎn)化為非常熟悉的模型 如占位填空模型 排隊模型 裝盒模型等 可使問題直觀解決 練習(xí)題 某排共有10個座位 若4人就坐 每人左右兩邊都有空位 那么不同的坐法有多少種 120 十一 實際操作窮舉法 例11 設(shè)有編號1 2 3 4 5的五個球和編號1 23 4 5的五個盒子 現(xiàn)將5個球投入這五個盒子內(nèi) 要求每個盒子放一個球 并且恰好有兩個球的編號與盒子的編號相同 有多少投法 解 從5個球中取出2個與盒子對號有 種還剩下3球3盒序號不能對應(yīng) 十一 實際操作窮舉策略 例11 設(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人 每人寫一張賀年卡集中起來 然后每人各拿一張別人的賀年卡 則四張賀年卡不同的分配方式有多少種 9 2 給圖中區(qū)域涂色 要求相鄰區(qū)域不同色 現(xiàn)有4種可選顏色 則不同的著色方法有 種 72 我們班里有43位同學(xué) 從中任抽5人 正 副班長 團支部書記至少有一人在內(nèi)的抽法有多少種 練習(xí)題 1 從4名男生和3名女生中選出4人參加某個座談會 若這4人中必須既有男生又有女生 則不同的選法共有 34 練習(xí)題 2 3成人2小孩乘船游玩 1號船最多乘3人 2號船最多乘2人 3號船只能乘1人 他們?nèi)芜x2只船或3只船 但小孩不能單獨乘一只船 這3人共有多少乘船方法 27 練習(xí) 有12名劃船運動員 其中3人只會劃左舷 4人只會劃右舷 其它5人既會劃左舷 又會劃右舷 現(xiàn)要從這12名運動員中選出6人平均分在左右舷參加劃船比賽 有多少種不同的選法 練習(xí) 將5名實習(xí)教師分配到高一年級的 個班實習(xí) 每班至少 名 最多 名 則不同的分配方案有 A