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

羅忠菊

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

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

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

①這n個(gè)元素必須相同；

②所分成的每一組至少分得一個(gè)元素；

③分成的組別彼此相異。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

參考文獻(xiàn)：

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

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