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

排列組合問(wèn)題——插板法(分組)、插空法（不相鄰）、捆綁法（相鄰）插板法（m為空的數(shù)量）【基本題型】

有n個(gè)相同的元素，要求分到不同的m組中，且每組至少有一個(gè)元素，問(wèn)有多少種分法？

圖中“”表示相同的名額，“”表示名額間形成的空隙，設(shè)想在這幾個(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份即可,共有種不同方法。

注意：這樣對(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è)班里，每個(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組，并且每組至少分到一個(gè)的問(wèn)題，也就可以用插板法來(lái)解決。

【例2】有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值可以不同），問(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)解決。

【例3】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（種）

捆綁法