“隔板模型”在排列組合中的應用技巧

大家都知道，當今社會，數學在金融、經濟、工程技術以及自然科學中有著廣泛的應用，它的重要性已逐漸成為人們的共識。用數學方法解決實際問題，就是要求從實際錯綜復雜的關系中找出其內在聯系和規律，然后用數學語言、圖形語言、符號語言和公式把它表示出來。這種把實際問題進行簡化并歸結為數學問題進行求解的過程就是建立數學模型，簡稱“建模”。如有關方程的正整數解，非負整數解以及在線性規劃中的有關整數解問題，排列組合中的“將相同的元素分配給不同的人”這樣的問題，我們都可以通過建立“隔板模型”來解決這類問題。本文中，筆者主要就以下幾個問題舉例說明如下：

題目：（1）現有10個優秀生名額擬分配給高三6個班，每班至少1個名額，試問共有多少種不同的分配方案。

初做本題，有學生用如下方法來解這道題，解法如下：

解：10個優秀生名額擬分配給高三6個班，每班至少1個名額，可以先給每個班1個名額，故要處理的問題是將余下的4個名額如何分給6個班，我們可以分給1個班，最多可以分給4個班。分給1個班，只要選班級即可；分給2個班，可先選班級，有種選法，再將4個名額分2份，有3種分法。依此類推，本題共有

注：名額沒有區別，屬于相同的元素分配給不同的人的問題，故可建立“隔板模型”。

解法如下：

解：用一個“0 ”表示1個名額，將10個名額排列如下：

0000000000

這10個名額中間產生9個“空”，從這9個“空”中選出5個插入5塊“隔板”，事先約定：第1塊“隔板”前的名額分給1班，第1塊“隔板”與第2塊“隔板”之間的名額給2班，依此類推，第5塊“隔板”后的名額給6班，比如在下圖中，1班1個，2班2個，3班3個，4班1個，5班2個，6班1個。

我們知道，從9個“空”任取5個插入5塊“隔板”，共c =126有種方法，而每一種插法都對應著一種名額分配方案，所以一共有126種不同的分配方案。

說明：（1）“事先約定”是必須的，沒有事先約定，名額就無法分配。

（2） “至少1個名額”是利用“隔板法”處理有關名額分配問題的特定情境。

變題：

① 求方程x + y + z = 10的正整數解的組數。

此題貌似與排列組合無關，但應用“隔板模型”該題即可轉化為組合問題輕易解決。

仔細想來，此題事實上與“10個名額分配給3個班，每班至少1個名額的問題”一回事。至此，可建立“隔板模型”。故本題有c =36組解。

問題：若本題改為：求方程x + y + z = 10的非負整數解的組數。

分析：此題事實上可以轉化為“10個名額分配給3個班，允許部分班級沒有名額”的問題。為此，我們先看下題：

②現有10個優秀生名額擬分配給高三6個班，如果允許部分班級沒有名額，試問共有多少種不同的分配方案。

分析：本題允許部分班級沒有名額，要創設“隔板”情境，必須每班至少1個名額。為此，我們可以先給每個班1個“虛”的名額，這樣，可以將原題轉化為：“現有16個優秀生名額擬分配給高三6個班，每班至少1個名額，試問共有多少中不同的分配方案。”

解：仿照上例，本題共有c =3003種不同的分配方案。比如在下圖中，1班1個，2班沒有，3班2個，4班3個，5班4個，6班沒有。注：每個班都有1個“虛”的名額，應該去掉。

0 0 ｜ 0 ｜ 0 0 0 ｜ 0 0 0 0 ｜ 0 0 0 0 0 ｜ 0

由此，方程x + y + z = 10的非負整數解的組數為c =66組。

注：本題也可以另解如下：

10個優秀生名額擬分配給高三6個班，如果允許部分班級沒有名額，那么最少可以分配給1個班，最多可以分配給6個班，共有6種可能。若分給1個班，有c ×1種可能；若分給2個班，可先選班級，有c 種選法，再將10個名額分兩份。此時再次創設“隔板情境”，利用“隔板模型”，故有c 種分法，這樣有c ×c 種分配方法。依此類推，本題可列式如下：

題目：（2）現有25個優秀生名額擬分配給高三6個班，每班至少3個名額，試問共有多少種不同的分配方案。

要創設“隔板”情境，即每班至少1個名額。為此，可先給每班分配2個名額，原題即可轉化為“現有13個優秀生名額擬分配給高三6個班，每班至少1個名額”的問題。從而本題有c =792種不同的分配方案。

創設“隔板模型”的情境，即要求每個個體至少分配到1個元素，為此：

（1）“事先約定”是必須的，沒有事先約定，元素就無法分配。

（2）“至少1個元素”是利用“隔板法”處理有關元素分配問題的特定情境。

（3）一般的，n個元素分配到m(m≤n；m，n∈N )個個體，每個個體至少1個元素，共有c 種不同的分配方案。

（4）一般的，n個元素分配到m(m≤n；m，n∈N )個個體，允許有的個體沒有分配到元素，共有c 種不同的分配方案。

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。”