排列組合問題17種策略.

1、rST*r *復習鞏固1 分類計數(shù)原理（加法原理） 完成一件事，有n類辦法，在第1類辦法中有 m】種不同的方法，在第2類辦法中有m2種不 同的方法，在第n類辦法中有叫種不同的 方法，那么完成這件事共有： 種不同的方法. N二叫切2+ni 口2分步計數(shù)原理（兼法原理） 完成一件事，需要分成n個步驟，做第1步有 眄種不同的方法，做第2步有叫種不同的方 法做第n步有叫種不同的方法，那么完 成這件事共有：二叫嗎叫種不同的方法3分類計數(shù)原理分步計數(shù)原理區(qū)別分類計數(shù)原理方法相互獨立，任何一種方法 都可以獨立地完成這件事。分步計數(shù)原理各步相互依存，每步中的方法 完成事件的一個階段，不能完成整個事件-解決排列

2、組合綜合性問S的一般過程如下：1. 認真審題弄清要做什么事2. 怎樣做才能完成所要做的事，即采取分步還 是分類或是分步與分類同時進行，確定分多少步及多少類。3. 確定每一步或每一類是排列問題（有序）還是 組合（無序）問題，元素總數(shù)是多少及取出多 少個元素.解決排列組合綜合性問題，往往類與步交叉，因此必須掌握一些常用的解題策略1. 推列的定義：從H個不同元素中，任取個元索，按照 定的順序排成列，叫做從n個不同元索中取出個 元索的個排列。2. 組合的定義：從fl個不同元素中，任取ni個元素，并成一組，叫做從n個不同元素中取出m個尤素的一 個組合推列與組合的關鍵他礦題與次序仔無關系。A = Z7（n

3、 1）（” 一 2）（”一力 + 1）3. 列數(shù)公式：(zi m )!-林/Z(Z7 1)(/7 2)-*-(z/ 7+1)4組合數(shù)公式：U =穴=Cfnm !(n m)!5加法廉理和乘法原理：完成任務時是分類進行還足步進行。一.特殊元素和特殊位優(yōu)先策*例1 由（M234,5可以組成多少個沒有重復數(shù)字 五位奇數(shù)_鮮:由于末位和首位有特殊要求，應該優(yōu)先安 IM_ _L_ f一 L 1位分析法和元素分析法罷解決排列組合問 MW用也是基本的方法若以元*分析為 主 11先安排特殊元*轉處理其它元若以 位分析為主 1先満足特殊位的要求再 如理其它位-若有多個約東條件往往是 考盤一個釣東條件的同時還要集願

4、其它條件練習題1. 7種不同的花種在排成一列的花盆里，若兩 種葵花不種在中間，也不種在兩端的花盆 里，問有多少不同的種法？解一：分兩步完成：第一步選兩英花之外的花占據(jù)兩端和中間的位置竹X：利喟乍V上 第二步排其余的位置：冇A：種排法.共冇種不同的排法 解二：第一步由葵花去占位:右X：利扌申法第二步由其余元素占位: 右左種排法共tmx 種不同的拙法小結：當排列或組合問題中，若某些元素或某些位置有特殊要 求的時候，那么，一般先按排這些特殊元素或位置.然后再 按排其它元素或位置.這種方法叫特殊元素（位S）分析法。二相鄰元素捆綁策略例27人站成一排，其中甲乙相鄰且丙丁相 鄰-共有多少種不同的排法WFi

