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

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

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

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

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

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

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

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

8、某單位訂 30 份學習材料發(fā)3 個部門，每個部門至少9 份材料。問閱了放給發(fā)放 一共有多少種不同的發(fā)放方法？（）A.7B.9C.1 D.120解析：每個部門先放 8 個，后面就至少放一個，三個部門 則要先放入這三個部門，且每個部門至少發(fā)放 1 份，則 C （5,2 ）=1083=2 份，還剩4 下30-24=6份放來插空法插空法就是對于解決某幾個元素要求不相鄰的問題時，先將其他元素排好，再將所指定的不相鄰的元素插入它們的間隙或兩端位置。首要特點就是不相鄰。下面舉例說明。. 數(shù)字問題例】把 1，2，3，4，5 組成沒有重復數(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é)目，位有 種方法。由乘法原理得，所有不同的添加方法為：. 關燈問題【例】一條馬路上有編號 1，2，3，4，5，6，7，8，9 的九盞路燈，為了節(jié)約

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

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

12、1，如果有 這樣兩個詞 語一般此題就可以直接插板進行解題。引例說明：春節(jié)前單位慰問困難職工，將 10 份相同的慰問品分給 6 名 職工，每名職工至少要分得 1份慰問品，分配方法共有：A.84 種 B.126 種 C.210 種 D.252 種 【分析】此題第一眼給人的感覺是能用列舉法進行分類解題，但是細一思考分類的情況太多了， 不易計算，因為想用插板法解題一般是分兩類或三類。而插板法就可以使這種為題迎刃而解。利用無形的 板子 把其分割開來?！窘馕觥俊?10 份慰問品相同且每人至少得 滿足插板法的兩個前提相同元素至少為可直接使用插板法。將 10 份慰問品依次排成一條直線， 我們用插板的形式把慰問

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

14、后一個慰問品之后的位置放板子那么最后一名職工就一份分不到了。x+y+z=36，則共有多少組、真題舉例：例 1、假設 x、y、 z 是三個非零自然數(shù)，且有 滿足條件的解A.700B.665C.630D.595【分析】此題可以看做是 36 塊糖排成一排，即元素相同 ; 由于 x、y、 z 是非零自然數(shù)，即至少為 1，問題： x+y+z=36 ，順便看成3 個人來分這 36 塊糖。滿足插板法應用條件。【解析】根據(jù)題意， 36 塊糖內部形成 分給三個人，需要插兩個板子，故有35 個空位，=595 種，而一種分法對應著一組解，如有 595 組解。因此，選x=1，y=1，z=34，就是一組解。共D。例 2

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

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