排列組合綜合應用.ppt

10 3 3排列組合綜合應用 完成一件事 有n類辦法 在第1類辦法中有m1種不同的方法 在第2類辦法中有m2種不同的方法 在第n類辦法中有mn種不同的方法 那么完成這件事共有 種不同的方法 復習鞏固 1 分類計數(shù)原理 加法原理 完成一件事 需要分成n個步驟 做第1步有m1種不同的方法 做第2步有m2種不同的方法 做第n步有mn種不同的方法 那么完成這件事共有 種不同的方法 2 分步計數(shù)原理 乘法原理 分步計數(shù)原理各步相互依存 每步中的方法完成事件的一個階段 不能完成整個事件 3 分類計數(shù)原理分步計數(shù)原理區(qū)別 分類計數(shù)原理方法相互獨立 任何一種方法都可以獨立地完成這件事 排列問題常用方法 直接法和間接法 1 優(yōu)限法 特殊元素 位置 2 捆綁法 相鄰排列問題3 插空法 不相鄰排列問題4 消序法 解決排列組合綜合性問題的一般過程如下 1 認真審題弄清要做什么事 2 怎樣做才能完成所要做的事 即采取分步還是分類 或是分步與分類同時進行 確定分多少步及多少類 3 確定每一步或每一類是排列問題 有序 還是組合 無序 問題 元素總數(shù)是多少及取出多少個元素 解決排列組合綜合性問題 往往類與步交叉 因此必須掌握一些常用的解題策略 1 排列組合混合問題先選后排策略 例1 有5個不同的小球 裝入4個不同的盒內 每盒至少裝一個球 共有多少不同的裝法 解 第一步從5個球中選出2個組成復合元共有 種方法 再把5個元素 包含一個復合元素 裝入4個不同的盒內有 種方法 根據(jù)分步計數(shù)原理裝球的方法共有 解決排列組合混合問題 先選后排是最基本的指導思想 此法與相鄰元素捆綁策略相似嗎 練習題1 一個班有6名戰(zhàn)士 其中正副班長各1人現(xiàn)從中選4人完成四種不同的任務 每人完成一種任務 且正副班長有且只有1人參加 則不同的選法有 種 192 2 分組 分配問題策略 平均分成的組 不管它們的順序如何 都是一種情況 所以分組后要一定要除以 n為均分的組數(shù) 避免重復計數(shù) 例2 6本不同的書 按下列要求處理 分別有多少種分法 1 分三堆 一堆1本 一堆2本 一堆3本 2 分給甲 乙 丙3個人 甲1本 乙2本 丙3本 3 分給甲 乙 丙3個人 一人1本 一人2本 一人3本 4 分三堆 有兩堆各1本 另一堆4本 5 平均分成三組 6 平均分給甲 乙 丙3個人 1將13個球隊分成3組 一組5個隊 其它兩組4個隊 有多少分法 3 10名學生分成3組 其中一組4人 另兩組3人但正副班長不能分在同一組 有多少種不同的分組方法 1540 2 某校高二年級共有六個班級 現(xiàn)從外地轉入4名學生 要安排到該年級的兩個班級且每班安排2名 則不同的安排方案種數(shù)為 練習2 3 特殊元素和特殊位置優(yōu)先策略 例1 由0 1 2 3 4 5可以組成多少個沒有重復數(shù)字五位奇數(shù) 解 由于末位和首位有特殊要求 應該優(yōu)先安排 以免不合要求的元素占了這兩個位置 先排末位共有 然后排首位共有 最后排其它位置共有 位置分析法和元素分析法是解決排列組合問題最常用也是最基本的方法 若以元素分析為主 需先安排特殊元素 再處理其它元素 若以位置分析為主 需先滿足特殊位置的要求 再處理其它位置 若有多個約束條件 往往是考慮一個約束條件的同時還要兼顧其它條件 7種不同的花種在排成一列的花盆里 若兩種葵花不種在中間 也不種在兩端的花盆里 問有多少不同的種法 練習題 4 元素相同問題隔板策略 例3 有10個運動員名額 在分給7個班 每班至少一個 有多少種分配方案 解 因為10個名額沒有差別 把它們排成一排 相鄰名額之間形成 個空隙 在 個空檔中選 個位置插個隔板 可把名額分成 份 對應地分給 個班級 每一種插板方法對應一種分法共有 種分法 將n個相同的元素分成m份 n m為正整數(shù) 每份至少一個元素 可以用m 1塊隔板 插入n個元素排成一排的n 1個空隙中 所有分法數(shù)為 練習題 10個相同的球裝5個盒中 每盒至少一個 有多少裝法 5 相鄰元素捆綁策略 例2 7人站成一排 其中甲乙相鄰且丙丁相鄰 共有多少種不同的排法 解 可先將甲乙兩元素捆綁成整體并看成一個復合元素 同時丙丁也看成一個復合元素 再與其它元素進行排列 同時對相鄰元素內部進行自排 要求某幾個元素必須排在一起的問題 可以用捆綁法來解決問題 即將需要相鄰的元素合并為一個元素 再與其它元素一起作排列 同時要注意合并元素內部也必須排列 某人射擊8槍 命中4槍 4槍命中恰好有3槍連在一起的情形的不同種數(shù)為 練習題 20 6 不相鄰問題插空策略 例3 一個晚會的節(jié)目有4個舞蹈 2個相聲 3個獨唱 舞蹈節(jié)目不能連續(xù)出場 則節(jié)目的出場順序有多少種 解 分兩步進行第一步排2個相聲和3個獨唱共有種 元素相離問題可先把沒有位置要求的元素進行排隊再把不相鄰元素插入中間和兩端 某班新年聯(lián)歡會原定的5個節(jié)目已排成節(jié)目單 開演前又增加了兩個新節(jié)目 如果將這兩個新節(jié)目插入原節(jié)目單中 且兩個新節(jié)目不相鄰 那么不同插法的種數(shù)為 30 練習題 7 合理分類與分步策略 例4 在一次演唱會上共10名演員 其中8人能唱歌 5人會跳舞 現(xiàn)要演出一個2人唱歌2人伴舞的節(jié)目 有多少選派方法 解 10演員中有5人只會唱歌 2人只會跳舞3人為全能演員 本題還有如下分類標準 以3個全能演員是否選上唱歌人員為標準 以3個全能演員是否選上跳舞人員為標準 以只會跳舞的2人是否選上跳舞人員為標準都可經(jīng)得到正確結果 解含有約束條件的排列組合問題 可按元素的性質進行分類 按事件發(fā)生的連續(xù)過程分步 做到標準明確 分步層次清楚 不重不漏 分類標準一旦確定要貫穿于解題過程的始終 1 從4名男生和3名女生中選出4人參加某個座談會 若這4人中必須既有男生又有女生 則不同的選法共有 34 練習題 2 3成人2小孩乘船游玩 1號船最多乘3人 2號船最多乘2人 3號船只能乘1人 他們任選2只船或3只船 但小孩不能單獨乘一只船 這3人共有多少乘船方法 27 8 重排問題求冪策略 例5 把6名實習生分配到7個車間實習 共有多少種不同的分法 解 完成此事共分六步 把第一名實習生分配到車間有種分法 7 1 某班新年聯(lián)歡會原定的5個節(jié)目已排成節(jié)目單 開演前又增加了兩個新節(jié)目 如果將這兩個節(jié)目插入原節(jié)目單中 那么不同插法的種數(shù)為 42 2 某8層大樓一樓電梯上來8名乘客人 他們到各自的一層下電梯 下電梯的方法 練習題 練習題 6顆顏色不同的鉆石 可穿成幾種鉆石圈 120 9 構造模型策略 例5 馬路上有編號為1 2 3 4 5 6 7 8 9的九只路燈 現(xiàn)要關掉其中的3盞 但不能關掉相鄰的2盞或3盞 也不能關掉兩端的2盞 求滿足條件的關燈方法有多少種 解 把此問題當作一個排隊模型在6盞亮燈的5個空隙中插入3個不亮的燈有 種 一些不易理解的排列組合題如果能轉化為非常熟悉的模型 如占位填空模型 排隊模型 裝盒模型等 可使問題直觀解決 練習題 某排共有10個座位 若4人就坐 每人左右兩邊都有空位 那么不同的坐法有多少種 120 10 實際操作窮舉策略 例6 設有編號1 2 3 4 5的五個球和編號1 23 4 5的五個盒子 現(xiàn)將5個球投入這五個盒子內 要求每個盒子放一個球 并且恰好有兩個球的編號與盒子的編號相同 有多少投法 解 從5個球中取出2個與盒子對號有 種還剩下3球3盒序號不能對應 10 實際操作窮舉策略 例6 設有編號1 2 3 4 5的五個球和編號1 23 4 5的五個盒子 現(xiàn)將5個球投入這五個盒子內 要求每個盒子放一個球 并且恰好有兩個球的編號與盒子的編號相同 有多少投法 解 從5個球中取出2個與盒子對號有 種還剩下3球3盒序號不能對應 同理3號球裝5號盒時 4 5號球有也只有1種裝法 由分步計數(shù)原理有2種 對于條件比較復雜的排列