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

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

2、素，不同個(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è)元素間的（n-1）個(gè)空中插入 若干個(gè)（b）個(gè)板，可以把n個(gè)元素分成（b+1 ）組的方法.應(yīng)用插板法必須滿足三個(gè)條件:（1）這n個(gè)元素必須互不相異？（2）所分成的每一組至少分得一個(gè)元素？ 分成的組別彼此相異？ 舉個(gè)很普通的例子來(lái)說(shuō)明？ 把10個(gè)相同的小球放入3個(gè)不同的箱子，每個(gè)箱子至少一個(gè)，問(wèn)有幾種

3、情況？ 問(wèn)題的題干滿足 條件（1）（2）,適用插板法，c9 2=36？F面通過(guò)幾道題目介紹下插板法的應(yīng)用 ？ e二次插板法？ 例8 :在一張節(jié)目單中原有 6個(gè)節(jié)目,若保持這些節(jié)目相對(duì)次序不變，再添加3個(gè)節(jié)目，共有幾種情況？-o - 0 - 0 - 0 - 0 - 0 -三個(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è)

4、組依次 按組序號(hào)分到對(duì)應(yīng)位置的幾個(gè)元素（可能是 1個(gè)、2個(gè)、3個(gè)、4個(gè)、.）,這樣 不同的插入辦法就對(duì)應(yīng)著n個(gè)相同的元素分到m組的一種分法，這種借助于這樣 的虛擬“檔板”分配元素的方法稱之為插板法。【基本題型例題】 ?【例11共有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、形（一）1題型：有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)解決。？?【例21有8個(gè)相同的球放到三個(gè)不同的盒子里，共有（）種不同方法.A. 35 B . 28 C. 21 D. 45解答：題目允許盒子有空，則需要每個(gè)組添加1個(gè)，則球的總數(shù)為8+3X 1 = 11, 此題就有C （10, 2） =45 （種）分法了，選項(xiàng)D為正確答案?！净绢}型的變

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

7、至少2個(gè):需預(yù)先添加1個(gè)球，則總數(shù)-1編號(hào)3:至少3個(gè),需預(yù)先添加2個(gè)，才能滿足條件，后面添加一個(gè)，則總數(shù)-2 則球總數(shù)15-1-2=12個(gè)放進(jìn)3個(gè)盒子里 所以 C (11, 2) =55 (種)t例題1有3顆相同的瞎.毎天至少吃1顆,要4天吃完，有寥少種吃法？解帕JS理同上，只需要用3個(gè)扳描入到9瓢糖?？血的8個(gè)內(nèi)部空隙，將9鎮(zhèn)糖分廟4 蛆且毎俎數(shù)S不少于1即可-因陽(yáng)3個(gè)板互不相邨，其方辻環(huán)t堀刃 現(xiàn)有10個(gè)完全相同的籃球全部另給7于班級(jí).毎班至少1亍球問(wèn)共有多少 種不同的分法？I 注釋：毎組允許有誓個(gè)元素時(shí)也可M用插毆法耳原理不同*注意下題解;齣區(qū)別例題將S牛完全相同的球®到3亍

8、不同的蠢子中 7有畫少種方法？解林11邀申遼有鑒求毒個(gè)盒子申至少放一伽，因此其解蛙不同寸上面的描板富 但 仍舊是插入2傘板，分成三蛆，但在分蛆的過(guò)程中，允許兩塊板込間法有球.央若慮思維為 插入琦塊板后，與原的S個(gè)塚一共山個(gè)無(wú)素口所有揃數(shù)實(shí)際是建10個(gè)；t：t的一個(gè)認(rèn)列， 但因酋球Kffl無(wú)羞班 板楚間無(wú)董別，所以方法數(shù)實(shí)際鋪從W個(gè)無(wú)紫斯占的10個(gè)倬宣中桃 2個(gè)倬適敢上2個(gè)姑 挨余也雖全部放球即 因此法救溝 盂注釋:特別注意插板法與擁綁法插空丫曲y星別之處在于其元素是相融=t例題一條馬路上有輪號(hào)為K入、9的九盞路燈-現(xiàn)為了節(jié)約用電-要將苴中 的三盞關(guān)擅，但不能同時(shí)關(guān)掉相鄰的兩盞或三盞-則所有不砸

