分堆問題的一種一般解法

辛智文

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

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

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

f（n，1）=1；

當m=2時，n個人中的每個人都有2種分配方案，總共有2×2×…×2=2n種方法，減去只到了其中一個單位的2種方法，就有

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

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

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

當m=4時，n個人中的每個人都有4種分配方案，總共有4×4×…×4=4n種方法，減去只到了其中3個單位的C34（3n-C23×2n+C13）種方法，只到了其中2個單位的C24（2n-2）種方法，還有只到了其中1個單位的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ù)學歸納法加以證明：

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

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

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

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

參考文獻

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

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