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

1、排列組合問題插板法(分組)、插空法（不相鄰）、捆綁法（相鄰） 插 板 法 （m為空的數(shù)量） 【基本題型】有n個相同的元素，要求分到不同的m組中，且每組至少有一個元素，問有多少種分法？圖中“ ”表示相同的名額，“ ”表示名額間形成的空隙，設(shè)想在這幾個空隙中插入六塊“擋板”，則將這10 個名額分割成七個部分，將第一、二、三、七個部分所包含的名額數(shù)分給第一、二、三七所學(xué)校，則“擋板”的一種插法恰好對應(yīng)了10 個名額的一種分配方法，反之，名額的一種分配方法也決定了檔板的一種插法，即擋板的插法種數(shù)與名額的分配方法種數(shù)是相等的，【總結(jié)】需滿足條件：n個相同元素，不同個m組，每組至少有一個元素，則只需在n個

2、元素的n-1個間隙中放置m-1塊隔板把它隔成m份即可,共有種不同方法。注意：這樣對于很多的問題，是不能直接利用插板法解題的。但，可以通過一定的轉(zhuǎn)變，將其變成符合上面3個條件的問題，這樣就可以利用插板法解決，并且常常會產(chǎn)生意想不到的效果。插板法就是在n個元素間的（n-1）個空中插入 若干個（b）個板,可以把n個元素分成（b+1）組的方法.應(yīng)用插板法必須滿足三個條件：（1） 這n個元素必須互不相異 （2） 所分成的每一組至少分得一個元素 (3) 分成的組別彼此相異 舉個很普通的例子來說明 把10個相同的小球放入3個不同的箱子,每個箱子至少一個,問有幾種情況?

3、問題的題干滿足 條件（1）（2）,適用插板法,c9 2=36 下面通過幾道題目介紹下插板法的應(yīng)用 e 二次插板法 例8 ：在一張節(jié)目單中原有6個節(jié)目,若保持這些節(jié)目相對次序不變,再添加3個節(jié)目,共有幾種情況?-o - o - o - o - o - o - 三個節(jié)目abc 可以用一個節(jié)目去插7個空位,再用第二個節(jié)目去插8個空位,用最后個節(jié)目去插9個空位 所以一共是 c7 1×c8 1×c9 1=504種【基本解題思路】將n個相同的元素排成一行，n個元素之間出現(xiàn)了（n-1）個空檔，現(xiàn)在我們用（m-1）個“檔板”插入（n-1）個

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

5、了7個班中。    【基本題型的變形（一）】題型：有n個相同的元素，要求分到m組中，問有多少種不同的分法？解題思路：這種問題是允許有些組中分到的元素為“0”，也就是組中可以為空的。對于這樣的題，我們就首先將每組都填上1個，這樣所要元素總數(shù)就m個，問題也就是轉(zhuǎn)變成將（n+m）個元素分到m組，并且每組至少分到一個的問題，也就可以用插板法來解決。   【例2】有8個相同的球放到三個不同的盒子里，共有（ ）種不同方法.A35 B28 C21 D45解答：題目允許盒子有空，則需要每個組添加1個，則球的總數(shù)為8+3×1=11，此題就有C

6、（10，2）=45（種）分法了，選項D為正確答案?！净绢}型的變形（二）】題型：有n個相同的元素，要求分到m組，要求各組中分到的元素至少某個確定值S（s1，且每組的s值可以不同），問有多少種不同的分法？ 解題思路：這種問題是要求組中分到的元素不能少某個確定值s，各組分到的不是至少為一個了。對于這樣的題，我們就首先將各組都填滿，即各組就填上對應(yīng)的確定值s那么多個，這樣就滿足了題目中要求的最起碼的條件，之后我們再分剩下的球。這樣這個問題就轉(zhuǎn)變?yōu)樯厦嫖覀兲岬降淖冃危ㄒ唬┑膯栴}了，我們也就可以用插板法來解決。【例3】15個相同的球放入編號為1、2、3的盒子內(nèi)，盒內(nèi)球數(shù)不少于編號數(shù)，有幾種不同的放法？解

