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

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

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

3、班里，每個班至少要分到一個球，問有幾種不同分法？解析：我們可以將10個相同的球排成一行，10個球之間出現(xiàn)了 9個空隙，現(xiàn)在我們用 6個檔板”插入這9 個空隙中，就“把10個球隔成有序的7份，每個班級依次按班級序號分到對應(yīng)位置的幾個球 （可能是1個、 2個、3個、4個），這樣，借助于虛擬“檔板”就可以把 10個球分到了 7個班中。【基本題型的變形（一）】題型：有n個相同的元素，要求分到m組中，問有多少種不同的分法？解題思路：這種問題是允許看些組中分到的元素為“ 0”，也就是組中可以為空的。對于這樣的題，我們就首先將每組都填上1個，這樣所要元素總數(shù)就 m個，問題也就是轉(zhuǎn)變成將（n+m個元素分到 m

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

5、對應(yīng)的確定值s那么多個，這樣就滿足了題目中要求的最起碼的條件，之后我們再分剩下的球。這樣這個問題就轉(zhuǎn)變?yōu)樯厦嫖覀兲岬降淖冃危ㄒ唬┑膯栴}了，我們 也就可以用插板法來解決。【例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 (種)【例】10個學生中，男女生各有 5人，選4人參加數(shù)學競賽。(1 )至少有一名女生的選法種數(shù)為 。

6、(2)A、B兩人中最多只有一人參加的選法種數(shù)為 解法1： io名中選4名代表的選法的種類：Cio4，排除4名參賽全是男生：C54 (排除法)ci。4 C54=205解法2 :選1女生時，選2個女生時，選3、4個女生時的選法，分別相加(2010年國考真題)某單位訂閱了 30份學習材料發(fā)放給 3個部門，每個部門至少發(fā)放 9份材料。問一共有 多少種不同的發(fā)放方法？()解析：每個部門先放 8個，后面就至少放一個，三個部門則要先放8 X 3=24份，還剩下30-24=6份來放入這三個部門，且每個部門至少發(fā)放1份，貝U C ( 5,2 ) =10插 空法插空法就是對于解決 某幾個元素要求不相鄰 的問題時，

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

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