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

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

2、有種不同方法注意：這樣對(duì)于很多的問(wèn)題，是不能直接利用插板法解題的。但，可以通過(guò)一定的轉(zhuǎn)變，將其變成符合上面3個(gè)條件的問(wèn)題,這樣就可以利用插板法解決，并且常常會(huì)產(chǎn)生意想不到的效果?！净窘忸}思路】將n個(gè)相同的元素排成一行，n個(gè)元素之間出現(xiàn)了 （n-1 ）個(gè)空檔，現(xiàn)在我們用（m-1）個(gè)“檔板”插入（n-1 ） 個(gè)空檔中，就把n個(gè)元素隔成有序的 m份，每個(gè)組依次按組序號(hào)分到對(duì)應(yīng)位置的幾個(gè)元素（可能是1個(gè)、2個(gè)、3個(gè)、4個(gè)、.），這樣不同的插入辦法就對(duì)應(yīng)著n個(gè)相同的元素分到 m組的一種分法，這種借助于這樣的虛擬“檔板”分配元素的方法稱之為插板法?！净绢}型例題】【例1】 共有10完全相同的球分到 7個(gè)

3、班里，每個(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è)班中?！净绢}型的變形（一）】題型：有n個(gè)相同的元素，要求分到m組中，問(wèn)有多少種不同的分法？解題思路：這種問(wèn)題是允許看些組中分到的元素為“ 0”，也就是組中可以為空的。對(duì)于這樣的題，我們就首先將每組都填上1個(gè)，這樣所要元素總數(shù)就 m個(gè)，問(wèn)題也就是轉(zhuǎn)變成將（n+m個(gè)元素分到 m

4、組，并且每 組至少分到一個(gè)的問(wèn)題，也就可以用插板法來(lái)解決。【例2】有8個(gè)相同的球放到三個(gè)不同的盒子里，共有（）種不同方法A. 35 B. 28 C. 21 D. 45解答：題目允許盒子有空，則需要每個(gè)組添加1個(gè)，則球的總數(shù)為8+3X仁11，此題就有C（ 10, 2） =45（種） 分法了，選項(xiàng)D為正確答案?！净绢}型的變形（二）】題型：有n個(gè)相同的元素，要求分到 m組，要求各組中分到的元素至少某個(gè)確定值S（s 1，且每組的s值可以不同），問(wèn)有多少種不同的分法？解題思路：這種問(wèn)題是要求組中分到的元素不能少某個(gè)確定值s,各組分到的不是至少為一個(gè)了。對(duì)于這樣的題，我們就首先將各組都填滿，即各組就填上

5、對(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:至少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 (種)【例】10個(gè)學(xué)生中，男女生各有 5人，選4人參加數(shù)學(xué)競(jìng)賽。(1 )至少有一名女生的選法種數(shù)為 。

6、(2)A、B兩人中最多只有一人參加的選法種數(shù)為 解法1： io名中選4名代表的選法的種類：Cio4，排除4名參賽全是男生：C54 (排除法)ci。4 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è)部門則要先放8 X 3=24份，還剩下30-24=6份來(lái)放入這三個(gè)部門，且每個(gè)部門至少發(fā)放1份，貝U C ( 5,2 ) =10插 空法插空法就是對(duì)于解決 某幾個(gè)元素要求不相鄰 的問(wèn)題時(shí)，

7、先將其他元素排好，再將所指定的不相鄰的元素插 入它們的間隙或兩端位置。首要特點(diǎn)就是不相鄰。下面舉例說(shuō)明。一. 數(shù)字問(wèn)題【例】 把1, 2, 3, 4, 5組成沒(méi)有重復(fù)數(shù)字 且數(shù)字1, 2不相鄰的五位數(shù)，則所有不同排法有多少種？解析：本題直接解答較為麻煩，因?yàn)榭上葘?, 4, 5三個(gè)元素排定，共有種排法，然后再將1, 2插入四個(gè)空位共有種排法，故由乘法原理得，所有不同的五位數(shù)有二. 節(jié)目單問(wèn)題【例】在一張節(jié)目單中原有六個(gè)節(jié)目，若保持這些節(jié)目的相對(duì)順序不變，再添加進(jìn)去三個(gè)節(jié)目，則所有不 同的添加方法共有多少種？解析：-o - o - o - o - o - o -六個(gè)節(jié)目算上前后共有 七個(gè)空位，那

8、么加上的第一個(gè)節(jié)目則有種方法；此時(shí)有七個(gè)節(jié)目， 再用第二個(gè)節(jié)目去插八個(gè)空位有種方法；此時(shí)有八個(gè)節(jié)目， 用最后一個(gè)節(jié)目去插九個(gè)空位有種方法。由乘法原理得，所有不同的添加方法為：。三. 關(guān)燈問(wè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)燈方法為種。四停車問(wèn)題【例】停車場(chǎng)劃出一排12個(gè)停車位置，今有8輛車需要停放，要求空位置連在一起，不同的停車方法有多少 種？解析：先排好8輛車有種方法，要求空位置連在一起（剩下4個(gè)空位在一起，來(lái)插入 8輛車，有9個(gè)空位可以插）,將空位置插入其中有種方法。所以共有種方法。五座位問(wèn)題【例】3個(gè)人坐在一排8個(gè)椅子上，若 每個(gè)人左右兩邊都有空位 ，則坐法的種類有多少種？解法：先拿出5