排列組合--插板法、插空法、捆綁法

1、排列組合問(wèn)題一一插板法 分組、插空法不相鄰、捆綁法相鄰插板法m為空的數(shù)量【基此題型】有n個(gè)一樣的兀素，要求分到不同的m組中，且每組至少有一個(gè)兀素，冋有多少種分法?Oi_O-_101j 011 01o. . Oi_ o. . o,.n圖中“"表示一樣的名額，“"表示名額間形成的空隙，設(shè)想在這幾個(gè)空隙中插入六塊“擋板"，那么將這10個(gè)名額分割成七個(gè)局部，將第一、二、三、七個(gè)局部所包含的名額數(shù)分給第一、二、三七所學(xué)校，那么“擋板"的一種插法恰好 對(duì)應(yīng)了 io個(gè)名額的一種分配方法，反之，名額的一種分配方法也決定了檔板的一種插法，即擋板的插法種數(shù)與名額的分配 方法

2、種數(shù)是相等的，【總結(jié)】需滿足條件： n個(gè)一樣元素，不同個(gè) m組，每組至少有一個(gè)元素，那么只需在n個(gè)元素的n-1個(gè)間隙中放置 m-1塊隔板把它隔成m份即可，共有種不同方法注意：這樣對(duì)于很多的問(wèn)題，是不能直接利用插板法解題的。但，可以通過(guò)一定的轉(zhuǎn)變，將其變成符合上面3個(gè)條件的問(wèn)題,這樣就可以利用插板法解決，并且常常會(huì)產(chǎn)生意想不到的效果。插板法就是在n個(gè)兀素間的應(yīng)用插板法必須滿足三個(gè)條件：n-1丨個(gè)空中插入假設(shè)干個(gè)b個(gè)板，可以把n個(gè)兀素分成b+1組的方法. 1這n個(gè)兀素必須互不相異2所分成的每一組至少分得一個(gè)兀素3分成的組別彼此相異舉個(gè)很普通的例子來(lái)說(shuō)明把10個(gè)一樣的小球放入3個(gè)不同的箱子，每個(gè)箱子

3、至少一個(gè)，問(wèn)有幾種情況？問(wèn)題的題干滿足條件12，適用插板法，c9 2=36下面通過(guò)幾道題目介紹下插板法的應(yīng)用 e二次插板法 例8 :在一節(jié)目單中原有 6個(gè)節(jié)目，假設(shè)保持這些節(jié)目相對(duì)次序不變，再添加3個(gè)節(jié)目，共有幾種情況？-o - o - o - o - o - o -三個(gè)節(jié)目abc可以用一個(gè)節(jié)目去插 7個(gè)空位，再用第二個(gè)節(jié)目去插8個(gè)空位，用最后個(gè)節(jié)目去插 9個(gè)空位 所以一共是 c7 1 X c8 1 X c9 1=504種【根本解題思路】將 n個(gè)一樣的元素排成一行，n個(gè)元素之間出現(xiàn)了 n-1個(gè)空檔，現(xiàn)在我們用m-1個(gè)“檔板插入n-1丨個(gè)空檔中，就把n個(gè)元素隔成有序的 m份，每個(gè)組依次按組序號(hào)分

4、到對(duì)應(yīng)位置的幾個(gè) 元素可能是1個(gè)、2個(gè)、3個(gè)、4個(gè)、.，這樣不同的插入方法就對(duì)應(yīng)著n個(gè)一樣的元素分到 m組的一種分法，這種借助于這樣的虛擬“檔板"分配元素的方法稱(chēng)之為插板法?！净祟}型例題】【例1】共有10完全一樣的球分到 7個(gè)班里，每個(gè)班至少要分到一個(gè)球，問(wèn)有幾種不同分法？解析：我 們可以將10個(gè)一樣的球排成一行，10個(gè)球之間出現(xiàn)了 9個(gè)空隙，現(xiàn)在我們用6個(gè)檔板"插入這9個(gè)空隙中， 就“把10個(gè)球隔成有序的7份，每個(gè)班級(jí)依次按班級(jí)序號(hào)分到對(duì)應(yīng)位置的幾個(gè)球可能是1個(gè)、2個(gè)、3個(gè)、4個(gè)，這樣，借助于虛擬“檔板'就可以把10個(gè)球分到了 7個(gè)班中?！净祟}型的變形一】題型

