“隔板法”巧解排列組合題

羅忠菊

摘 要：“隔板法”適用于相同元素的分配問題，如投球進盒、名額或指標(biāo)的分配、部分不定方程的整數(shù)解的組數(shù)等，解決時通常設(shè)計一個問題情景，構(gòu)造一個隔板模型。將復(fù)雜的問題簡單化，抽象的問題具體化，從而實現(xiàn)解題的目的。

關(guān)鍵詞：隔板；空檔；問題情景；構(gòu)造；模型；正整數(shù)解；排列組合

“隔板法”是解決組合問題中關(guān)于若干個相同元素的分組問題的一種常用方法，用這種方法解決此類問題，過程簡潔明了，富有創(chuàng)意性和趣味性。這類問題的類型就是把n（n≥1）個相同的元素分配到k（1≤k≤n）個不同的組，使得每組中都至少有一個元素，求一共有多少種不同的分法的問題。在這n個相同元素中找“空檔”（不含兩端），在n-1個“空檔”中插入k-1個隔板，把n個元素分成k“堆”，把“堆”看作排列組合中的元素，這樣問題就用Ck-1n-1來解決。直接應(yīng)用“隔板法”必須滿足三個條件：

①這n個元素必須相同；

②所分成的每一組至少分得一個元素；

③分成的組別彼此相異。

“隔板法”適用于相同元素的分配問題，如投球進盒、名額或指標(biāo)的分配、部分不定方程的整數(shù)解的組數(shù)等，解決時通常設(shè)計一個問題情景，構(gòu)造一個隔板模型。將復(fù)雜的問題簡單化，抽象的問題具體化，從而實現(xiàn)解題的目的。

【例1】 高二年級8個班級協(xié)商組成年級籃球隊，共需10名隊員，每個班級至少要出一名，有多少種不同的組成方式？

【分析】 將10名隊員理解成10個相同的球，排成一列，共形成9個空檔，設(shè)想有7塊隔板，將排成一列的10個球隔成8段，注意：任意兩塊隔板不能相鄰，只能插入空檔，在9個空檔中插入7塊隔板，故有C79=36（種）。這個問題也可轉(zhuǎn)化為求不定方程x1+x2+…+x8=10，有多少組不同的正整數(shù)解。

【例2】 不定方程x+y+z+w=10有多少組正整數(shù)解？

【分析】 我們設(shè)想有10個相同的球排成一列，共形成9個空檔，可以理解為有3塊隔板，將排成一列的10個球隔成4段，注意：任意兩塊隔板不能相鄰，只能插入空檔，在9個空檔中插入3塊隔板，故有C39=84組正整數(shù)解。

對某些不符合上述“隔板法”條件的問題可以通過一些技巧轉(zhuǎn)化為符合條件的隔板問題。

技巧一：添加球數(shù)用“隔板法”

【例3】 不定方程x+y+z+w=10有多少組非負整數(shù)解？

【分析】 注意到x、y、z、w可以為0，故例2解法中的限定“每個空檔至多插入一塊隔板”就不成立了，怎么辦呢？只要添加4個球，給x、y、z、w各一個球。這樣原問題就轉(zhuǎn)化為求不定方程x+y+z+w=14的正整數(shù)解的組數(shù)，故方程解的組數(shù)為C313=286。

【評述】 本例通過添加球數(shù)，將問題轉(zhuǎn)化為例2中的典型“隔板法”問題。

【例4】 將9個相同的球分給3個人，允許有人不取，但必須分完，有多少種分法？

問題轉(zhuǎn)化為：9個相同的球分給編號為1，2，3的盒子，允許有盒子為空，但必須分完，有多少種分法？

【解法一】 將9個球排成一列，包括兩端一共有10個空檔，因為這里允許有盒子為空，就是隔板可以“擠進”同一個空檔里，所以不能以空檔計算。將2個隔板插入這些空檔中，則每一種隔板位置對應(yīng)一種分法。這里球和隔板共有11個，則有C211=55種分法。

【解法二】 添加3個球，給3個人每人一個，問題轉(zhuǎn)化為：12個相同的球分給3個人，每人至少分一個球，且必須分完，有多少種分法？也就是將12個球排成一列，有11個空檔，插入2塊隔板分成三段，則有C211=55種分法。

【評述】 這個問題的解法是典型的玻色─愛因斯坦（BoseEinstein）統(tǒng)計模型：要將n（n≥1）個相同的球放入k（1≤k≤n）個不同的盒子，每盒所放球數(shù)不限，有多少種不同放法？用組合公式Ck-1n+k-1來解決。

技巧二：減少球數(shù)用“隔板法”

【例5】 將9個相同的球放入編號為1，2，3的盒子中，要求每個盒子中的球數(shù)不少于它的編號數(shù)，有多少種放法？

【分析】 先在編號1，2，3的盒子內(nèi)分別放入0，1，2個球，剩下6個相同的球，問題轉(zhuǎn)化為：將6個相同的球放入編號為1，2，3的盒子里，每個盒子至少有一個球的問題。

剩下6個相同的球排成一列，共形成5個空檔，可以理解為有2塊隔板，將排成一列的6個球隔成3段，每段至少有1個，則有C25=10（種）。

【評述】 本例通過減少球數(shù)，使得每個盒子中至少放入一個球，將問題轉(zhuǎn)化為典型“隔板法”問題。

以上是我從教學(xué)實際中列舉的幾個用“隔板法”解決的排列組合題，解題時通常設(shè)計一個問題情景，構(gòu)造一個隔板模型，套用公式Ck-1n-1或Ck-1n+k-1，使解題過程簡潔明了，富有創(chuàng)意性和趣味性。

參考文獻：

[1]徐幫利.巧用隔板法解排列組合題[J].數(shù)學(xué)愛好者（高考版），2007，（12）.

[2]程小芳.“隔板”法與一類排列組合題[J].中學(xué)數(shù)學(xué)教學(xué)，2006，（04）.