9、關(guān)燈方法有多少種？鮮*比 妻剣車9盞燈中的3鏈 便奠求相鄰閔燈不樂(lè)罷閉，因此可以龍嵋奠芙*車的3 蓋燈拿出來(lái)，逮禪還剰fi蓋燈，現(xiàn)喪只常把準(zhǔn)*關(guān)詡地?zé)魴懭雱⒘林那鹕w燈所形成.的 空僵之間即可-£盞燈的內(nèi)部友胡端共有7個(gè)塞，址分這數(shù)為®t例題】1案馬路的兩邊各立著山盞電燈現(xiàn)在帥了節(jié)省用電，決癥毎邊關(guān)薦3盞， 但宵了安全道SS起點(diǎn)和終點(diǎn)兩邊的燈必須是亮的而且任意一邊不直眶續(xù)關(guān)掉兩蓋.問(wèn)總 薩可以有冬少總方案？扎 120B> 320C> 43Q0 £0屛折：潸慮一側(cè)的芙燈方法，山盞燈知車2盞，還剰7>,因?qū)潈啥说臒舨荒苣?，?*2畫芙焯的燈只能播在7

10、養(yǎng)燈形成的6個(gè)內(nèi)部空隙中，衙不苗喊在兩諾,故沁數(shù)為C,【例】10個(gè)學(xué)生中，男女生各有5人，選4人參加數(shù)學(xué)競(jìng)賽。(1)至少有一名女生的選法種數(shù)為(2) A、B兩人中最多只有一人參加的選法種數(shù)為解法1： 10名中選4名代表的選法的種類：C104,排除4名參賽全是男生：C54（排除法）c104 -c54=205解法2:選1女生時(shí)，選2個(gè)女生時(shí)，選3、4個(gè)女生時(shí)的選法，分別相加(2010年國(guó)考真題)某單位訂閱了 30份學(xué)習(xí)材料發(fā)放給3個(gè)部門，每個(gè)部門至 少發(fā)放9份材料。問(wèn)一共有多少種不同的發(fā)放方法？(解析：每個(gè)部門先放8個(gè)，后面就至少放一個(gè)，三個(gè)部門則要先放 8X 3=24份, 還剩下30-24=6份

11、來(lái)放入這三個(gè)部門，且每個(gè)部門至少發(fā)放1份，則C(5,2 ) =10插 空法插空法就是對(duì)于解決 某幾個(gè)元素要求不相鄰 的問(wèn)題時(shí)，先將其他元素排好，再將 所指定的不相鄰的元素插入它們的間隙或兩端位置。首要特點(diǎn)就是不相鄰。下面 舉例說(shuō)明。.數(shù)字問(wèn)題【例】 把1, 2, 3, 4, 5組成沒(méi)有重復(fù)數(shù)字且數(shù)字1, 2不相鄰的五位數(shù)，則所有不同排法有多少種?種排解析：本題直接解答較為麻煩，因?yàn)榭上葘?3, 4, 5三個(gè)元素排定，共有五位數(shù)有法，然后再將1, 2插入四個(gè)空位共有占中排法，故由乘法原理得，所有不同的 a/ =72種。二. 節(jié)目單問(wèn)題【例】在一張節(jié)目單中原有六個(gè)節(jié)目，若保持這些節(jié)目的相對(duì)順序不變

12、，再添加進(jìn)去三個(gè)節(jié)目，則所有不同的添加方法共有多少種?解析：-0 - 0 - 0 - 0 - 0 - 0 -六個(gè)節(jié)目算上前后共有 七個(gè)空位，那么加上的第一個(gè)節(jié)目則有均'種方法；此時(shí)有七個(gè)節(jié)目，再用第二個(gè)節(jié)目去插八個(gè)空位 有冷中方法；此時(shí)有八個(gè)節(jié)目，用最后一個(gè)節(jié)目去插九個(gè)空位有熱I種方法。由乘法原理得，所有不同的添加方法為:為L(zhǎng)電L 比1 J S疋9 = 504種三. 關(guān)燈問(wèn)題【例】一條馬路上有編號(hào)1，2，3, 4，5，6，7，8，9的九盞路燈，為了節(jié)約用 電，可以把其中的三盞燈關(guān)掉，但 不能同時(shí)關(guān)掉相鄰兩盞或三盞，則所有不同的 關(guān)燈方法有多少種?解析：如果直接解答須分類討論，故可把六盞

13、亮著的燈看作六個(gè)元素，然后用不亮的三盞燈去插七個(gè)空位（用不亮的 3盞燈去插剩下亮的6盞燈空位，就有7個(gè)空位）共有p/種方法，因此所有不同的關(guān)燈方法為種。四. 停車問(wèn)題【例】停車場(chǎng)劃出一排12個(gè)停車位置，今有8輛車需要停放，要求空位置連在一 起，不同的停車方法有多少種?解析：先排好8輛車有比冷中方法，要求空位置連在一起（剩下 4個(gè)空位在一起， 來(lái)插入8輛車，有9個(gè)空位可以插），將空位置插入其中有5"種方法。所以共有I九"q' 種方法。五. 座位問(wèn)題【例】3個(gè)人坐在一排8個(gè)椅子上，若每個(gè)人左右兩邊都有空位，則坐法的種類 有多少種?解法：先拿出5個(gè)椅子排成一排，在5個(gè)椅子