5、：有n個(gè)一樣的元素，要求分到 m組中，問(wèn)有多少種不同的分法？ 解題思路：這種問(wèn)題是允許有些組中分到的元素為“0，也就是組中可以為空的。對(duì)于這樣的題，我們就首先將每組都填上1個(gè)，這樣所要元素總數(shù)就 m個(gè)，問(wèn)題也就是轉(zhuǎn)變成將n+m個(gè)元素分到 m組，并且每 組至少分到一個(gè)的問(wèn)題，也就可以用插板法來(lái)解決?！纠?】有8個(gè)一樣的球放到三個(gè)不同的盒子里，共有種不同方法.A . 35 B . 28 C . 21 D . 45解答：題目允許盒子有空，那么需要每個(gè)組添加1個(gè)，那么球的總數(shù)為8+3X仁11，此題就有C 10, 2=45種分法了，選項(xiàng) D為正確答案?！净祟}型的變形二】題型：有n個(gè)一樣的元素，要求分到

6、 m組，要求各組中分到的元素至少某個(gè)確定 值S s> 1，且每組的s值可以不同，問(wèn)有多少種不同的分法？解題思路：這種問(wèn)題是要求組中分到的元 素不能少某個(gè)確定值 s，各組分到的不是至少為一個(gè)了。對(duì)于這樣的題，我們就首先將各組都填滿，即各組 就填上對(duì)應(yīng)確實(shí)定值 s那么多個(gè)，這樣就滿足了題目中要求的最起碼的條件，之后我們?cè)俜质Ｏ碌那?。這 樣這個(gè)問(wèn)題就轉(zhuǎn)變?yōu)樯厦嫖覀兲岬降淖冃我坏膯?wèn)題了，我們也就可以用插板法來(lái)解決?！纠?】15個(gè)一樣的球放入編號(hào)為1、2、3的盒子，盒球數(shù)不少于編號(hào)數(shù)，有幾種不同的放法？解析：編號(hào)1:至少1個(gè),符合要求。編號(hào)2 :至少2個(gè)：需預(yù)先添加1個(gè)球，那么總數(shù)-1編號(hào)3:至少

7、3個(gè)，需預(yù)先添加個(gè)放進(jìn)3個(gè)盒子里2個(gè)，才能滿足條件，后面添加一個(gè)，那么總數(shù)-2那么球總數(shù)15-1-2=12112=55【例題有9顆相同的糖/每天至少吃1顆，要4天吃完有名少種吃法宅辭析：氐理同上，具需要同2個(gè)板插入到9 粧成的思個(gè)內(nèi)部空駄 轉(zhuǎn)9菽糖分成4 蛆且毎蛆魏目不少于1即可口因而3個(gè)扳互不棚鄰，實(shí)方法就為【毎功 現(xiàn)有!0個(gè)完全相同的籃球全部另給7個(gè)班級(jí).毎班至少1個(gè)球，問(wèn)共有舊少 神不同的分法？注釋:每組允許有書(shū)個(gè)元素時(shí)也可以用插取法亠苴原理不闔注意下題解;軸區(qū)別.【例;將8牛完全相同的球於到3個(gè)不同的禽子中Tt有雲(yún)少種方法？解枷此題申進(jìn)有要萃毎個(gè)盤(pán)子中至少匾一沖球，國(guó)此實(shí)解址不同孑上面

