基本介紹
- 中文名：插空法
- 外文名：Interpolation method
- 學科：數學
- 套用：解排列組合中的不鄰問題
- 優點：思路清晰、簡便易懂
- 其他方法：插板法、捆綁法
方法簡介,插板法,捆綁法,排列組合問題,
方法簡介
插空法就是對於解決 某幾個元素要求不相鄰 的問題時，先將其他元素排好，再將所指定的不相鄰的元素插入它們的間隙或兩端位置。首要特點就是不相鄰。下面舉例說明。
（1）例1：把1，2，3，4，5組成沒有重複數字且數字 1，2不相鄰的五位數，則所有不同排法有多少種？
解析：本題直接解答較為麻煩，因為可先將 3，4，5三個元素排定，共有
種排法，然後再將 1，2插入四個空位共有
種排法，故由乘法原理得，所有不同的五位數有
種。
（2）例2：在一張節目單中原有六個節目，若保持這些節目的相對順序不變，再添加進去三個節目，則所有不同的添加方法共有多少種？
解析： -o - o - o - o - o - o - ，即六個節目算上前後共有七個空位，那么加上的第一個節目則有
種方法； 此時有七個節目， 再用第二個節目去插八個空位有
種方法； 此時有八個節目， 用最後一個節目去插九個空位有
種方法。由乘法原理得，所有不同的添加方法為：
種。
插板法
基本題型
基本題型為：n個相同元素，不同個m組，每組至少有一個元素；則只需在 n 個元素的n-1 個間隙中放置 m-1 塊隔板把它隔成 m 份，求共有多少種不同方法？
其解題思路為：將 n 個相同的元素排成一行， n 個元素之間出現了（ n-1 ）個空檔，現在我們用（ m-1 ）個 “檔板 ”插入（ n-1 ）個空檔中，就把 n 個元素隔成有序的 m 份，每個組依次按組序號分到對應位置的幾個元素（可能是 1 個、2 個、 3 個、 4 個、 ….），這樣不同的插入辦法就對應著 n 個相同的元素分到 m 組的一種分法，這種藉助於這樣的虛擬 “檔板 ”分配元素的方法稱之為插板法。
例題：共有 10 完全相同的球分到 7 個班裡，每個班至少要分到一個球，問有幾種不同分法？
解析：我們可以將 10 個相同的球排成一行， 10 個球之間出現了 9 個空隙，現在我們用 6 個檔板 ”插入這 9個空隙中，就 “把 10 個球隔成有序的 7 份，每個班級依次按班級序號分到對應位置的幾個球（可能是 1 個、2 個、 3 個、 4 個），這樣，藉助於虛擬 “檔板 ”就可以把 10 個球分到了 7 個班中。
基本題型的變形
（1）變形1：有 n 個相同的元素，要求分到 m 組中，問有多少種不同的分法？
解題思路：這種問題是允許有些組中分到的元素為 “0”，也就是組中可以為空的。對於這樣的題，我們就首先將每組都填上 1 個，這樣所要元素總數就 m 個，問題也就是轉變成將（ n+m ）個元素分到 m 組，並且每組至少分到一個的問題，也就可以用插板法來解決。
例題：有 8 個相同的球放到三個不同的盒子裡，共有（ ）種不同方法 。
解答：題目允許盒子有空，則需要每個組添加 1 個，則球的總數為 8+3 ×1=11，此題就有 C（10 ，2） =45（種）分法了。
（2）變形2：有 n 個相同的元素，要求分到 m 組，要求各組中分到的元素至少某個確定值 S（ s>1，且每組的 s值可以不同） ，問有多少種不同的分法？
解題思路： 這種問題是要求組中分到的元素不能少某個確定值 s，各組分到的不是至少為一個了。 對於這樣的題，我們就首先將各組都填滿，即各組就填上對應的確定值 s 那么多個，這樣就滿足了題目中要求的最起碼的條件，之後我們再分剩下的球。這樣這個問題就轉變為上面提到的變形1的問題了，也就可以用插板法來解決。
例題：15 個相同的球放入編號為 1、2、 3 的盒子內，盒內球數不少於編號數，有幾種不同的放法？
解析：編號 1：至少 1 個，符合要求；
編號 2：至少 2 個：需預先添加 1 個球，則總數 -1 ；
編號 3：至少 3 個，需預先添加 2 個，才能滿足條件，後面添加一個，則總數 -2 ；
則球總數 15-1-2=12 個放進 3 個盒子裡，所以 C（11，2）=55 （種）。
捆綁法
所謂捆綁法，指在解決對於某幾個元素要求相鄰問題時，先整體考慮，將相鄰元素視作一個整體參與排序，然後再單獨考慮這個整體內部各元素間順序。注意：其首要特點是相鄰，其次捆綁法一般都套用在不同物體的排序問題中。
例題：6個不同的球放到5個不同的盒子中，要求每個盒子至少放一個球，一共有多少種方法?
解答：根據題目要求，則其中一個盒子必須得放 2 個，其他每個盒子放 1 個球，所以從 6 個球中挑出 2 個球看成一個整體，則有
，這個整體和剩下 4 個球放入 5 個盒子裡，則有
。方法是
。
排列組合問題
排列組合問題從解法看，大致有以下幾種：
(1)有附加條件的排列組合問題，大多需要分類討論的方法，注意分類時應不重不漏；
(2)排列與組合的混合型問題，用分類加法或分步乘法計數原理解決；
(3)元素相鄰，可以看作是一個整體的方法；
(4)元素不相鄰，可以利用插空法；
(5)間接法，把不符合條件的排列與組合剔除掉；
(6)窮舉法，把不符合條件的所有排列或組合一一寫出來。
