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

擺列組合問題——插板法(分組)、插空法（不相鄰）、捆綁法（相鄰）插板法（m為空的數(shù)目）【基本題型】有n個(gè)同樣的元素，要求分到不一樣的m組中，且每組最罕有一個(gè)元素，問有多少種分法？圖中“”表示同樣的名額，“”表示名額間形成的縫隙，假想在這幾個(gè)縫隙中插入六塊“擋板”，則將這10個(gè)名額切割成七個(gè)部分，將第一、二、三、七個(gè)部分所包括的名額數(shù)分給第一、二、三七所學(xué)校，則“擋板”的一種插法恰巧對(duì)應(yīng)了10個(gè)名額的一種分派方法，反之，名額的一種分派方法也決定了檔板的一種插法，即擋板的插法種數(shù)與名額的分派方法種數(shù)是相等的，【總結(jié)】需知足條件：n個(gè)同樣元素，不一樣個(gè)m組，每組最罕有一個(gè)元素，則只需在n個(gè)元素的n-1個(gè)空隙中擱置m-1塊隔板把它隔成m份即可,共有種不一樣方法。注意：這樣關(guān)于好多的問題，是不可以直接利用插板法解題的。但，能夠經(jīng)過(guò)必定的轉(zhuǎn)變，將其變?yōu)榍泻仙线?個(gè)條件的問題，這樣就能夠利用插板法解決，而且經(jīng)常會(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è),問有幾種狀況?問題的題干知足條件（1）（2）,合用插板法,c92=36下邊經(jīng)過(guò)幾道題目介紹下插板法的應(yīng)用e二次插板法例8：在一張節(jié)目單中原有個(gè)節(jié)目,共有幾種狀況?

6個(gè)節(jié)目,若保持這些節(jié)目相對(duì)序次不變

,再增添