8、藥播槌為 但 仍庖是入2個(gè)板，盤(pán)廟三俎.怛在分蛆的過(guò)程申，允許兩塊扳之間沒(méi)有球.其考慮鶴雛為 插入兩塊刼亂與原來(lái)的8個(gè)球一共10介無(wú)素口所有方進(jìn)數(shù)實(shí)際是這10個(gè)無(wú)素地一個(gè)隊(duì)列， 怛因?yàn)榍蛴亻g無(wú)恙昂h板迂間儘別，所収方進(jìn)議實(shí)際為從io個(gè)元素斯占的m個(gè)位章甲桃2個(gè)佼量就±2個(gè)板，實(shí)余位置全部換球即可口因此為法數(shù)為盂注釋?zhuān)禾貏e注意插板法與捆娜法.插空滲虺別之處在于其元隸是相號(hào)口【例題1 一條馬路上有輪號(hào)為K N 、9的丸盞路燈.現(xiàn)為了節(jié)約用電.要將苴中 的三壟關(guān)擅但不能同時(shí)關(guān)掉相鄰的兩雯或三盞-那么所有不融關(guān)燈方法有裟少種？解枷 典繪蚌9盞燈中鉛3蠱憧孌求捅鄰藥燈不樂(lè)芙亂 因此可以屯將羹昊

9、焯韻3 爺燈拿出応 逮禪還飄由蓋燈.現(xiàn)在只孟把準(zhǔn)字關(guān)閉的M整燈桶入列亮著的5盞燈所弼成的 空腕之間即可口庁養(yǎng)燈的內(nèi)部友畫(huà)端共有？個(gè)塞，址芳法歎為鼻口【例題】一條馬路的兩邊各立著山盞電虹現(xiàn)在帥了書(shū)省用電事決是毎邊關(guān)掉3黃， 但宵了平安，道瞎起點(diǎn)和終點(diǎn)兩邊的燈必須星亮的，而且任意一邊不首眶續(xù)關(guān)擅兩蓋口問(wèn)總 找可以有駕少總方案？扎 120B. 320 C> 4J0D. 420霹析：君慮一側(cè)的關(guān)燈方法，山盞燈知車(chē)M盞還剩7盞卩因注兩端的燈不能走 衣 示3爺芙坤的燈只能握在7養(yǎng)燈形咸時(shí)首個(gè)內(nèi)部空隙中，衙不命綴在斑諾,故吻法數(shù)為CS更【例】10個(gè)學(xué)生中，男女生各有 5人，選4人參加數(shù)學(xué)競(jìng)賽。1至少有

10、一名女生的選法種數(shù)為 。2A、B兩人中最多只有一人參加的選法種數(shù)為 解法1： 10名中選4名代表的選法的種類(lèi)：Cio4，排除4名參賽全是男生：C54 排除法Cio4 C54=205解法2 :選1女生時(shí)，選2個(gè)女生時(shí)，選3、4個(gè)女生時(shí)的選法，分別相加2021年國(guó)考真題某單位訂閱了 30份學(xué)習(xí)材料發(fā)放給 3個(gè)部門(mén)，每個(gè)部門(mén)至少發(fā)放 9份材料。問(wèn)一共有多少種不同的發(fā)放方法？ A.7B.9C.10D.12解析：每個(gè)部門(mén)先放 8個(gè)，后面就至少放一個(gè)，三個(gè)部門(mén)那么要先放8X 3=24份，還剩下30-24=6份來(lái)放入這三個(gè)部門(mén)，且每個(gè)部門(mén)至少發(fā)放1份，那么C 5,2=10插空法插空法就是對(duì)于解決 某幾個(gè)元素

11、要求不相鄰 的問(wèn)題時(shí)，先將其他元素排好，再將所指定的不相鄰的元素插 入它們的間隙或兩端位置。首要特點(diǎn)就是不相鄰。下面舉例說(shuō)明。一. 數(shù)字問(wèn)題【例】把1，2, 3，4, 5組成沒(méi)有重復(fù)數(shù)字 且數(shù)字1, 2不相鄰的五位數(shù)，那么所有不同排法有多少種？解析：此題直接解答較為麻煩，因?yàn)榭上葘?, 4，5三個(gè)元素排定，共有種排法，然后再將1, 2插入四個(gè)空位共有種排法，故由乘法原理得，所有不同的五位數(shù)有二. 節(jié)目單問(wèn)題【例】在一節(jié)目單中原有六個(gè)節(jié)目，假設(shè)保持這些節(jié)目的相對(duì)順序不變，再添加進(jìn)去三個(gè)節(jié)目，那么所有 不同的添加方法共有多少種？解析：-o - o - o - o - o - o -六個(gè)節(jié)目算上前后

