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

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

2、個相同元素，不同個 m 組，每組至少有一個元素-，則只需在 n 個元素的 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é)目,共有幾種情況？-0 - o - o - o - o - o -二個節(jié)目 abc可以用一個節(jié)目去插 7 個空位，再用第二個節(jié)目去插8 個空位，用最后個節(jié)目去插 9 個空位所以一共是 C7 1 乞 8 1Xc9 仁 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 組的一種分法，這種借助于這排列組合問題插板法 份組）、插空法（不相鄰）、捆綁法（相鄰）精品文檔，歡迎下載2 / 10樣的虛擬 檔板”分配元素的方法稱之為插板法。【基本題型例題】【例 1】 共有 10 完全相同的球分到 7 個班里，每個班至少要分到一個球，問有幾種不同分法？解析：我們可以將 10 個相同的球排成一行，10 個球之間出現(xiàn)了 9 個空隙，現(xiàn)在我們用 6 個檔板”插入這 9 個空隙中，就 把 10 個球隔成

5、有序的 7 份，每個班級依次按班級序號分到對應(yīng)位置的幾個球（可能是1 個、2 個、3 個、4 個），這樣，借助于虛擬 檔板”就可以把 10 個球分到了 7 個班中?！净绢}型的變形（一）】題型：有 n 個相同的元素，要求分到 m 組中，問有多少種不同的分法?解題思路：這種問題是允許有些組中分到的元素為0”,也就是組中可以為空的。對于這樣的題，我們就首先將每組都填上 1 個，這樣所要元素總數(shù)就 m 個，問題也就是轉(zhuǎn)變成將（n+m ）個元素分到 m 組，并且每 組至少分到一個的問題，也就可以用插板法來解決?！纠?2】有 8 個相同的球放到三個不同的盒子里，共有（）種不同方法A. 35 B. 28

6、C. 21 D . 45解答：題目允許盒子有空，則需要每個組添加1 個，則球的總數(shù)為 8+3X仁 11，此題就有 C （10, 2） =45（種）分法了，選項 D 為正確答案?！净绢}型的變形（二）】題型：有 n 個相同的元素，要求分到 m 組，要求各組中分到的元素至少某個確定值S（s 1，且每組的 s 值可以不同），問有多少種不同的分法？解題思路：這種問題是要求組中分到的元素不能少某個確定值s,各組分到的不是至少為一個了。對于這樣的題，我們就首先將各組都填滿， 即各組就填上對應(yīng)的確定值 s 那么多個，這樣就滿足了題目中要求的最起 碼的條件，之后我們再分剩下的球。這樣這個問題就轉(zhuǎn)變?yōu)樯厦嫖覀兲?/p>

7、到的變形（一）的問題了，我們也 就可以用插板法來解決。【例 3】15 個相同的球放入編號為 1、2、3 的盒子內(nèi)，盒內(nèi)球數(shù)不少于編號數(shù)，有幾種不同的放法？ 解析：編號 1:至少 1 個，符合要求。編號 2:至少 2 個：需預(yù)先添加 1 個球，則總數(shù)-1編號 3:至少 3 個，需預(yù)先添加 2 個，才能滿足條件，后面添加一個，則總數(shù) -2 則球總數(shù) 15-1-2=12 個放進 3 個盒子里所以 C （11，2） =55 （種）【例題有 9 顆相同的韜,毎天至少吃 1 顆，要 4 天吃禿“有多少種吃法 2 解樸 感理同上，只需要用 3 個扳描入型炭的&個內(nèi)部空隙，將 9 穎總分成 4 蛆且岳

8、蛆數(shù)目不少于 1 即可因而？個板互不捆峯 其方法救為C；B【球習現(xiàn)有 10 個完全相同的籃球全部幻給 7 個班級,每班至少 1 個球“問共有哆少 種不同的分法？注釋：毎爼允許有零個元素時也可以用插愎法.直原理不同上注意下題解;堀匡別0精品文檔，歡迎下載3 / 10【例題 1 將 8 個完全相同的球放到 3 個不同的盒子中、一共有多少種方詵？解析：此題中沒有要求粵個金子中至少放一勺球，因此并舞訣不同于上面的插板法，怛 仍舊是插入 2 個扳，分成三如。但在分址的過程中，允許兩塊植之間沒有球口其盤慮思維為 播入兩塊板后，與瘟來的 8 個球一塊 10 個無素所有方法數(shù)賣際是這 10 個無索的一個隊捌，

9、 但因為球乏間無董別，板之間儘別，所以芳辻敦實際為從 i0 個無素所占的 10 個偉蓋中桃 2 個位査就上 2 個板，實余險蚩全部放球即可。因此方辻數(shù)為盂 備 9 的九葢路燈， 現(xiàn)為了節(jié)約用電要將苴中 的三盞關(guān)捧，但不能同時關(guān)毎相鄰的兩盞或三多則所有不融關(guān)燈方法有多少種 7辭析：姜羌棹 9 盞燈中的 3 盞，但要求捆鄰的燈不能關(guān) HU 因此可以先將要關(guān)槨的 3 養(yǎng)燈拿出來，這樣還剩竹盞燈，現(xiàn)衣只需把準備羌訶的 3 養(yǎng)燈插入劃亮著的 6 蓋燈所珊成的 空隙之間即可 6鑒燈的內(nèi)部及兩蠕共有了個空，故為進救為【例題】一條馬路的兩邊各立著 10 盞電燈，現(xiàn)在為了節(jié)省用電，決定毎邊關(guān)撞 3 盞， 但為了

