分堆问题的一种一般解法

辛智文

将n个不同元素分成m堆（每堆至少一个，每堆个数可以不相等），一共有多少种不同的分法.这样的问题通常称为分堆问题.当n，m较小时这类问题解决起来并不困难，但要给出一般的结论却不容易.

为了叙述方便，我们先来探讨这样的问题：将n个人分配到m个单位（每个单位至少一人，各单位人数可以不相等.n≥m），一共有多少种不同的分法.显然，这一问题的结果除以m！就是上面分堆问题的结果.

设将n个人分配到m个单位（每个单位至少一人，各单位人数可以不相等.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

下面用第二数学归纳法加以证明：

①当m=1时，左=右=1，结论显然成立.

②假设m≤k时结论都成立，即

这表明当m=k+1时结论成立，由归纳原理知原结论成立.

就是说，将n个不同元素分成m堆（每堆至少一个，每堆个数可以不相等，m≤n），一共有[mn-Cm-1m×（m-1）n+Cm-2m×（m-2）n-Cm-3m×（m-3）n+…+（-1）m-1C1m]÷m！种不同的分法.

参考文献

[1]严明军.分堆问题[J].中学数学杂志（高中版），2011（3）：37-39

[2]杨素慧.分堆问题的完美解决[J].中学数学杂志（高中版），2011（9）：65