12、共有 七個(gè)空位，那么加上的第一個(gè)節(jié)目那么有種方法；此時(shí)有七個(gè)節(jié)目， 再用第二個(gè)節(jié)目去插八個(gè)空位有種方法；此時(shí)有八個(gè)節(jié)目， 用最后一個(gè)節(jié)目去插九個(gè)空位有種方法。由乘法原理得，所有不同的添加方法為：。三. 關(guān)燈問(wèn)題【例】一條馬路上有編號(hào) 1 , 2, 3, 4, 5, 6, 7, 8, 9的九盞路燈，為了節(jié)約用電，可以把其中的三盞燈關(guān)掉，但不能同時(shí)關(guān)掉相鄰兩盞或三盞 ，那么所有不同的關(guān)燈方法有多少種？解析：如果直接解答須分類(lèi)討論，故可把六盞亮著的燈看作六個(gè)元素，然后用不亮的三盞燈去插七個(gè)空位用不亮的3盞燈去插剩下亮的6盞燈空位，就有7個(gè)空位共有種方法，因此所有不同的關(guān)燈方法為種。四停車(chē)問(wèn)題【例】停

13、車(chē)場(chǎng)劃出一排12個(gè)停車(chē)位置，今有8輛車(chē)需要停放，要求空位置連在一起，不同的停車(chē)方法有多少 種？解析：先排好8輛車(chē)有種方法，要求空位置連在一起剩下4個(gè)空位在一起，來(lái)插入 8輛車(chē)，有9個(gè)空位可以插,將空位置插入其中有種方法。所以共有種方法。五座位問(wèn)題【例】3個(gè)人坐在一排8個(gè)椅子上，假設(shè) 每個(gè)人左右兩邊都有空位 ，那么坐法的種類(lèi)有多少種？解法：先拿出5個(gè)椅子排成一排，在5個(gè)椅子中間出現(xiàn)4個(gè)空，再讓3個(gè)人每人帶一把椅子去插空，于是有種。【例題】假設(shè)有茲味氏K E五亍人排IU,要我比和B兩人必須不站在一起那么有實(shí) 牛排肚方;費(fèi)鮮*廿題中要至AB兩人不站在一翹,所以可以丸席除AB之夕卜的3個(gè)人排威-揀 專(zhuān)

14、注救為g.效器再將蟲(chóng)舸B分対儲(chǔ)兀劍其余3個(gè)人排吐所爭(zhēng)成的4個(gè)空中,也就黒從4 個(gè)空中桃出禹個(gè)并出上兩個(gè)人，具方辻數(shù)曲才，邑此患為法數(shù)盤(pán)疋口1例題"人排成TA.要求甲乙必?zé)﹖晦且呂丙不相勿有寥少種方法¥解析1甲乙利鄰，可法捆鄴看件一個(gè)元索，但這個(gè)螫體元索又和丙不村鄰，所以死不的F 這個(gè)甲乙侯h而餐排剌下尿個(gè)人，方法數(shù)為疋，然啟再將甲乙枸戍的整體無(wú)素及丙這兩 個(gè)元素描心山匕前廳人所彩成的芻個(gè)空里，方進(jìn)歎為用車(chē)另外甲乙兩個(gè)人內(nèi)部還喬在排序 鑒求為啟選芳進(jìn)數(shù)為兀實(shí)丿/【遵習(xí)1 $亍男生2仕生排成一排"要求立生不能相鄰有囑少種方法？注釋?zhuān)簩⒁蟛幌噜徳夭迦肱藕迷鲿r(shí)，要注