14、中間出現(xiàn)4個(gè)空，再讓3個(gè)人每人帶 把椅子去插空，于是有 已' = 24種。例題】若有&也Cs D> E五亍人排Rb要求A和E兩個(gè)人必須不站在一起，則有多 少排IU方;解*打題中要#-AB兩人不站在一翹,斯哄可以丸將除盤矜E之夕卜的3個(gè)人排成一ilf> 方法數(shù)為g.煤宿再將A鄆B分別插入到典余3個(gè)人排隊(duì)所爭(zhēng)戍的4個(gè)空中，也就是從4 個(gè)空中桃出蔭個(gè)并排上兩個(gè)人，捷才辻軾注 才，0此篡;t連數(shù)盤龍t例題3個(gè)人排成一恥，要求甲乙必?zé)?瞬且與丙不*瞬，有寥少種方法？解析（甲&袖霽，可以捆鄴看件一個(gè)無(wú)索，但逐個(gè)螫體元索靈和丙不相鄰，所以先不i# 迭個(gè)甲乙毎 而姥排剰下的

15、5個(gè)人，方詵歎溝加，撚t再將T乙枸A的整體元素及丙這兩 個(gè)元素*人到此前5人所彩成的6個(gè)空里，方法敕為用，劭卜甲乙同個(gè)人內(nèi)部還喬衣排序 要求為眉口址選芳進(jìn)數(shù)沖1理/：»【怨刃5個(gè)男生3仕生排成一排*要求玄生不能相鄰，有嗥少種方法？注釋：將要求不相鄰元隸插入排好元隸時(shí)，要注釋是否帛翱插入兩端位例題若有h氐匚山E五個(gè)人排EA.要求人和B兩個(gè)人必須不站在 V且A 和E不能站在兩端，則有環(huán)排KA方法？鮮析：原理同前，也是屯排好二Ds E三個(gè)人，踐后將扱B查到二D. E所璐成的 S個(gè)空呻，a沖扣B不鮎兩蠕，所職只有斷個(gè)空可選，方進(jìn)總歆注毘找E注釋；對(duì)于®綁法和JB空法的醫(yī)別.可簡(jiǎn)單記

16、為''相鄰不鄒問(wèn)裁仝T'l糟要二所謂ffl綁法指在解決對(duì)于某幾的鈕斟湘鄒的問(wèn)題時(shí)I先整體葦慮，將栢鄰 元隸視作一個(gè)整萍參與排序然后再單獨(dú)芳慮這亍整內(nèi)gP各元素間順序.提IS；其首要特點(diǎn)是«9>苴枚捆綁法一卿應(yīng)用5不鳳枷體的*»序問(wèn)題中.【例題1著山本不同的書(shū)：苴中數(shù)學(xué)書(shū)<4本，外語(yǔ)書(shū)3本語(yǔ)立書(shū)3本.若將這些書(shū) 排成一列放在書(shū)架上讓數(shù)學(xué)帚排在一起 > 外語(yǔ)書(shū)也恰奸排在一起的排法#<()種.解柿 洼一個(gè)排凈崗題沖本總聞是不周紈其申要能數(shù)學(xué)書(shū)才#1器書(shū)部售首在一也 曲快速鮮決這個(gè)問(wèn)起 先將4桂爭(zhēng)肅市做一個(gè)元柔，特3本外語(yǔ)書(shū)肅故Y個(gè)元

17、無(wú) 踐馬和 剌下藥3本語(yǔ)文枠5個(gè)無(wú)索進(jìn)檸統(tǒng)一排序，方法戮溝A ,然怡排莊一起妁4本戳學(xué)書(shū)之 間順痔不同更對(duì)應(yīng)最后整個(gè)持序不同，所CI在4本書(shū)內(nèi)部也需察誹序，方法歎角片，同理， 外語(yǔ)和非京芳法救為者之間是令歩卸，戟帀用來(lái)法慮理得兀理採(cǎi)t例題I T'T人站成S求甲乙兩人鉆在一起，有多少種方法？辭椅：先哺甲乙廊人看成1個(gè)人，藥剩下闘3個(gè)人一起出咧，*選數(shù)為乂，釀啟甲乙 個(gè)人也和匝序更求才諜趺為Jl因此姑肌掃述澈為刈【毎口】一臺(tái)晩會(huì)上有6個(gè)唱節(jié)§和4"Tl瞬節(jié)目4個(gè)S蹈節(jié)g要排在一起有爹 少不同的對(duì)E節(jié)目的順序？注釋：運(yùn)用捆球;去時(shí)，一定要主意ffl物起釆的整體內(nèi)部是否存百