10、安全/道路起點和終點兩邊的燈必須是亮的而且任意一邊不自誌續(xù)關(guān)掉兩盞.問總 共可以有多少總方案號A 120B. 320 C. 4)0Ek 420解析；考慮一側(cè)的羌燈方為 W 盍燈關(guān)掉 3 盞，還剩 7 蠢，因為囲瑞的燈不能黃,表 樂 3 整羌掉的燈只能據(jù)忘 7 整燈形戍的6個內(nèi)部空轡申，而不能放在兩端,故方法數(shù)為 C,【例】10 個學生中，男女生各有 5 人，選 4 人參加數(shù)學競賽。(1 )至少有一名女生的選法種數(shù)為 _。(2)A、B 兩人中最多只有一人參加的選法種數(shù)為 _解法 1：10 名中選 4 名代表的選法的種類：Cio4,排除 4 名參賽全是男生：C4(排除法)Cio4 -C54=205

11、解法 2:選 1 女生時，選 2 個女生時，選 3、4 個女生時的選法，分別相加真題(2010 年國考真題)某單位訂閱了30 份學習材料發(fā)放給 3 個部門，每個部門至少發(fā)放多少種不同的發(fā)放方法？ ()A.7B.9C.10D.12解析：每個部門先放 8 個，后面就至少放一個，三個部門則要先放8X3=24 份，還剩下 30-24=6 份來放入這三個部門，且每個部門至少發(fā)放1 份，則 C ( 5,2) =109 份材料。問一共有精品文檔，歡迎下載4 / 10插 空法插空法就是對于解決 某幾個元素要求不相鄰 的問題時，先將其他元素排好，再將所指定的不相鄰的元素插 入它們的間隙或兩端位置。首要特點就是不

12、相鄰。下面舉例說明。一.數(shù)字問題【例】 把 1, 2, 3，4, 5 組成沒有重復(fù)數(shù)字 且數(shù)字 1, 2 不相鄰的五位數(shù)，則所有不同排法有多少種？3, 4，5 三個元素排定，共有丄 種排法，然后再將 1，2 插入四個空位共有凡種排法，故由乘法原理得，所有不同的五位數(shù)有二.節(jié)目單問題【例】在一張節(jié)目單中原有六個節(jié)目，若保持這些節(jié)目的相對順序不變，再添加進去三個節(jié)目，則所有不同的添加方法共有多少種？解析：-0 - o - o - o - o - o -六個節(jié)目算上前后共有七個空位，那么加上的第一個節(jié)目則有 種方法；此時有七個節(jié)目，再用第二個節(jié)目去插八個空位有二種方法；此時有八個節(jié)目，用最后一個節(jié)目

13、去插九個空位 有種方法。由乘法原理得，所有不同的添加方法為：亠一 一 一 TV。三.關(guān)燈問題【例】一條馬路上有編號 1, 2, 3, 4, 5, 6,乙8, 9 的九盞路燈，為了節(jié)約用電，可以把其中的三盞燈關(guān) 掉，但不能同時關(guān)掉相鄰兩盞或三盞 ，則所有不同的關(guān)燈方法有多少種？解析：如果直接解答須分類討論，故可把六盞亮著的燈看作六個元素，然后用不亮的三盞燈去插七個空位【例】停車場劃出一排 12 個停車位置，今有 8 輛車需要停放，要求空位置連在一起，不同的停車方法有多少 種？解析：先排好 8 輛車有種方法，要求空位置連在一起（剩下 4 個空位在一起，來插入 8 輛車，有 9 個空位可 以插），將

14、空位置插入其中有 cJ 種方法。所以共有蘭種方法。五.座位問題【例】3 個人坐在一排 8 個椅子上，若 每個人左右兩邊都有空位，則坐法的種類有多少種？解法：先拿出 5 個椅子排成一排，在 5 個椅子中間出現(xiàn) 4 個空，再讓 3 個人每人帶一把椅子去插空，于是有 打 V 種。解析：本題直接解答較為麻煩，因為可先將（用不亮的 3盞燈去插剩下亮的6 盞燈空位，就有7 個空位）共種方法，因此所有不同的關(guān)燈方法為種。四停車問題精品文檔，歡迎下載5 / 10【例題】若有虹乩 C-. Ik E 五個人排 IU，要求 A 和 B 兩個人必須不站在一起“則有哆 少排隊方:去？解析晝題申娶求 AB 兩人不池總一起

