排列組合--插板法、插空法、捆綁法[優(yōu)質嚴選]

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

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

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

4、成將（n+m）個元素分到m組，并且每組至少分到一個的問題，也就可以用插板法來解決。 【例2】有8個相同的球放到三個不同的盒子里，共有（ ）種不同方法.A35 B28 C21 D45解答：題目允許盒子有空，則需要每個組添加1個，則球的總數為8+31=11，此題就有C（10，2）=45（種）分法了，選項D為正確答案?！净绢}型的變形（二）】題型：有n個相同的元素，要求分到m組，要求各組中分到的元素至少某個確定值S（s1，且每組的s值可以不同），問有多少種不同的分法？ 解題思路：這種問題是要求組中分到的元素不能少某個確定值s，各組分到的不是至少為一個了。對于這樣的題，我們就首先將各組都填滿，即各組就

5、填上對應的確定值s那么多個，這樣就滿足了題目中要求的最起碼的條件，之后我們再分剩下的球。這樣這個問題就轉變?yōu)樯厦嫖覀兲岬降淖冃危ㄒ唬┑膯栴}了，我們也就可以用插板法來解決?！纠?】15個相同的球放入編號為1、2、3的盒子內，盒內球數不少于編號數，有幾種不同的放法？解析：編號1：至少1個，符合要求。編號2：至少2個：需預先添加1個球，則總數-1編號3：至少3個，需預先添加2個，才能滿足條件，后面添加一個，則總數-2則球總數15-1-2=12個放進3個盒子里所以C（11，2）=55（種）【例】10 個學生中，男女生各有5 人，選4 人參加數學競賽。（1）至少有一名女生的選法種數為_。（2）A、B 兩

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

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

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