分組、分配問題的遞推公式及通項公式

張益明 (上海市奉賢中學(xué) 201499)

分組問題、分配問題是排列組合中非常重要的一類問題.通常該類問題只解決按照特定條件進行分組或分配的問題，比如：將4個不同元素平均分為兩組，共有多少種不同方法？將4個相同元素分為兩組，共有多少種不同方法？n個元素呢？很少有文章涉及這一問題，究其原因是情況較為復(fù)雜.本文將探究這類問題的遞推公式及通項公式．

1 問題提出

(1)不同素分組問題：將n個不同元素分成m組，共有多少種方法？

(2)不同素分配問題：將n個不同元素分配給m個不同對象，共有多少種方法？

(3)同素分組問題：將n個相同元素分成m組，共有多少種方法？

(4)同素分配問題：將n個相同元素分配給m個不同對象，共有多少種方法？

分析若上述問題中的n,m比較小，則可以利用簡單的排列組合知識加以解決.例如引文中提出的情況：n=4,m=2．

a1,a2-a3,a4；a1,a3-a2,a4；a1,a4-a2,a3；

a1-a2,a3,a4；a2-a1,a3,a4；a3-a1,a2,a4；a4-a1,a2,a3．

(2)因為n個元素各不相同，故只需將(1)中的分組進行排列即可，則方法數(shù)為7·2!=14種．

(3)將四個相同元素記為a，a，a，a，則分組方法僅有2種，即a-aaa，aa-aa．

(4)分配方法數(shù)有3種，即a-aaa，aaa-a，aa-aa．

但是若將問題變?yōu)橐话愕淖帜竛,m，則問題變得異常復(fù)雜，本文將繼續(xù)探尋此類問題的遞推公式或通項公式.

2 問題解決

為了表達方便，將上述四個問題的答案分別用f(n,m),g(n,m),h(n,m),r(n,m)來表示.

2.1 問題(1)(2)的解決

下面用數(shù)學(xué)歸納法證明(*)式：

①n=2,m=2時，(*)式顯然成立；

②假設(shè)n

即當(dāng)n=k,m=s時，(*)式也成立．綜上可知(*)式對于一切滿足n≥m的自然數(shù)都成立.

2.2 問題(3)(4)的解決

第一步：給m組每組1個元素；

第二步：將剩余的n-m個元素分為1組、2組、…、min{n-m,m}組(每組至少一個元素)，當(dāng)n<2m時，h(n,m)=h(n-m,1)+h(n-m,2)+…+h(n-m,n-m)．

又由n<2m，得n+1<2(m+1)，則h(n+1,m+1)=h(n-m,1)+h(n-m,2)+…+h(n-m,n-m)，兩式相減有h(n,m)=h(n+1,m+1)(n<2m)． ①

當(dāng)n≥2m時，h(n,m)=h(n-m,1)+h(n-m,2)+…+h(n-m,m)，又由n≥2m，得n-1≥2(m-1)，則h(n-1,m-1)=h(n-m,1)+h(n-m,2)+…+h(n-m,m-1)，兩式相減有h(n,m)=h(n-1,m-1)+h(n-m,m)(n≥2m)． ②

則①②即為同素分組問題的遞推公式.

由①式得如下結(jié)論：

h(3,2)=h(4,3)=…=h(m+1,m)=1,m≥2；

h(5,3)=h(6,4)=…=h(m+2,m)=2,m≥3；

h(7,4)=h(8,5)=…=h(m+3,m)=3,m≥4；

h(9,5)=h(10,6)=…=h(m+4,m)=5,m≥5；

……

由②式有如下結(jié)論：

依此類推，可以得到h(n,4),h(n,5),…的通項公式，但是能否找到一個統(tǒng)一的式子還有待進一步研究.