7、析：編號1：至少1個，符合要求。編號2：至少2個：需預(yù)先添加1個球，則總數(shù)-1編號3：至少3個，需預(yù)先添加2個，才能滿足條件，后面添加一個，則總數(shù)-2則球總數(shù)15-1-2=12個放進3個盒子里所以C（11，2）=55（種）【例】10 個學(xué)生中，男女生各有5 人，選4 人參加數(shù)學(xué)競賽。（1）至少有一名女生的選法種數(shù)為_。（2）A、B 兩人中最多只有一人參加的選法種數(shù)為_解法1：10 名中選4 名代表的選法的種類：C104, 排除4名參賽全是男生：C54 (排除法)C104 -C54=205解法2：選1女生時，選2個女生時，選3、4個女生時的選法，分別相加真題（2010年國考真題）某單位訂閱了30

8、份學(xué)習(xí)材料發(fā)放給3個部門，每個部門至少發(fā)放9份材料。問一共有多少種不同的發(fā)放方法？（ ） A.7 B.9 C.10 D.12 解析：每個部門先放8個，后面就至少放一個，三個部門則要先放8×3=24份，還剩下30-24=6份來放入這三個部門，且每個部門至少發(fā)放1份，則C（5,2）=10 插 空 法 插空法就是對于解決某幾個元素要求不相鄰的問題時，先將其他元素排好，再將所指定的不相鄰的元素插入它們的間隙或兩端位置。首要特點就是不相鄰。下面舉例說明。一. 數(shù)字問題【例】 把1，2，3，4，5組成沒有重復(fù)數(shù)字且數(shù)字1，2不相鄰的五位數(shù)，則所有不同排法有多少種？解析：本題直接解答較為麻煩，因為

9、可先將3，4，5三個元素排定，共有種排法，然后再將1，2插入四個空位共有種排法，故由乘法原理得，所有不同的五位數(shù)有二. 節(jié)目單問題【例】在一張節(jié)目單中原有六個節(jié)目，若保持這些節(jié)目的相對順序不變，再添加進去三個節(jié)目，則所有不同的添加方法共有多少種？解析：-o - o - o - o - o - o - 六個節(jié)目算上前后共有七個空位，那么加上的第一個節(jié)目則有種方法；此時有七個節(jié)目，再用第二個節(jié)目去插八個空位有種方法；此時有八個節(jié)目，用最后一個節(jié)目去插九個空位有種方法。由乘法原理得，所有不同的添加方法為：。三. 關(guān)燈問題【例】一條馬路上有編號1，2，3，4，5，6，7，8，9的九盞路燈，為

10、了節(jié)約用電，可以把其中的三盞燈關(guān)掉，但不能同時關(guān)掉相鄰兩盞或三盞，則所有不同的關(guān)燈方法有多少種？解析：如果直接解答須分類討論，故可把六盞亮著的燈看作六個元素，然后用不亮的三盞燈去插七個空位（用不亮的3盞燈去插剩下亮的6盞燈空位，就有7個空位）共有種方法，因此所有不同的關(guān)燈方法為種。四. 停車問題【例】停車場劃出一排12個停車位置，今有8輛車需要停放，要求空位置連在一起，不同的停車方法有多少種？解析：先排好8輛車有種方法，要求空位置連在一起（剩下4個空位在一起，來插入8輛車，有9個空位可以插），將空位置插入其中有種方法。所以共有種方法。五. 座位問題【例】 3個人坐在一排8個椅子上，若每個人左右

