隔板法的三種題型公式

理解隔板法#

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

應用隔板法必須滿足的 3 個條件：

n 個元素是相同的

k 個組是互異的

每組至少分得一個元素

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

隔板法應用#

普通隔板法#

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

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

增減元素隔板法#

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

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

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

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

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

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

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

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

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

分析：因為前 2 位唯一確定了整個序列，只要求出前兩位的所有情況即可，設前兩位為 a 和 b

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

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

題目等價于，11 個球放入 3 個不同的箱子，每個箱子至少放一個，C210。

選板法#

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

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

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

分類插板法#

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

分析：

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

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

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

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

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

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

*逐步插板法#

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

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

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

綜合例題#

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

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