15、釋是否育猶插入兩端位置。【例題假設(shè)有入氐匚山E五個(gè)人排BA -要求人和B兩個(gè)人必須不站在一起且A 和另不能站在兩諦，那么有塞少排EA方法？解析：原理同前，也是也排好G D E三個(gè)人，鶴馬將扱B查到二Ds E所璉成的 兩個(gè)空 因?yàn)楣螧不站廚端，所職只有兩個(gè)空可選，方進(jìn)總擻油運(yùn)總?cè)俗⑨專(zhuān)簩?duì)于捆綁法和拯空法的區(qū)別，可簡(jiǎn)單記為"相鄒冋匹讎不鄒問(wèn)歯證捆綁法r蓿要：所謂捆綁法指在解決對(duì)于梵幾十元秦a眛相鄒的問(wèn)題時(shí)I先整體考慮，將栢鄰 元素視詐整悻參與排序然后再單獨(dú)考慮這個(gè)整僭?xún)?nèi)熬各元素間順序提0S:其首要特點(diǎn)是*« 苴測(cè)§綁法一O®用在不鳳枷體的持序問(wèn)題孔【例題有W

16、本不同的書(shū)：苴中數(shù)學(xué)書(shū)4本外語(yǔ)書(shū)3本語(yǔ)文書(shū)H本.假設(shè)將這些書(shū) 排成一列放在書(shū)架上讓數(shù)學(xué)蘋(píng)徘在一起，外語(yǔ)吾也恰奸排在一起的排法共首f種。解悅迄是一個(gè)排序筒題，書(shū)本屯聞是不同竝其申娶配姒學(xué)書(shū)才#|潘書(shū)都售首在一起. 為快連解決這個(gè)問(wèn)題 先將4本裁譬韋亦做個(gè)元將M本外評(píng)書(shū)肅故一元素，鵝席種 剩下藥3本語(yǔ)丸書(shū)矢5個(gè)元索進(jìn)舒統(tǒng)一排取 方迭歎溝A ,蕊肩排莊一起妁4本戳學(xué)書(shū)之 間順痔不同也X曲最后整個(gè)持序不亂 所以在4本書(shū)內(nèi)部也需要排序，方辻歎為片*同理， 外語(yǔ)書(shū)排序方蛙歎為&明三者尢間是分歩邊嗽 戰(zhàn)而用乘法慮理得乂彳以【例題3牛人站成T* 要求甲乙兩?J粧一起，有多少種方法¥解椅：先瘠

17、申乙廊人看呢1個(gè)人，馬剩下藥3個(gè)人一起出妙山芳辻鮫為片，然啟申乙 兩個(gè)人也和匝厚姜篥，方諜數(shù)為力二 因此站肌方逸數(shù)為片g-【毎口】一臺(tái)晩會(huì)上有6個(gè)演唱卒目和4丿灣朝節(jié)目,4個(gè)舞蹈節(jié)且要排在一起，晉爹 啓不同吊商節(jié)目頤序*?莊釋:運(yùn)用捆綁梏時(shí)-一定翱主意捆堺起釆的整體內(nèi)部是否存刃負(fù)序的要求有的題目 育J頁(yè)序的要求有的那么段有口如下面的例題.例題1 6個(gè)不同的球邂5個(gè)不同酌盒子中，要求毎個(gè)禽孑至步放一個(gè)恿,一共有棗 少種方法¥ U+fl-s按黑題憊.顯奧是2個(gè)球敕到異申一個(gè)盒芋，另外4林盤(pán)敘報(bào)劉4個(gè)盒孑申， 因此務(wù)述是先從6個(gè)誅中桃岀2個(gè)球作茹一個(gè)瞪眸疲列一個(gè)蠱子中,然寤這個(gè)確休和制下的

18、 4個(gè)球4?啡利畝劃5個(gè)盒子札 址芳辻嶽是併jC解答：根據(jù)題目要求，那么其中一個(gè)盒子必須得放 2 個(gè)，其他每個(gè)盒子放 1個(gè)球，所以從 6 個(gè)球中挑出 22 5 2 5 個(gè)球看成一個(gè)整體，那么有 C62 ，這個(gè)整體和剩下 4個(gè)球放入 5個(gè)盒子里，那么有 A55 。方法是 C62 A55排列組合中的解題方法之插板法一、根底理論：插板是一個(gè)無(wú)形的東西即板子，它不能代表一個(gè)元素，它區(qū)別于插空法。插板法是用于解決“一樣元素分組問(wèn)題。 判斷插板法的題目主要看題干中的兩個(gè)詞語(yǔ)： 一樣元素 至少為 1， 如果有這樣兩個(gè)詞語(yǔ)一般此題就可以直接插板進(jìn)展解題。引例說(shuō)明：春節(jié)前單位慰問(wèn)困難職工，將10份一樣的慰問(wèn)品分