5、:可先將甲乙兩元素捆綁成整體并看成 一個復合元素，同時丙丁也看成一個 復合元孟再與其它元素進行排列， *宴求第幾個元縈必須祥在一起的問題,可以用 糰綁法來詔決問題.即將需寥相鄰前元素臺井 為一丫元縈，再與其它元累一起作禪列，同時 搜注意白笄元素內部也必須挪列練習題某人射擊8槍，命中4槍，4槍命中恰好 有3槍連在一起的情形的不同種數(shù)為(2()三不相鄰問插空策略Til例3個晚會的節(jié)目有4個舞蹈 2個相聲,3個 獨唱，舞蹈節(jié)目不能連續(xù)出場，則節(jié)目的出 場順序有多少種？解:分兩步進行第一步排2個相聲和3個獨唱共 有 疋 種，第二步將4舞蹈插入第一步排 好的6個元素中間包含首尾兩個空位共有 種上笙不同的

6、方法由分步計數(shù)原理,節(jié)目的 不同順序共有也種元匚憑胡詞問趣可先把沒有位童耍穴前元霆疑 行曲趾再把不掃鄰元案插八中冋臥冏端練習題某班新年聯(lián)歡會原定的5個節(jié)目已排成節(jié) 目單，開演前又增加了兩個新節(jié)目如果 將這兩個新節(jié)目插入原節(jié)目單中，且兩 個新節(jié)目不相鄰，那么不同插法的種數(shù) 為（30 ）四定序問題倍縮空位插入策略例47人排隊其中甲乙丙3人順序一定共有多 少不同的排法解：（倍縮法）對于某幾個元素順序一定的排列 問題,可先把這幾個元素與其他元素一起 進行排列，然后用總排列數(shù)除以這幾個元 素之間的全排列數(shù),則共有不同排法種數(shù) 是：4Ax:|Til（空位法）設想有7把椅子讓除甲乙丙以外 的四人就坐共有上

7、種方法，其余的三個 位S甲乙丙共有丄種坐法，則共有仝種 方法 思考:可以先讓甲乙丙就坐嗎?（插入法）先排甲乙丙三個人，共有1種排法，再 把其余4四人依次插入共有4*5*6*7方法 定序問題可以用倍縮法，還可轉化為占位插I 空模型處理練習題10人身高各不相等,排成前后排，每排5人，要 求從左至右身高逐漸增加，共有多少排法？J 10五重排問題求幕策略止例5 把6名實習生分配到7個車間實習共有 多少種不同的分法Cl解:完成此事共分六步:把第一名實習生分配 到車間有2種分法.把第二名實習生分配 到車間也W7種分法，依此類推，由分步計粧許賣踴韻IJ問題的特點是嘆元素為研究 對象，元素不受位置的約束，可以

8、逐一安排 各個元素的位般地n不同的元素沒有限 制地安排在m個位置上的排列數(shù)為練習題1.某班新年聯(lián)歡會原定的5個節(jié)目已排成節(jié) 目單，開演前又增加了兩個新節(jié)目如果將這 兩個節(jié)目插入原節(jié)目單中，那么不同插法的 種數(shù)為（42 ）2.某8層大樓一樓電梯上來8名乘客人，他們 到各自的一層下電梯，下電梯的方法（T ）六.環(huán)排問題線排策略例6. 5人圍桌而坐，共有多少種坐法？解：圍桌而坐與坐成一排的不同點在于，坐成 圓形沒有首尾之分，所以固定一人A并從 此位置把圓形展成直線其余4人共有 種排法即（5-1）!一般地.n個不同元素作E形排 列，共有（n-D!種排法如果 從n個不同元素中取岀m個元素 作圓形排列共有

9、i A：練習題6顆顏色不同的鉆石，可穿成幾種鉆石圈60要考慮“鉆石圈”可以翻轉的特點設六顆顏色不同的鉆石為a,b,c d,e,f與圍桌 而坐情形不同點是abcdef與f,edc,b,a在 圍桌而坐中是兩種排法，即在鉆石圈中只 是一種排法，即把鉆石圈翻到一邊,所求數(shù) 為：(61)!/2=60七多排問題直排策略例78人排成前后兩排，每排4人，其中甲乙在 前排，丁在后排共有多少排法解人排前后兩排，相當于8人坐8把椅子，可以 把椅子排成一排先在前4個位置排甲乙兩 個特殊元素有種，再排后4個位置上的 無廉元素有種其空的5人在5個位置 上任意排列有種，則共有丄辿種一般地，元素分成多排的排列問題, 可歸結為

10、一排考慮，再分段研究.練習題nrnr有兩排座位，前排11個座位，后排12個座位，現(xiàn) 安排2人就座規(guī)定前排中間的3個座位不能坐，并 且這2人不左右相鄰，那么不同排法的種數(shù)是346甲乙都在前排：1、都在左面4個座位A；x3=6種2、都在右面4個座位同上，6種3、分列在中間3個的左右/1Jx4x4=32種共6+6+32=44種甲乙都在后排：A(22)*( 10+9+8+7+6+5+4+3+2+1 )=110種甲乙分列在前后兩排A(22)*!2*8=192種共44+110+192=346種八.排列組合混合問題先選后排策略例&有5個不同的小球裝入4個不同的盒內, 每盒至少裝一個球共有多少不同的裝解:第%

11、從5個球中選出2個組成復合元共 有G種方法再把5個元素(包含一個復合 元素)裝入4個不同的盒內有2：_種方法. 根據(jù)分步計數(shù)原理裝球的方法共有魚解決排列姐合混合問愿先選后排是量墓本 的曇思此法與相鄰元素捆綁策略相似 I 陽？_ _練習題一個班有6名戰(zhàn)士，其中正副班長各1人 現(xiàn)從中選4人完成四種不同的任務，每人 完成一種任務，且正副班長有且只有1人 參加則不同的選法有19 種U!Til九小集團問題先整體局部策珞例9用1,2, 3. 4, 5組成沒有重復數(shù)字的五位數(shù) 其中恰有兩個偶數(shù)夾1, 5這兩個奇數(shù)之 間這樣的五位數(shù)有多少個？:把1,5,2,4當作一個小集團與3排隊 共有種排法，再排小集團內部

12、共有 A淀種排法,由分步計數(shù)原理共有 A加用種排洙wfTil小集團排列問題中，先整體后局部，再結合其它策略進行處理。1 計劃展出10幅不同的畫，其中1幅水彩畫,4 幅油畫,5幅國畫，排成一行陳列，要求同一 品種的必須連在一起，并且水彩畫不在兩 端，那么共有陳列方式的種數(shù)為仝込ITil2. 5男生和5女生站成一排照像9男生相鄰，女 生也相鄰的排法有血丄種十元素相同問題隔板策略TilStTil91例10有10個運動員名額，在分給7個班，每 班至少一個,有多少種分配方案？ 因為W個名額沒有差別，把它們排成 一排。相鄰名額之間形成9個空隙。 在9個空檔中選6個位置插個隔板， 可把名額分成7份，對應地分

13、給7個 班級每一種插梅冇法對應一種分法 將n個相W的元素分成份（n, 為正#數(shù)）. I每份至少一個元素可以用H塊購板.#入 個元素排成一排的rH個空障中，所分法數(shù) 為C練習題1. 10個相同的球裝5個盒中每盒至少一 有多少裝法？2 .x+y+z+w=100求這個方程組的自然數(shù)解 的組數(shù)cL十一.正難則反總體淘汰策略例11從0,123456億&9這十個數(shù)字中取出三 個數(shù)，使其和為不小于10的偶數(shù)，不同的 取法有多少種？解：這i弓題中如果直接求不小于10的偶數(shù)很 困難，可用總體淘汰法。這十個數(shù)字中有5 個偶數(shù)5個奇數(shù)所取的三個數(shù)含有3個偶 數(shù)的取法有只含有1個偶數(shù)的取法 亠 CCi亠4亠有些排列組

14、合問甌正面直接考慮比較復雜. 両它的反面往往比較簡捷可以先求岀它的 反面再從S體中海汰.練習題我們班里有43位同學，從中任抽5人，正、 副班長、團支部書記至少有一人在內的 抽法有多少種？ c2-c：十二.平均分組問題除法策略例12. 6本不同的書平均分成3堆，每堆2本共有 多少分法？ 2 ,解:分三步取書得GC；C；種方法，但這里出現(xiàn) 重復計數(shù)的現(xiàn)象,不妨記6本書為ABCDEF 若第一步取AB,第二步取CD,第三步取EF 該分法記為（AB,CD,EF）,則CCC中還有 （AB，EF,CD）,（CD,AB,EF）,（CD，EF，AB） I/W M J i a彎 III J n J J Id, 口

15、I*腫情況，所以分組后要一定要除以 人n為均 I分的組數(shù)）避免靈復計數(shù)?！崩齢有12人。按照下列要求分配.求不同的 分法種數(shù)。分為三組，一組5人，一組4人，一組3人；甲組5人，乙組4人,一組5人，一組4人，一組3人; 每組4人； 分為甲、乙、丙三組，丙組3人； 分為甲、乙、丙三組， 分為甲、乙、丙三組， 分為三組，每組4人 分成三組，其中一組2人，另外兩組都是5人.答案GfCJ心 CJCJC，CjCJy：AJ C JC J心 陽啊心 cjAj21、結：練習I說明了非平均分配、平均分配以及部分平 均分配問題1.非平均分配問題中，沒有給出組名與給出 組名是一樣的，可以直接分步求；給出了組名 而沒指

16、明哪組是幾個，可以在沒有給出組名 （或給出組名但不指明各組多少個）種數(shù)的 基礎上乘以組數(shù)的全排列數(shù)2平均分配問題中，給出組名的分步求；若沒給出組名的, 一定要在給出組名的基礎上除以組數(shù)的全排列數(shù)3部分平均分配問題中，先考慮不平均分配，剩下的就是 平均分配.這樣分配問題就解決了.結論：給出組名（非平均中未指明 各組個數(shù)）的要在未給出組名的種 數(shù)的基礎上，乘以組數(shù)的階乘1將13個球隊分成3組T組5個隊，其它兩組4 個隊,有多少分法？ CCjCA；2.10名學生分成3組，其中一組4人，另兩組3人 但正副班長不能分在同一組有多少種不同 的分組方法（1540）3某校高二年級共有六個班級，現(xiàn)從外地轉 入4

17、名學生，要安排到該年級的兩個班級且每 班安排2名，則不同的安排方案種數(shù)為十三.合理分類與分步策略例13在一次演唱會上共10名演員，其中8人能 能唱歌 5人會跳舞現(xiàn)要演出一個2人 唱歌2人伴舞的節(jié)目，有多少選派方法？ 解:10演員中有5人只會唱歌，2人只會跳舞 3人為全能演員。以只會唱歌的5人是否 選上唱歌人員為標準進行研究只會唱 的5人中沒有人選上唱歌人員共有 種，只會唱的5人中只有1人選上唱歌人 員C C C種.只會唱的5人中只有2人 選上唱歌人員有心種，由分類計數(shù) 原理共有 廣種。本題還有如下分類標準：Yd*以3個全能演員是否選上唱歌人員為標準 *以3個全能演員是否選上跳算人員為標準 *以

18、只會跳算的2人是否選上跳算人員為標準 都可經(jīng)得到正確結果列組合問題，可按元素 拠性質進行分類，按事件發(fā)生的連續(xù)過程分 涉，做到標準明確。分步層次清楚，不重不 帽，分類標準一旦確定要貫穿于解題過程的 懷終。練習題1.從4名男生和3名女生中選出4人參加某個座 談會，若這4人中必須既有男生又有女生，則 不同的選法共有3423成人2小孩乘船游玩,1號船最多乘3人，2 號船最多乘2人,3號船只能乘1人，他們任選 2只船或3只船,但小孩不能單獨乘一只船， 這3人共有多少乘船方法.27十四構造模型策略例14馬路上有編號為1,2, 3, 4, 5, 6, 7, 8, 9的 九只路燈，現(xiàn)要關掉其中的3盞但不能關

19、 掉相鄰的2盞或3盞，也不能關掉兩端的2 盞,求滿足條件的關燈方法有多少種？ 解：把此問題當作一個排隊模型在6盞 亮燈的5個空隙中插入3個不亮的燈E常熟悉的模型，如占位填空模型，排隊 莫型，裝盒模型等，可使問題直觀解決練習題某排共有w個座位，若4人就坐，每人左右 兩邊都有空位，那么不同的坐法有多少種?120十五實際操作窮舉策略例15設有編號1.2, 3, 4. 5的五個球和編號1,2 3, 4, 5的五個盒子現(xiàn)將5個球投入這五 個盒子內要求每個盒子放一個球，并且 恰好有兩個球的編號與盒子的編號相同,- 有多少投法.解：從5個球中取出2個與盒子對號有工種 還剩下3球3盒序號不能對應，利用實際 操

20、作法，如果剩下345號球,3,4,5號盒 3號球裝4號盒時，貝14號5號球有只有1種 裝法in Lft Lft3號盒4號盒 5號盒十五實際操作窮舉策略例15設有編號1.2, 3, 4. 5的五個球和編號1,2 3, 4, 5的五個盒子，現(xiàn)將5個球投入這五 個盒子內要求每個盒子放一個球，并且 恰好有兩個球的編號與盒子的編號相同,- 有多少投法.解：從5個球中取出2個與盒子對號有工種 還剩下3球3盒序號不能對應，利用實際 操作法，如果剩下345號球,3,4,5號盒 3號球裝4號盒時，貝14號5號球有只有1種 裝法，同理3號球裝5號盒時45號球有也 只有1種裝法，由分步計數(shù)原理有2C種対于務件比較夏祭的禪列紐臺問;額，不易用 么式誑行運寡，往往利用窮舉法或畫出樹狀 圖乞收到意想不到的結弟練習題則四張(9)Til1.同一寢室4人，每人寫一張賀年卡集中起來, 然后每人各拿一張別人的賀年卡， 賀年卡不同的分配方式有多少種？42 給圖中區(qū)域涂色，要求相鄰區(qū) 域不同色，現(xiàn)有4種可選顏色，則 不同的著色方法有墓種十六.分解與合成策略例1630030能被多少個不同的偶數(shù)整除 分析：先把30030分解成質因數(shù)的乘積形式 30030=2X3X5 X 7 X11X13依題 意可知偶因數(shù)必先取2,再從其余5個 因