3-o-o-o-o-o-o-三個(gè)節(jié)目abc能夠用一個(gè)節(jié)目去插7個(gè)空位,再用第二個(gè)節(jié)目去插8個(gè)空位,用最后個(gè)節(jié)目去插個(gè)空位所以一共是c71×c81×c91=504種【基本解題思路】將n個(gè)同樣的元素排成一行，n個(gè)元素之間出現(xiàn)了（n-1）個(gè)空檔，此刻我們用（m-1）個(gè)“檔板”插入（n-1）個(gè)空檔中，就把n個(gè)元素隔成有序的m份，每個(gè)組挨次按組序號(hào)分到對(duì)應(yīng)地點(diǎn)的幾個(gè)元素（可能是1個(gè)、2個(gè)、3個(gè)、4個(gè)、.），這樣不一樣的插入方法就對(duì)應(yīng)著n個(gè)同樣的元素分到m組的一種分法，這類借助于這樣的虛構(gòu)“檔板”分派元素的方法稱之為插板法。【基本題型例題】【例1】共有10完整同樣的球分到7個(gè)班里，每個(gè)班最少要分到一個(gè)球，問有幾種不一樣分法？分析：我們能夠?qū)?0個(gè)同樣的球排成一行，10個(gè)球之間出現(xiàn)了9個(gè)縫隙，現(xiàn)在我們用6個(gè)檔板”插入這9個(gè)縫隙中，就“把10個(gè)球隔成有序的7份，每個(gè)班級(jí)挨次按班級(jí)序號(hào)分到對(duì)應(yīng)地點(diǎn)的幾個(gè)球（可能是1個(gè)、2個(gè)、3個(gè)、4個(gè)），這樣，借助于虛構(gòu)“檔板”就能夠把10個(gè)球分到了7個(gè)班中?！净绢}型的變形（一）】題型：有n個(gè)同樣的元素，要求分到m組中，問有多少種不一樣的分法？解題思路：這類問題是同意有些組中分到的元素為“0，”也就是組中能夠?yàn)榭盏?。關(guān)于這樣的題，我們就第一將每組都填上1個(gè)，這樣所要元素總數(shù)就m個(gè)，問題也就是轉(zhuǎn)變?yōu)閷ⅲ╪+m）個(gè)元素分到m組，而且每組最少分到一個(gè)的問題，也就能夠用插板法來(lái)解決?！纠?】有8個(gè)同樣的球放到三個(gè)不一樣的盒子里，共有（）種不一樣方法.A．35B．28C．21D．45解答：題目同意盒子有空，則需要每個(gè)組增添1個(gè)，則球的總數(shù)為8+3×1=11，本題就有C（10，2）=45（種）分法了，選項(xiàng)D為正確答案?！净绢}型的變形（二）】題型：有n個(gè)同樣的元素，要求分到m組，要求各組中分到的元素最少某個(gè)確立值S（s＞1，且每組的s值能夠不一樣），問有多少種不一樣的分法？解題思路：這類問題是要求組中分到的元素不可以少某個(gè)確立值s，各組分到的不是最少為一個(gè)了。關(guān)于這樣的題，我們就第一將各組都填滿，即各組就填上對(duì)應(yīng)確實(shí)定值s那么多個(gè)，這樣就知足了題目中要求的最最少的條件，以后我們?cè)俜质Ｏ碌那颉＿@樣這個(gè)問題就轉(zhuǎn)變?yōu)樯线呂覀兲岬降淖冃危ㄒ唬┑膯栴}了，我們也就能夠用插板法來(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：最少2個(gè)：需早先增添1個(gè)球，則總數(shù)-1編號(hào)3：最少3個(gè)，需早先增添2個(gè)，才能知足條件，后邊增添一個(gè)，則總數(shù)-2則球總數(shù)15-1-2=12個(gè)放進(jìn)3個(gè)盒子里所以C（11，2）=55（種）【例】10個(gè)學(xué)生中，男女生各有5人，選4人參加數(shù)學(xué)比賽。（1）最罕有一名女生的選法種數(shù)為_______________。（2）A、B兩人中最多只有一人參加的選法種數(shù)為___________解法1：10名中選4名代表的選法的種類：C10清除4名參賽全部是男生：C4(清除法)C4=2055C105解法2：選1女生時(shí)，選2個(gè)女生時(shí)，選3、4個(gè)女生時(shí)的選法，分別相加（2010年國(guó)考真題）某單位定閱了30份學(xué)習(xí)資料發(fā)放給3個(gè)部門，每個(gè)部門至少發(fā)放9份資料。問一共有多少種不一樣的發(fā)放方法？（）A.7B.9C.10D.12分析：每個(gè)部門先放8個(gè)，后邊就最少放一個(gè)，三個(gè)部門則要先放8×3=24份，還剩下30-24=6份來(lái)放入這三個(gè)部門，且每個(gè)部門最少發(fā)放1份，則C（5,2）=10插空法插空法就是關(guān)于解決某幾個(gè)元素要求不相鄰的問題時(shí)，先將其余元素排好，再將所指定的不相鄰的元素插入它們的空隙或兩頭地點(diǎn)。首要特色就是不相鄰。下邊舉例說(shuō)明。一.數(shù)字問題【例】把1，2，3，4，5構(gòu)成沒有重復(fù)數(shù)字且數(shù)字1，2不相鄰的五位數(shù)，則所有不一樣排法有多少種？分析：本題直接解答較為麻煩，因?yàn)榭上葘?，4，5三個(gè)元素排定，共有種排法，而后再將1，2插入四個(gè)空位共有種排法，故由乘法原理得，全部不一樣的五位數(shù)有二.節(jié)目單問題【例】在一張節(jié)目單中原有六個(gè)節(jié)目，若保持這些節(jié)目的相對(duì)次序不變，再添加進(jìn)去三個(gè)節(jié)目，則全部不一樣的增添方法共有多少種？分析：-o-o-o-o-o-o-六個(gè)節(jié)目算上前后共有七個(gè)空位，那么加上的第一個(gè)節(jié)目則有種方法；此時(shí)有七個(gè)節(jié)目，再用第二個(gè)節(jié)目去插八個(gè)空位有種方法；此時(shí)有八個(gè)節(jié)目，用最后一個(gè)節(jié)目去插九個(gè)空位有種方法。由乘法原理得，全部不一樣的增添方法為：。三.關(guān)燈問題【例】一條馬路上有編號(hào)1，2，3，4，5，6，7，8，9的九盞路燈，為了節(jié)儉用電，能夠把此中的三盞燈關(guān)掉，但不可以同時(shí)關(guān)掉相鄰兩盞或三盞，則全部不一樣的關(guān)燈方法有多少種？分析：假如直接解答須分類議論，故可把六盞亮著的燈看作六個(gè)元素，而后用不亮的三盞燈去插七個(gè)空位（用不亮的3盞燈去插剩下亮的6盞燈空位，就有7個(gè)空位）共有種方法，所以全部不一樣的關(guān)燈方法為種。四.泊車問題【例】泊車場(chǎng)劃出一排12個(gè)泊車地點(diǎn)，今有8輛車需要停放，要求空地點(diǎn)連在一同，不一樣的泊車方法有多少種？分析：先排好8輛車有種方法，要求空地點(diǎn)連在一同（剩下來(lái)插入8輛車，有9個(gè)空位能夠插），將空地點(diǎn)插入此中有

4個(gè)空位在一同，種方法。所以共有種方法。五.

座位問題【例】

3個(gè)人坐在一排

8個(gè)椅子上，若每個(gè)人左右兩邊都有空位

