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

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