隔板法的三種題型公式

理解隔板法#

隔板法就是在 n 個(gè)元素間的 n?1 個(gè)空插入 k?1 個(gè)板子，把 n 個(gè)元素分成 k 組的方法。方案數(shù)為 Ck?1n?1。

應(yīng)用隔板法必須滿足的 3 個(gè)條件：

n 個(gè)元素是相同的

k 個(gè)組是互異的

每組至少分得一個(gè)元素

例如，把 10 個(gè)相同的球放入 3 個(gè)不同的箱子，每個(gè)箱子至少一個(gè)，有 C29 種情況。

隔板法應(yīng)用#

普通隔板法#

例 1. 求方程 x+y+z=10 的正整數(shù)解的個(gè)數(shù)。

分析：將 10 個(gè)求排成一排，球與球之間形成 9 個(gè)空隙，將兩個(gè)隔板插入這些空隙中（每空至多插一塊隔板），規(guī)定由隔板分成的左、中、右三部分的球數(shù)分別為 x、y、z 的值，則隔板法與解的個(gè)數(shù)之間建立了一一對(duì)應(yīng)關(guān)系，故解的個(gè)數(shù)為 Cm?1n?1=C29=36。

增減元素隔板法#

例 2. 求方程 x+y+z=10 的非負(fù)整數(shù)解的個(gè)數(shù)。

分析：注意到 x、y、z 可以為零，故例 1 解法中的限定「每空至多插一塊隔板」就不成立了，怎么辦呢？只要預(yù)先給 x、y、z 各添加一個(gè)球，這樣原問題就轉(zhuǎn)化為求 (x+1)+(y+1)+(z+1)=13 的解的個(gè)數(shù)了，則問題就等價(jià)于把 13 個(gè)相同小球放入 3 個(gè)不同箱子，每個(gè)箱子至少一個(gè)，方案數(shù)為 Cm?1n+m?1=C212=66。

例 3. 把 10 個(gè)相同的小球放到 3 個(gè)不同的箱子，第一個(gè)箱子至少 1 個(gè)，第二個(gè)箱子至少 3 個(gè)，第 3 個(gè)箱子可以為空，有幾種情況？

我們可以在第二個(gè)箱子先放入 10 個(gè)小球中的 2 個(gè)，小球剩 8 個(gè)放 3 個(gè)箱子，然后在第三個(gè)箱子放入 8 個(gè)小球之外的 1 個(gè)小球（即補(bǔ)充了一個(gè)球），則問題轉(zhuǎn)化為把 9 個(gè)相同小球放 3 不同箱子，每箱至少 1 個(gè)，幾種方法？C28=28。

也可轉(zhuǎn)化為例 2 的形式，即求方程 x+y+z=10 (x≥1,y≥3,z≥0) 的整數(shù)解的個(gè)數(shù)。構(gòu)造新變量 a=y?2,b=z+1，現(xiàn)在 x,a,b 都 ≥1 了，因此可以運(yùn)用隔板法。原方程化為 x+a+b=10?2+1=9，隔板法求得方案數(shù) C2?19?1=C28=28。

例 4. 將 20 個(gè)相同的小球放入編號(hào)分別為 1，2，3，4 的四個(gè)盒子中，要求每個(gè)盒子中的球數(shù)不少于它的編號(hào)數(shù)，求放法總數(shù)。

分析：先在編號(hào) 1,2,3,4 的四個(gè)盒子內(nèi)分別放 0,1,2,3 個(gè)球，剩下 14 個(gè)球，再把剩下的球分成 4 組，每組至少 1 個(gè)，由例 1 知方法有 C313=286（種）。

添板插板法（添加盒子法）#

例 5. 有一類自然數(shù)，從左往右的第三個(gè)數(shù)字開始，每個(gè)數(shù)字都恰好是它左邊兩個(gè)數(shù)字之和，直至不能再寫為止，如 1459，58，21369 等。這類數(shù)共有幾個(gè)？

分析：因?yàn)榍?2 位唯一確定了整個(gè)序列，只要求出前兩位的所有情況即可，設(shè)前兩位為 a 和 b

顯然 a+b≤9，且 a 不為 0，但 b 可以為 0（例如 202246）。這里惱人的地方在于這個(gè)不等號(hào)，a+b 的總數(shù)是不確定的。怎么辦？

這里可以構(gòu)造第三個(gè)盒子 c 來放剩下的球，即 a+b+c=9 (a≥1,b≥0,c≥0)。老套路，轉(zhuǎn)化為 a+(b+1)+(c+1)=11，使得???a≥1(b+1)≥1(c+1)≥1

題目等價(jià)于，11 個(gè)球放入 3 個(gè)不同的箱子，每個(gè)箱子至少放一個(gè)，C210。

選板法#

例 6. 有 10 粒糖，如果每天至少吃一粒（多不限），吃完為止，求有多少種不同吃法？

分析：o_o_o_o_o_o_o_o_o_o（o 代表 10 個(gè)糖，_ 代表 9 個(gè)空）

所以 10 塊糖，9 個(gè)空，插入 9 塊隔板，每個(gè)板都可以選擇放或不放，相鄰兩板間的糖一天吃掉，這樣共有 29=512 啦。

分類插板法#

例 7. 小梅有 15 塊糖，如果每天至少吃 3 塊，吃完為止，那么共有多少種不同的吃法？

分析：

此問題不能用插板法的原因在于沒有規(guī)定一定要吃幾天，因此我們需要對(duì)吃的天數(shù)進(jìn)行分類討論。顯然最多吃 5 天，最少吃 1 天。

吃 1 天或是 5 天，各一種吃法,一共 2 種情況

吃 2 天，每天預(yù)先吃 2 塊，即問 11 塊糖，每天至少吃 1 塊，吃 2 天，幾種情況？ C110=10

吃 3 天，每天預(yù)先吃 2 塊，即問 9 塊糖，每天至少 1 塊，吃 3 天？C28=28

吃 4 天，每天預(yù)先吃 2 塊，即問 7 塊糖，每天至少 1 塊，吃 4 天？C36=20

所以一共是 2+10+28+20=60 種。

*逐步插板法#

實(shí)際上是逐步插空法，屬于插空而不是插板法。

例 8. 在一張節(jié)目單中原有 6 個(gè)節(jié)目，若保持這些節(jié)目相對(duì)次序不變，再添加 3 個(gè)節(jié)目，共有幾種情況？

分析：可以用一個(gè)節(jié)目去插 7 個(gè)空位，再用第二個(gè)節(jié)目去插 8 個(gè)空位，用最后個(gè)節(jié)目去插 9 個(gè)空位，所以一共是 C17C18C19=504 種。

綜合例題#

有 n 個(gè)不同的盒子，在每個(gè)盒子中放一些球（可以不放），使得總球數(shù)不大于 m，求方案數(shù)。

分析：總球數(shù) ≤m，所以我們可以增加一個(gè)盒子放 m 個(gè)球中沒被選中的球。所以題目等價(jià)于 m 個(gè)球放入 n+1 個(gè)盒子中，盒子有里球數(shù)可以為 0，添元素插板法，每一個(gè)盒子都增加一個(gè)球，即 m+n+1 個(gè)球放入 n+1 個(gè)盒子，Cnm+n 為答案。