分配問題的幾種類型及其解法

在排列組合中有一種分配問題，形式多樣，掌握這些問題的解法，一要注意問題間的區別，進行正確分類;二要注重同類問題解法之間的聯系，能夠觸類旁通。

一、正確識別分配問題的類型

總體而言，分配問題有兩種類型:相同元素的分配問題與不同元素的分配問題。相同元素的分配是組合問題，不同元素的分配是組合排列綜合問題，正確識別類型是解決分配問題的首要任務。

例1:將6個競賽名額分給4個班級，每個班至少1個，則不同的分配方案共有多少種?

例2:將4名教師分配到3所中學任教，每所中學至少1名教師，則不同的分配方案共有多少種?

名額之間是無區別的，所以例1屬相同元素的分配問題;教師之間是有區別的，所以例2屬不同元素的分配問題。

二、相同元素分配問題的基本模型與解法

基本模型:將n個相同元素分裝到m(m≤n)個不同盒中，每盒至少一個球，有多少種不同的分配方案?

分析與解:將n個相同元素視作排成一排的n個相同小球，每兩個小球之間有一個間隔，共有n-1個間隔。要把這n個小球分開成m段(每段至少一個球)，只需從n-1個間隔中任意選擇m-1個間隔放進隔板，從而共有C種不同的分配方案。

根據上述思路，例1共有C=10種不同的分配方案。

下面幾種相同元素的分配問題都可轉化為基本模型來解。

例3:將6個相同小球分到4個不同盒中，每盒可空，則不同的分配方案共有多少種?

解:該問題等價于“將10個相同小球分到4個不同盒中，每盒至少1個”，因此不同的分配方案共有C種。

例4:將20個相同小球分到3個不同盒中，每盒至少4個，則不同的分配方案共有多少種?

解:先往3個盒中分別放入3個小球，再將剩下的11個小球分到3個盒中，每盒至少1個，共有C種不同的分配方案。

例5:將20個相同小球分到編號為1，2，3的三個盒中，要求每個盒子中的球數不小于它的編號數，則不同的放法有多少種?

解:先在編號為1，2，3的三個盒中依次放入0，1，2個球，再將剩下的17個小球分到3個盒中，每盒至少1個，共有C種不同的放法。

三、不同元素分配問題的幾種類型與聯系

1.將個不同的球分裝到n-1個不同盒中，每盒至少一個球，有多少種裝法?

分析與解:先分類，滿足題意的裝法只有一類，有一個盒子中裝2個球，其余每個盒子各裝一個球。再分步，第一步將n個不同的球按題意分為n-1組，有C種組合;第二步將這n-1個組分到n-1個不同盒中，每個盒子各一組，有P種裝法;根據乘法原理，共有C×P種不同的裝法。

根據上述思路，例2共有C×P=36種不同的裝法。

“將個不同的球分裝到n個不同盒中，恰好有一個空盒”也可以轉化為類型Ⅰ來解。

例6:將四個不同的小球分到編號為1，2，3，4的四個盒中，則恰好有一個空盒的放法種數為多少?

解:第一步選定一個盒子為空盒，有C=4種選法，第二步將四個不同的小球分到三個盒中，每盒至少一個，問題就轉化為例2，有C×P=36種放法，根據乘法原理共有144種不同放法。

2.將n個不同的球分裝到m(m

類型Ⅱ的一般解法和類型Ⅰ一樣，可以視n，m的具體值先分類再分步，現以一個例子說明。

例7:將4名教師分配到2所中學任教，每所中學至少1名教師，則不同的分配方案共有多少種?

先分類再分別進行分步計數。根據題意，將問題分為“一所中學3名，一所中學1名”與“2所中學各2名”兩類。對第一類，第一步分組有C種組合，第二步將這兩個組分到2所中學，有P種不同分法，由乘法原理，第一類有C×P=8種不同分配方案;對第二類，第一步先將4名教師平均分為兩組，注意到平均分組必須剔除兩步的順序性，故有種組合，第二步將這兩個組分到2所中學，有種不同分法，由乘法原理，第二類有6種不同分配方案。根據分類計數原理，總共有14種不同的分配方案。

綜上所述，盡管分配問題形式多樣，但題型都可歸為兩類:相同元素的分配問題與不同元素的分配問題，而且解法上也可進行類比:相同元素的分配問題都可以轉化為基本模型來解，不同元素的分配問題一般都采用先分類再分步的方法。