18、負(fù)序的5求.有前題目 有順序的要或.有的flJ股有.如TS的例題“C例題1 6個(gè)不同的球Sffi 5個(gè)不同ffl盒子中，5求毎個(gè)盤孑至步放一個(gè)眛 > -共有塞 歩種方法？辭折：按駅ft憊，顯嫖是2金球融劉莫申一個(gè)盒孑，S外4個(gè)煤盤射城劉4金盒孑申， 因此棄法足先從6個(gè)球中桃出2個(gè)球作為一個(gè)整體坂到一個(gè)盤子中丨然厝這個(gè)菱休羽剃下時(shí) 4個(gè)球分舟射頃裁劃5個(gè)盒子札 址芳連歎是C$4二解答：根據(jù)題目要求,所以從6個(gè)球中挑出則其中一個(gè)盒子必須得放 2個(gè)，其他每個(gè)盒子放1個(gè)球, 2個(gè)球看成一個(gè)整體，則有C62，這個(gè)整體和剩下4個(gè)球放入5個(gè)盒子里，則有A。方法是C62 A排列組合中的解題方法之插板法、

19、基礎(chǔ)理論：插板是一個(gè)無(wú)形的東西即板子，它不能代表一個(gè)元素，它區(qū)別于插空法。插 板法是用于解決“相同元素”分組問(wèn)題。 判斷插板法的題目主要看題干中的兩個(gè)詞語(yǔ)：相同元素至少為1，如果有這樣兩個(gè)詞語(yǔ)一般此題就可以直接插 板進(jìn)行解題。引例說(shuō)明：春節(jié)前單位慰問(wèn)困難職工，將 10份相同的慰問(wèn)品分給 6 名職工， 每名職工至少要分得 1 份慰問(wèn)品，分配方法共有：種種種種分析】此題第一眼給人的感覺(jué)是能用列舉法進(jìn)行分類解題，但是細(xì)一思考分類的情況太多了，不易計(jì)算，因?yàn)橄胗貌灏宸ń忸}一般是分兩類或三類。而插 板法就可以使這種為題迎刃而解。利用無(wú)形的板子把其分割開(kāi)來(lái)。【解析】“ 10份慰問(wèn)品相同且每人至少得1份”，

20、滿足插板法的兩個(gè)前提相同元素至少為 1，故可直接使用插板法。將 1 0份慰問(wèn)品依次排成一條直線，我們用插板的形式把慰問(wèn)品分給 6名職工，中間形成9個(gè)空，插上第1個(gè)板子,則第一個(gè)板子之前的分給第一名職工，在后面又插了一個(gè)板子，表示第1個(gè)板子和第2個(gè)板子之間的分給第二名職工，依次類推，因?yàn)橐纸o6個(gè)人，所以要插 5個(gè)板子，第5個(gè)板子之后的分給第六名職工，所以只要板子固定了，那么每名= 126職工分幾份慰問(wèn)品就固定了。所以10分慰問(wèn)品中間形成了 9個(gè)空;分給6個(gè)人，插入5個(gè)板;共有 種分配方法。注：估計(jì)有的同學(xué)會(huì)問(wèn)，為什么第一個(gè)慰問(wèn)品之前的位置和最后一個(gè)慰問(wèn)品之后的位置不能放板子。其實(shí)原因在于“每名

21、員工至少分1份慰問(wèn)品”，如果在第一個(gè)慰問(wèn)品之前的位置放板子那么第一名職工就一份分不到了，如果在最后一 個(gè)慰問(wèn)品之后的位置放板子那么最后一名職工就一份分不到了。二、真題舉例:例1、假設(shè)X、y、z是三個(gè)非零自然數(shù)，且有x+y+z=36,則共有多少組滿足 條件的解？【分析】此題可以看做是36塊糖排成一排，即元素相同；由于X、y、z是非零自然數(shù)，即至少為1， 問(wèn)題：x+y+z=36,順便看成3個(gè)人來(lái)分這36塊糖。滿 足插板法應(yīng)用條件?！窘馕觥扛鶕?jù)題意，36塊糖內(nèi)部形成35個(gè)空位，分給三個(gè)人，需要插兩個(gè)板子，故有9=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)共有多少種不同的分法?()【分析】根據(jù)題意，“ 10本沒(méi)有區(qū)別的圖書(shū)”即相同元素，“要求每個(gè)圖書(shū)館分得圖書(shū)數(shù)量不