11、兩邊都有空位，則坐法的種類有多少種？解法：先拿出5個椅子排成一排，在5個椅子中間出現(xiàn)4個空，再讓3個人每人帶一把椅子去插空，于是有種。 捆 綁 法 解答：根據(jù)題目要求，則其中一個盒子必須得放2個，其他每個盒子放1個球，所以從6個球中挑出2個球看成一個整體，則有，這個整體和剩下4個球放入5個盒子里，則有。方法是排列組合中的解題方法之插板法一、基礎(chǔ)理論：插板是一個無形的東西即板子，它不能代表一個元素，它區(qū)別于插空法。插板法是用于解決“相同元素”分組問題。判斷插板法的題目主要看題干中的兩個詞語：相同元素 至少為1， 如果有這樣兩個詞語一般此題就可以直接插板進行解題。引例說明：春節(jié)

12、前單位慰問困難職工，將10份相同的慰問品分給6名職工，每名職工至少要分得1份慰問品，分配方法共有：A.84種 B.126種 C.210種 D.252種【分析】此題第一眼給人的感覺是能用列舉法進行分類解題，但是細一思考分類的情況太多了，不易計算，因為想用插板法解題一般是分兩類或三類。而插板法就可以使這種為題迎刃而解。利用無形的板子把其分割開來。【解析】“10份慰問品相同且每人至少得1份”，滿足插板法的兩個前提相同元素至少為1，故可直接使用插板法。將10份慰問品依次排成一條直線，我們用插板的形式把慰問品分給6名職工，中間形成9個空，插上第1個板子，則第一個板子之前的分

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

14、非零自然數(shù)，且有x+y+z=36，則共有多少組滿足條件的解?A.700 B.665 C.630 D.595【分析】此題可以看做是36塊糖排成一排，即元素相同;由于x、y、z是非零自然數(shù)，即至少為1， 問題：x+y+z=36，順便看成3個人來分這36塊糖。滿足插板法應(yīng)用條件。【解析】根據(jù)題意，36塊糖內(nèi)部形成35個空位，分給三個人，需要插兩個板子，故有=595種，而一種分法對應(yīng)著一組解，如x=1，y=1，z=34，就是一組解。共有595組解。因此，選D。例2、將10本沒有區(qū)別的圖書分到編號為1、2、3的圖書館，要求每個圖書館分得圖書數(shù)量不小于其編號數(shù)，問共

15、有多少種不同的分法?( )A.12 B.15 C.30 D.45【分析】根據(jù)題意，“10本沒有區(qū)別的圖書”即相同元素，“要求每個圖書館分得圖書數(shù)量不小于其編號數(shù)“即1號圖書館至少分1本，2號圖書館至少分兩本，3號圖書館至少分3本，分析完題意之后發(fā)現(xiàn)似乎不滿足插板法的前提條件至少為1，類似的這種題目我們只需要適當變形就可利用插板法解題?！窘馕觥?號圖書館至少分1本，已經(jīng)滿足至少為1，不用變形。而2號圖書館至少分兩本，所以可從10本中取出一本先給2號圖書館。而3號圖書館至少分3本，可以從10本中取出兩本書給3號圖書館，所以在給出一本和兩本，那么還剩下7本，現(xiàn)

16、在1號，2號，3號圖書館至少在發(fā)放一本書就可以滿足了，那么此時就可以用插板法解題。所以答案是 =15    小結(jié)：題目中一般有相同元素，至少為什么，此題都可用插板法解題，所以大家要不斷熟悉插板法的應(yīng)用。三、插板法和列舉法的對比例3、10個名額分配到八個班，每班至少一個名額，問有多少種不同的分配方法?A.34種 B.36種 C.40種 D.42種【答案】B【列舉法】先每個班級分一個名額，然后剩下兩個名額，如果兩個名額分到一個班級里面則有 ,如果兩個名額分到兩個班級里面則有 種分法，則共有8+28=36.【插板法】10個名額9個空，插入7個板，共有 種分配方法。例4、某單位訂閱了30份學(xué)習(xí)材料發(fā)放給3個部門，每個部門至少發(fā)放9份材料。問一共有