解排列組合問題的常見策略

《解排列組合問題的常見策略》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、解排列組合問題的常見策略湖北省淆水縣第一中學(xué)田勝慧、程選志、皮本炎【內(nèi)容摘要】計(jì)數(shù)問題中排列組合問題是最常見的，其解法往往是構(gòu)造性的，方法靈活多樣，因而不同解法就決定了解決問題的難易，而且解題過程出現(xiàn)“重復(fù)”和“遺漏”的錯(cuò)誤很難發(fā)現(xiàn)。因而掌握一些解這類問題的常見策略是十分必要的?！娟P(guān)鍵詞】排列組合策略1、特殊元素和特殊位置優(yōu)先策略位置分析法和元素分析法是解決排列組合問題最常用也是最基本的方法，若以元素分析為主，需先安排特殊元素，再處理其它元素?若以位置分析為主，需先滿足特殊位置的要求，再處理其它位置。若有多個(gè)約束條件，往往是考慮一個(gè)約束條件的同時(shí)還要兼顧其它條件?！纠坑?到9這10個(gè)數(shù)字

2、，可以組成多少個(gè)沒有重復(fù)數(shù)字的三位偶數(shù)?！窘馕觥靠紤]“0”是特殊元素，如果三位數(shù)中含0,則它不能排在首位，因此，符合條件的三位數(shù)分為2類：第一類，0排在末位時(shí)，前兩位數(shù)字從數(shù)字1—9中選，符合題意的三位偶數(shù)有A；=72個(gè)。第二類，0不排在末位時(shí)，末位數(shù)字從2,4,6,8四個(gè)數(shù)字中選，首位數(shù)字從除0和末位數(shù)字的8個(gè)數(shù)字中選，中間位置的數(shù)字從除首位和末位的8個(gè)數(shù)字中選，符合題意的三位偶數(shù)有￡W=256個(gè)。由分類計(jì)數(shù)原理可得，沒有重復(fù)數(shù)字的三位偶數(shù)共有72+256=328個(gè)。2、相鄰元素捆綁策略要求某幾個(gè)元素必須排在一起的問題，可以用捆綁法來解決問題.即將需要相鄰的元素合并為一個(gè)元素，再與其它元

3、素一起作排列，同時(shí)要注意合并元素內(nèi)部也必須排列?！纠考?、乙等6人要求甲、乙兩人相鄰站成一排，有多少種不同的站法。【解析】分2部完成：第一步：先讓甲、乙兩人站隊(duì)，有盃種站法;第二步：將甲、乙看作一個(gè)整體，作為一個(gè)元素與另外4人站隊(duì)，有攜種站法。由分步計(jì)數(shù)原理，共有AlAl=240種不同站法。3、不相鄰問題插空策略元素相離問題可先把沒有位置要求的元素進(jìn)行排隊(duì)再把不相鄰元素插入中間和兩端?！纠?名學(xué)生和2位老師站成一排合影，要求2位老師不相鄰的排法有多少種?！窘馕觥肯扰?名學(xué)生，有心種排法，8名學(xué)生間共有9個(gè)空隙（加上邊上空隙），然后把老師排在9個(gè)空隙中，有福種排法，所以共有A爲(wèi)種排法。4、

4、定序問題空位插入策略定序問題可轉(zhuǎn)化為占位插空模型處理【例】7人排隊(duì)，其中甲乙丙3人順序一定共有多少不同的排法？【解析】設(shè)想有7把椅子讓除甲乙丙以外的四人就坐共有劃種方法,其余的三個(gè)位置甲乙丙共有1種坐法，則共有種方法。5、重排問題求磊策略允許重復(fù)的排列問題的特點(diǎn)是以元素為研究對(duì)象，元素不受位置的約束，可以逐一安排各個(gè)元素的位置，一般地〃不同的元素沒有限制地安排在加個(gè)位置上的排列數(shù)為加"種?！纠堪?名實(shí)習(xí)生分配到7個(gè)車間實(shí)習(xí)，共有多少種不同的分法？【解析】完成此事共分六步:把第一名實(shí)習(xí)生分配到車間有7種分法.到車間也有7種分法，依此類推，由分步計(jì)數(shù)原理共有腫種不同的排法。6、環(huán)排問題線排策

5、略一般地,n個(gè)不同元素作圓形排列，共有(n-1)!種排法?如果從n個(gè)不同元素中取出m個(gè)元素作圓形排列共有丄船。m【例】5人圍桌而坐，共有多少種坐法？【解析】圍桌而坐與坐成一排的不同點(diǎn)在于，坐成圓形沒有首尾之分,所以固定一人A并從此位置把圓形展成直線其余4人共有況種排法即(5—1)!7、多排問題直排策略一般地，元素分成多排的排列問題，可歸結(jié)為一排考慮，再分段研究。【例】8人排成前后兩排，每排4人，其中甲乙在前排，丁在后排，共有多少排法？【解析】8人排前后兩排，相當(dāng)于8人坐8把椅子，可以把椅子排成一排。先在前4個(gè)位置排甲乙兩個(gè)特殊元素有碼種，再排后4個(gè)位置上的特殊元素有種,其余的5人在5個(gè)位置

6、上任意排列有&種，則共有A~AA^種。8、排列組合混合問題先選后排策略解決排列組合混合問題，先選后排是最基本的指導(dǎo)思想.【例】有5個(gè)不同的小球，裝入4個(gè)不同的盒內(nèi)，每盒至少裝一個(gè)球,共有多少不同的裝法.【解析】第一步從5個(gè)球中選出2個(gè)組成復(fù)合元共有C；種方法?再把5個(gè)元素（包含一個(gè)復(fù)合元素）裝入4個(gè)不同的盒內(nèi)有尤種方法，根據(jù)分步計(jì)數(shù)原理裝球的方法共有9、相同元素問題隔板策略將n個(gè)相同的元素分成m份（mm為正整數(shù)），每份至少一個(gè)元素,可以用m-1塊隔板，插入n個(gè)元素排成一排的n-1個(gè)空隙中，所有分法數(shù)為C：：/O【例】某校準(zhǔn)備組建一個(gè)10人的籃球隊(duì)，這10人由高一6個(gè)班學(xué)生組成，每班至少1

7、人，則名額分配方案有多少種?！窘馕觥繉?0人看成10個(gè)元素，共有9個(gè)空，選5個(gè)空插入隔板，分成6部分，即為6個(gè)班各班選出的學(xué)生人數(shù)，共有C；種。10、正難則反總體淘汰策略有些排列組合問題，正面直接考慮比較復(fù)雜，而它的反面往往比較簡潔,可以先求出它的反面，再從整體中淘汰?！纠磕嘲嗉?jí)要從4名男生2名女生中選派4人參加某次社區(qū)服務(wù)，如果要求至少有1名女生有多少種不同的選派方案。【解析】6人中選派4人的組合數(shù)為C爲(wèi)其中都選男生