分堆問題的一種一般解法

辛智文

將n個(gè)不同元素分成m堆（每堆至少一個(gè)，每堆個(gè)數(shù)可以不相等），一共有多少種不同的分法.這樣的問題通常稱為分堆問題.當(dāng)n，m較小時(shí)這類問題解決起來并不困難，但要給出一般的結(jié)論卻不容易.

為了敘述方便，我們先來探討這樣的問題：將n個(gè)人分配到m個(gè)單位（每個(gè)單位至少一人，各單位人數(shù)可以不相等.n≥m），一共有多少種不同的分法.顯然，這一問題的結(jié)果除以m！就是上面分堆問題的結(jié)果.

設(shè)將n個(gè)人分配到m個(gè)單位（每個(gè)單位至少一人，各單位人數(shù)可以不相等.n≥m），一共有f（n，m）種不同的分法.易得：

f（n，1）=1；

當(dāng)m=2時(shí)，n個(gè)人中的每個(gè)人都有2種分配方案，總共有2×2×…×2=2n種方法，減去只到了其中一個(gè)單位的2種方法，就有

f（n，2）=2n-C12；

當(dāng)m=3時(shí)，n個(gè)人中的每個(gè)人都有3種分配方案，總共有3×3×…×3=3n種方法，減去只到了其中2個(gè)單位的C23（2n-2）種方法，還有只到了其中1個(gè)單位的3種方法，就有

f（n，3）=3n-C23（2n-2）-C13=3n-C23×2n+C13；

當(dāng)m=4時(shí)，n個(gè)人中的每個(gè)人都有4種分配方案，總共有4×4×…×4=4n種方法，減去只到了其中3個(gè)單位的C34（3n-C23×2n+C13）種方法，只到了其中2個(gè)單位的C24（2n-2）種方法，還有只到了其中1個(gè)單位的4種方法，就有

f（n，4）=4n-C34[3n-C23（2n-2）-C13]-C24（2n-2）-C14=4n-C34×3n+C24×2n-C14……

我們猜想：

f（n，m）=mn-Cm-1m×（m-1）n+Cm-2m×（m-2）n-Cm-3m×（m-3）n+…+（-1）m-1C1m

下面用第二數(shù)學(xué)歸納法加以證明：

①當(dāng)m=1時(shí)，左=右=1，結(jié)論顯然成立.

②假設(shè)m≤k時(shí)結(jié)論都成立，即

這表明當(dāng)m=k+1時(shí)結(jié)論成立，由歸納原理知原結(jié)論成立.

就是說，將n個(gè)不同元素分成m堆（每堆至少一個(gè)，每堆個(gè)數(shù)可以不相等，m≤n），一共有[mn-Cm-1m×（m-1）n+Cm-2m×（m-2）n-Cm-3m×（m-3）n+…+（-1）m-1C1m]÷m！種不同的分法.

參考文獻(xiàn)

[1]嚴(yán)明軍.分堆問題[J].中學(xué)數(shù)學(xué)雜志（高中版），2011（3）：37-39

[2]楊素慧.分堆問題的完美解決[J].中學(xué)數(shù)學(xué)雜志（高中版），2011（9）：65