19、給 6 名職工，每名職工至少要分得 1 份 慰問(wèn)品，分配方法共有：A.84 種 B.126 種 C.210 種 D.252 種【分析】此題第一眼給人的感覺(jué)是能用列舉法進(jìn)展分類(lèi)解題，但是細(xì)一思考分類(lèi)的情況太多了，不易 計(jì)算，因?yàn)橄胗貌灏宸ń忸}一般是分兩類(lèi)或三類(lèi)。而插板法就可以使這種為題迎刃而解。利用無(wú)形的板子 把其分割開(kāi)來(lái)?！窘馕觥俊?0份慰問(wèn)品一樣且每人至少得 1份'，滿足插板法的兩個(gè)前提一樣元素至少為1,故可直接使用插板法。將 10份慰問(wèn)品依次排成一條直線，我們用插板的形式把慰問(wèn)品分給6名職工，中間形成 9 個(gè)空,插上第 1 個(gè)板子,那么第一個(gè)板子之前的分給第一名職工,在后面又插了一

20、個(gè)板子,表示第1個(gè)板子和第 2個(gè)板子之間的分給第二名職工,依次類(lèi)推,因?yàn)橐纸o 6 個(gè)人,所以要插 5個(gè)板子,第 5個(gè) 板子之后的分給第六名職工,所以只要板子固定了,那么每名職工分幾份慰問(wèn)品就固定了。所以 1 0分慰問(wèn)品中間形成了 9個(gè)空;分給 6個(gè)人,插入 5個(gè)板;共有=1 26種分配方法。注：估計(jì)有的同學(xué)會(huì)問(wèn),為什么第一個(gè)慰問(wèn)品之前的位置和最后一個(gè)慰問(wèn)品之后的位置不能放板子。 其實(shí)原因在于“每名員工至少分 1 份慰問(wèn)品,如果在第一個(gè)慰問(wèn)品之前的位置放板子那么第一名職工就 一份分不到了,如果在最后一個(gè)慰問(wèn)品之后的位置放板子那么最后一名職工就一份分不到了。二、真題舉例：例1、假設(shè)x、y、z是三

21、個(gè)非零自然數(shù)，且有x+y+z=36，那么共有多少組滿足條件的解？A.700 B.665 C.630 D.595【分析】 此題可以看做是 36 塊糖排成一排, 即元素一樣 ; 由于 x、 y、 z 是非零自然數(shù), 即至少為 1, 問(wèn) 題：x+y+z=36，順便看成3個(gè)人來(lái)分這36塊糖。滿足插板法應(yīng)用條件?！窘馕觥扛鶕?jù)題意, 36 塊糖部形成 35 個(gè)空位,分給三個(gè)人,需要插兩個(gè)板子,故有=595 種,而一種分法對(duì)應(yīng)著一組解，如 x=1，y=1，z=34,就是一組解。共有 595組解。因此，選 D。例 2、將 10 本沒(méi)有區(qū)別的圖書(shū)分到編號(hào)為 1、 2、 3的圖書(shū)館，要求每個(gè)圖書(shū)館分得圖書(shū)數(shù)量不小于其編號(hào)數(shù),問(wèn)共有多少種不同的分法 ?()A.12 B.15 C.30 D.45【分析】根據(jù)題意，“ 10 本沒(méi)有區(qū)別的圖書(shū)即一樣元素，“要求每個(gè)圖書(shū)館分得圖書(shū)數(shù)量不小于其編號(hào)數(shù)“即 1 號(hào)圖書(shū)館至少分 1本，2號(hào)圖書(shū)館至少分兩本， 3號(hào)圖書(shū)館至少分 3 本， 分析完題意之后發(fā)現(xiàn)似乎不滿足插板法的前提條件