15、，斯以可馭先將除 A 和 B 更外的 3 個人排成一挑 方法數(shù)為然賠再將 A 和 E 分別斂到莫余 3 個人排隊斯形成的 4 個空札 也就是從卻 個空中桃出兩個并排上兩個人，英方法數(shù)為才，因此迫方法歎用才【例題8 個人排成 HR.要求甲乙必須*胡 I 且與丙不木瞬有多少種方法？解析：甲乙相朋 可以據(jù)鄴看作一個元素，但這個整體元素久和向不和鄰，所以先不排 達個甲乙丙,而是排剩下的 5 個人，方法救為加，然治再將甲乙枸成的螫體無索及丙這兩 個無素柿入到此前T 人所形成的右個空里， 方珪數(shù)為/,另外甲乙兩個人內(nèi)部還存在排序 要求為崔o 畋 3進數(shù)為AA；A -【憑習 1 5 個男生 3 仕生排成一排

16、 要求玄生不能相鄰.有多少種方袪？注釋：將要求不相鄰元素插入排好無素時，要注釋是否直掰插入兩端位置.【例題 1 若有治B、C. R E 五個人排甌要求 A 和 B 兩個人必須不站在丄且丸 和 B 不能站在兩端,則有多少排臥方法？解析 1 原理同前，也是先排城 G D E 三個人然忌將人 B 查列 GDHE 所彫成的 兩個空甲，因為九 E 不濟兩端，所収只有兩個空可逸,方灤迫數(shù)為衛(wèi)注釋：對于捆綁法和插空法的區(qū)別可簡單記為“相鄒冋理莽法不鄰冋裁召沬先精品文檔，歡迎下載6 / 10精要：所謂擁綁法.指在辭決對于某幾個元康要求相鄒的問題時,先整転慮，將相鄰 元素視作一整體參與排序，然后再單獨考慮這個整

17、體內(nèi)部各元素間順序.提醒：苴首要特點是桶 4 其次捆綁法一股都應(yīng)用在不同躺的器序問題中柯【例題有10本不同的書：苴中數(shù)學書4本*外語書3本語文書3本口若將這些書 排成一列放在書架上讓數(shù)學書排在一起 外語書也恰好排在一起的排法共有（）種。解析:這是一個排序間錢，書本之間是不同鍬實申要求數(shù)學卒和外語韋都備自在一起. 為快速解決這個問廳先將4本數(shù)學書看做一個元讀，將？本外語書請做一個元素，感后和 剌下藥2本語文書拱5個兄啜進幷坑 T#序，方蛙歎為兀，然后排在一起餉4本數(shù)學書之 間順序不同也對應(yīng)暈后螫個排序不同，所以在4本書內(nèi)部也需要捋序，方法數(shù)為片，同理， 外語豐排序方法數(shù)為ga而三署之間靈好步過程

18、故而用乘法原理得AXA-【例題1 5個人站成 T要求甲乙兩人站在一起，有多少種方法g解析：先將甲乙兩人看戍1個人，再剩下的3個人一起排列，方進數(shù)為片，然冶申乙 兩個人也有順序要求，為蛙載為因此站炫法歎為火耳?！竞Ａ暋恳慌_晩會上有百個濾唱節(jié)目和4-ms節(jié)目，4個舞蹈節(jié)目要排在一起# 少不同的軸*節(jié)目的順序？注釋：運用捆綁法時，1 定要注意1S綁起來極體內(nèi)部是否存在順序的要求有的題目 肓順序的要求 育的則沒有.如下面的例題-【例題6個不同的球放到5個不同的當子中，要求毎個盤子至少放一個球* 一共有容 少種方法解析：榜蹩蹇懣，顯慈是2個球放劉其中一個食子，另外4個球分別放割4個盒孑中， 因此方辻劉I

19、從6個嫌中桃出2個球作為亠個整體放別一個蠹子申,魅常送個螫俸春剩下的4個球分昂甘非列換劃5個金子申,故為法數(shù)是CAr.解答：根據(jù)題目要求， 則其中一個盒子必須得放 2 個，其他每個盒子放 1 個球，所以從 6 個球中挑出 2 個球2525看成一個整體，則有C6,這個整體和剩下 4 個球放入 5 個盒子里，則有A5。方法是C6A排列組合中的解題方法之插板法一、基礎(chǔ)理論：插板是一個無形的東西即板子，它不能代表一個元素，它區(qū)別于插空法。插板法是用于解決相同元素”分組問題。判斷插板法的題目主要看題干中的兩個詞語：相同元素至少為 1，如果有這樣兩個詞語一般此題就可以直接插板進行解題。引例說明：春節(jié)前單位

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

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

22、慰問品之后的位置放板子那么最后一名職工就一份分不到了。二、 真題舉例：例 1、假設(shè) X、y、z 是三個非零自然數(shù)，且有x+y+z=36，則共有多少組滿足條件的解？A.700B.665C.630D.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ù)，問共有多少種不同的分法？()A.12 B.15C.30D.45【分析】根據(jù)題意，10 本沒有區(qū)別的圖書”即相同元素，要求每個圖書館分得圖書數(shù)量不小于其編號數(shù)即 1 號圖書館至少分 1 本，2 號圖書館至少分兩本，3 號圖書館至少分 3 本，分析完題意之后發(fā)現(xiàn)似乎不滿足插板法的前提條件至少為1，類似的這種題目我們只需要適當變形就可利用插