，則坐法的種類有多少種？解法：先取出5個(gè)椅子排成一排，在5個(gè)椅子中間出現(xiàn)4個(gè)空，再讓3個(gè)人每人帶一把椅子去插空，于是有種。捆綁法解答：依據(jù)題目要求，則此中一個(gè)盒子一定得放2個(gè)，其余每個(gè)盒子放1個(gè)球，所以從6個(gè)球中挑出2個(gè)球當(dāng)作一個(gè)整體，則有C62，這個(gè)整體和剩下4個(gè)球放入5個(gè)盒子里，則有A55。方法是C62A55擺列組合中的解題方法之插板法一、基礎(chǔ)理論：插板是一個(gè)無(wú)形的東西即板子，它不可以代表一個(gè)元素，它差別于插空法。插板法是用于解決“同樣元素”分組問題。判斷插板法的題目主要看題干中的兩個(gè)詞語(yǔ)：①同樣元素②最少為1，假如有這樣兩個(gè)詞語(yǔ)一般本題就能夠直接插板進(jìn)行解題。引例說(shuō)明：春節(jié)前單位慰勞困難員工，將10份同樣的慰勞品分給6名員工，每名員工最少要分得1份慰勞品，分派方法共有：A.84種B.126種C.210種D.252種【剖析】本題第一眼給人的感覺是能用列舉法進(jìn)行分類解題，可是細(xì)一思慮分類的狀況太多了，不易計(jì)算，因?yàn)橄胗貌灏宸ń忸}一般是分兩類或三類。而插板法就能夠使這類為題水到渠成。利用無(wú)形的板子把其切割開來(lái)?！痉治觥俊?0份慰勞品同樣且每人最少得1份”，知足插板法的兩個(gè)前提①同樣元素②最少為1，故可直接使用插板法。將10份慰勞品挨次排成一條直線，我們用插板的形式把慰勞品分給6名員工，中間形成9個(gè)空，插上第1個(gè)板子，則第一個(gè)板子以前的分給第一名員工，在后邊又插了一個(gè)板子，表示第1個(gè)板子和第2個(gè)板子之間的分給第二名員工，挨次類推，因?yàn)橐纸o6個(gè)人，所以要插5個(gè)板子，第5個(gè)板子以后的分給第六名員工，所以只需板子固定了，那么每名員工分幾份慰勞品就固定了。所以10分慰勞品中間形成了9個(gè)空;分給6個(gè)人，插入5個(gè)板;共有=126種分派方法。注：預(yù)計(jì)有的同學(xué)會(huì)問，為何第一個(gè)慰勞品以前的地點(diǎn)和最后一個(gè)慰勞品以后的地點(diǎn)不可以放板子。其實(shí)原由在于“每名員工最少分1份慰勞品”，假如在第一個(gè)慰勞品以前的地點(diǎn)放板子那么第一名員工就一份分不到了，假如在最后一個(gè)慰勞品以后的地點(diǎn)放板子那么最后一名員工就一份分不到了。二、真題舉例：例1、假定x、y、z是三個(gè)非零自然數(shù)，且有x+y+z=36，則共有多少組滿足條件的解?【剖析】本題能夠看做是36塊糖排成一排，即元素同樣;因?yàn)?/p>

x、y、z是非零自然數(shù)，即最少為1，問題：x+y+z=36，趁便當(dāng)作3個(gè)人來(lái)分這36塊糖。滿足插板法應(yīng)用條件。【分析】依據(jù)題意，36塊糖內(nèi)部形成35個(gè)空位，分給三個(gè)人，需要插兩個(gè)板子，故有=595種，而一種分法對(duì)應(yīng)著一組解，如x=1，y=1，z=34，就是一組解。共有595組解。所以，選D。例2、將

10本沒有區(qū)其余圖書分到編號(hào)為

1、2、3

的圖書室，要求每個(gè)圖書館分得圖書數(shù)目不小于其編號(hào)數(shù)，問共有多少種不一樣的分法?( )【剖析】依據(jù)題意，“10本沒有區(qū)其余圖書”即同樣元素，“要求每個(gè)圖書室分得圖書數(shù)目不小于其編號(hào)數(shù)“即1號(hào)圖書室最少分1本，2號(hào)圖書室最少分兩本，3號(hào)圖書室最少分3本，剖析完題意以后發(fā)現(xiàn)仿佛不知足插板法的前提條件最少為1，近似的這類題目我們只需要適合變形便可利用插板法解題。【分析】1號(hào)圖書室最少分1本，已經(jīng)知足最少為1，不用變形。而2號(hào)圖書室最少分兩本，所以可從10本中取出一本先給2號(hào)圖書室。而3號(hào)圖書室最少分3本，能夠從10本中取出兩本書給3號(hào)圖書室，所以在給出一本和兩本，那么還剩下7本，此刻1號(hào)，2號(hào)，3號(hào)圖書室最少在發(fā)放一本書就能夠知足了，那么此時(shí)就能夠用插板法解題。所以答案是=15小結(jié)：題目中一般有同樣元素，最少為何，本題都可用插板法解題，所以大家要不停熟習(xí)插板法的應(yīng)用。三、插板法和列舉法的對(duì)照例3、10個(gè)名額分派到八個(gè)班，每班最少一個(gè)名額，問有多少種不一樣的分派方法?A.34種B.36種C.40種D.42種【答案】B【列舉法】先每個(gè)班級(jí)分一個(gè)名額，而后剩下兩個(gè)名額，①假如兩個(gè)名額分到一個(gè)班級(jí)里面則有,②假如兩個(gè)名額分到兩個(gè)班級(jí)里面則有種分法，則共有8+28=36.【插板法】10個(gè)名額