排列組合問題17種方法.ppt

解排列組合問題的十七種常用策略 完成一件事 有n類辦法 在第1類辦法中有m1種不同的方法 在第2類辦法中有m2種不同的方法 在第n類辦法中有mn種不同的方法 那么完成這件事共有 種不同的方法 復(fù)習(xí)鞏固 1 分類計數(shù)原理 加法原理 完成一件事 需要分成n個步驟 做第1步有m1種不同的方法 做第2步有m2種不同的方法 做第n步有mn種不同的方法 那么完成這件事共有 種不同的方法 2 分步計數(shù)原理 乘法原理 分步計數(shù)原理各步相互依存 每步中的方法完成事件的一個階段 不能完成整個事件 3 分類計數(shù)原理分步計數(shù)原理區(qū)別 分類計數(shù)原理方法相互獨立 任何一種方法都可以獨立地完成這件事 解決排列組合綜合性問題的一般過程如下 1 認真審題弄清要做什么事 2 怎樣做才能完成所要做的事 即采取分步還是分類 或是分步與分類同時進行 確定分多少步及多少類 3 確定每一步或每一類是排列問題 有序 還是組合 無序 問題 元素總數(shù)是多少及取出多少個元素 解決排列組合綜合性問題 往往類與步交叉 因此必須掌握一些常用的解題策略 從n個不同元素中 任取m個元素 并成一組 叫做從n個不同元素中取出m個元素的一個組合 從n個不同元素中 任取m個元素 按照一定的順序排成一列 叫做從n個不同元素中取出m個元素的一個排列 1 排列的定義 2 組合的定義 3 排列數(shù)公式 4 組合數(shù)公式 排列與組合的關(guān)鍵是問題與次序有無關(guān)系 5加法原理和乘法原理 完成任務(wù)時是分類進行還是步進行 一 特殊元素和特殊位置優(yōu)先策略 例1 由0 1 2 3 4 5可以組成多少個沒有重復(fù)數(shù)字五位奇數(shù) 解 由于末位和首位有特殊要求 應(yīng)該優(yōu)先安排 以免不合要求的元素占了這兩個位置 先排末位共有 然后排首位共有 最后排其它位置共有 位置分析法和元素分析法是解決排列組合問題最常用也是最基本的方法 若以元素分析為主 需先安排特殊元素 再處理其它元素 若以位置分析為主 需先滿足特殊位置的要求 再處理其它位置 若有多個約束條件 往往是考慮一個約束條件的同時還要兼顧其它條件 7種不同的花種在排成一列的花盆里 若兩種葵花不種在中間 也不種在兩端的花盆里 問有多少不同的種法 練習(xí)題 解一 分兩步完成 第一步選兩葵花之外的花占據(jù)兩端和中間的位置 第二步排其余的位置 解二 第一步由葵花去占位 第二步由其余元素占位 小結(jié) 當排列或組合問題中 若某些元素或某些位置有特殊要求的時候 那么 一般先按排這些特殊元素或位置 然后再按排其它元素或位置 這種方法叫特殊元素 位置 分析法 二 相鄰元素捆綁策略 例2 7人站成一排 其中甲乙相鄰且丙丁相鄰 共有多少種不同的排法 解 可先將甲乙兩元素捆綁成整體并看成一個復(fù)合元素 同時丙丁也看成一個復(fù)合元素 再與其它元素進行排列 同時對相鄰元素內(nèi)部進行自排 要求某幾個元素必須排在一起的問題 可以用捆綁法來解決問題 即將需要相鄰的元素合并為一個元素 再與其它元素一起作排列 同時要注意合并元素內(nèi)部也必須排列 某人射擊8槍 命中4槍 4槍命中恰好有3槍連在一起的情形的不同種數(shù)為 練習(xí)題 20 三 不相鄰問題插空策略 例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ù)除以這幾個元素之間的全排列數(shù) 則共有不同排法種數(shù)是 空位法 設(shè)想有7把椅子讓除甲乙丙以外的四人就坐共有種方法 其余的三個位置甲乙丙共有種坐法 則共有種方法 1 思考 可以先讓甲乙丙就坐嗎 插入法 先排甲乙丙三個人 共有1種排法 再把其余4四人依次插入共有方法 4 5 6 7 定序問題可以用倍縮法 還可轉(zhuǎn)化為占位插空模型處理 練習(xí)題 10人身高各不相等 排成前后排 每排5人 要求從左至右身高逐漸增加 共有多少排法 五 重排問題求冪策略 例5 把6名實習(xí)生分配到7個車間實習(xí) 共有多少種不同的分法 解 完成此事共分六步 把第一名實習(xí)生分配到車間有種分法 7 把第二名實習(xí)生分配 到車間也有7種分法 1 某班新年聯(lián)歡會原定的5個節(jié)目已排成節(jié)目單 開演前又增加了兩個新節(jié)目 如果將這兩個節(jié)目插入原節(jié)目單中 那么不同插法的種數(shù)為 42 2 某8層大樓一樓電梯上來8名乘客人 他們到各自的一層下電梯 下電梯的方法 練習(xí)題 七 多排問題直排策略 例7 8人排成前后兩排 每排4人 其中甲乙在前排 丁在后排 共有多少排法 解 8人排前后兩排 相當于8人坐8把椅子 可以把椅子排成一排 一般地 元素分成多排的排列問題 可歸結(jié)為一排考慮 再分段研究 有兩排座位 前排11個座位 后排12個座位 現(xiàn)安排2人就座規(guī)定前排中間的3個座位不能坐 并且這2人不左右相鄰 那么不同排法的種數(shù)是 346 練習(xí)題 甲乙都在前排 1 都在左面4個座位 6種2 都在右面4個座位同上 6種3 分列在中間3個的左右 32種一共6 6 32 44種甲乙都在后排 A 22 10 9 8 7 6 5 4 3 2 1 110種甲乙分列在前后兩排A 22 12 8 192種一共44 110 192 346種 八 排列組合混合問題先選后排策略 例8 有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 九 小集團問題先整體局部策略 例9 用1 2 3 4 5組成沒有重復(fù)數(shù)字的五位數(shù)其中恰有兩個偶數(shù)夾1 這兩個奇數(shù)之間 這樣的五位數(shù)有多少個 解 把 當作一個小集團與 排隊共有 種排法 再排小集團內(nèi)部共有 種排法 由分步計數(shù)原理共有 種排法 小集團排列問題中 先整體后局部 再結(jié)合其它策略進行處理 計劃展出10幅不同的畫 其中1幅水彩畫 幅油畫 幅國畫 排成一行陳列 要求同一品種的必須連在一起 并且水彩畫不在兩端 那么共有陳列方式的種數(shù)為 2 5男生和 女生站成一排照像 男生相鄰 女生也相鄰的排法有 種 十 元素相同問題隔板策略 例10 有10個運動員名額 在分給7個班 每班至少一個 有多少種分配方案 解 因為10個名額沒有差別 把它們排成一排 相鄰名額之間形成 個空隙 在 個空檔中選 個位置插個隔板 可把名額分成 份 對應(yīng)地分給 個班級 每一種插板方法對應(yīng)一種分法共有 種分法 將n個相同的元素分成m份 n m為正整數(shù) 每份至少一個元素 可以用m 1塊隔板 插入n個元素排成一排的n 1個空隙中 所有分法數(shù)為 練習(xí)題 10個相同的球裝5個盒中 每盒至少一有多少裝法 2 x y z w 100求這個方程組的自然數(shù)解的組數(shù) 十一 正難則反總體淘汰策略 例11 從0 1 2 3 4 5 6 7 8 9這十個數(shù)字中取出三個數(shù) 使其和為不小于10的偶數(shù) 不同的取法有多少種 解 這問題中如果直接求不小于10的偶數(shù)很困難 可用總體淘汰法 再淘汰和小于10的偶數(shù)共 符合條件的取法共有 9 有些排列組合問題 正面直接考慮比較復(fù)雜 而它的反面往往比較簡捷 可以先求出它的反面 再從整體中淘汰 我們班里有43位同學(xué) 從中任抽5人 正 副班長 團支部書記至少有一人在內(nèi)的抽法有多少種 練習(xí)題 十二 平均分組問題除法策略 例12 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 10名學(xué)生分成3組 其中一組4人 另兩組3人但正副班長不能分在同一組 有多少種不同的分組方法 1540 3 某校高二年級共有六個班級 現(xiàn)從外地轉(zhuǎn)入4名學(xué)生 要安排到該年級的兩個班級且每班安排2名 則不同的安排方案種數(shù)為 十三 合理分類與分步策略 例13 在一次演唱會上共10名演員 其中8人能能唱歌 5人會跳舞 現(xiàn)要演出一個2人唱歌2人伴舞的節(jié)目 有多少選派方法 解 10演員中有5人只會唱歌 2人只會跳舞3人為全能演員 本題還有如下分類標準 以3個全能演員是否選上唱歌人員為標準 以3個全能演員是否選上跳舞人員為標準 以只會跳舞的2人是否選上跳舞人員為標準都可經(jīng)得到正確結(jié)果 解含有約束條件的排列組合問題 可按元素的性質(zhì)進行分類 按事件發(fā)生的連續(xù)過程分步 做到標準明確 分步層次清楚 不重不漏 分類標準一旦確定要貫穿于解題過程的始終 1 從4名男生和3名女生中選出4人參加某個座談會 若這4人中必須既有男生又有女生 則不同的選法共有 34 練習(xí)題 2 3成人2小孩乘船游玩 1號船最多乘3人 2號船最多乘2人 3號船只能乘1人 他們?nèi)芜x2只船或3只船 但小孩不能單獨乘一只船 這3人共有多少乘船方法 27 十四 構(gòu)造模型策略 例14 馬路上有編號為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 十五 實際操作窮舉策略 例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人 每人寫一張賀年卡集中起來 然后每人各拿一張別人的賀年卡 則四張賀年卡不同的分配方式有多少種 9 2 給圖中區(qū)域涂色 要求相鄰區(qū)域不同色 現(xiàn)有4種可選顏色 則不同的著色方法有 種 72 十六 分解與合成策略 例16 30030能被多少個不同的偶數(shù)整除 分析 先把30030分解成質(zhì)因數(shù)的乘積形式30030 2 3 5 7 11 13依題意可知偶因數(shù)必先取2 再從其余5個因數(shù)中任取若干個組成乘積 所有的偶因數(shù)為 例17 正方體的8個頂點可連成多少對異面直線 解 我們先從8個頂點中任取4個頂點構(gòu)成四體共有體共 6 6 58 174 分解與合成策略是排列組合問題的一種最基本的解題策略 把一個復(fù)雜問題分解成幾個小問題逐一解決 然后依據(jù)問題分解后的結(jié)構(gòu) 用分類計數(shù)原理和分步計數(shù)原理將問題合成 從而得到問題的答案 每個比較復(fù)雜的問題都要用到這種解題策略 十七 化歸策略 例18 25人排成5 5方隊 現(xiàn)從中選3人 要求3人不在同一行也不在同一列 不同的選法有多少種 解 將這個問題退化成9人排成3 3方隊 現(xiàn)從中選3人 要求3人不在同一行也不在同一列 有多少選法 這樣每行必有1人從其中的一行中選取1人后 把這人所在的行列都劃掉 從5 5方隊中選取3行3列有 選法所以從5 5方隊選不在同一行也不在同一列的3人有 選法 處理復(fù)雜的排列組合問題時可以把一個問題退化成一個簡要的問題 通過解決這個簡要的問題的解決找到解題方法 從而進下一步解決原來的問題 如此繼續(xù)下去 從3 3方隊中選3人