“隔板模型”在排列組合中的應(yīng)用技巧

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

題目：（1）現(xiàn)有10個(gè)優(yōu)秀生名額擬分配給高三6個(gè)班，每班至少1個(gè)名額，試問共有多少種不同的分配方案。

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

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

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

解法如下：

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

0000000000

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

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

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

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

變題：

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

此題貌似與排列組合無(wú)關(guān)，但應(yīng)用“隔板模型”該題即可轉(zhuǎn)化為組合問題輕易解決。

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

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

分析：此題事實(shí)上可以轉(zhuǎn)化為“10個(gè)名額分配給3個(gè)班，允許部分班級(jí)沒有名額”的問題。為此，我們先看下題：

②現(xiàn)有10個(gè)優(yōu)秀生名額擬分配給高三6個(gè)班，如果允許部分班級(jí)沒有名額，試問共有多少種不同的分配方案。

分析：本題允許部分班級(jí)沒有名額，要?jiǎng)?chuàng)設(shè)“隔板”情境，必須每班至少1個(gè)名額。為此，我們可以先給每個(gè)班1個(gè)“虛”的名額，這樣，可以將原題轉(zhuǎn)化為：“現(xiàn)有16個(gè)優(yōu)秀生名額擬分配給高三6個(gè)班，每班至少1個(gè)名額，試問共有多少中不同的分配方案?！?/p>

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

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

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

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

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

題目：（2）現(xiàn)有25個(gè)優(yōu)秀生名額擬分配給高三6個(gè)班，每班至少3個(gè)名額，試問共有多少種不同的分配方案。

要?jiǎng)?chuàng)設(shè)“隔板”情境，即每班至少1個(gè)名額。為此，可先給每班分配2個(gè)名額，原題即可轉(zhuǎn)化為“現(xiàn)有13個(gè)優(yōu)秀生名額擬分配給高三6個(gè)班，每班至少1個(gè)名額”的問題。從而本題有c =792種不同的分配方案。

創(chuàng)設(shè)“隔板模型”的情境，即要求每個(gè)個(gè)體至少分配到1個(gè)元素，為此：

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

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

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

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

注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文?！?/p>