分堆问题的一种一般解法

将 n 个不同元素分成 m 堆（每堆至少一个， 每堆个数 可

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

为了叙述方便，我们先来探讨这样的问题：将 n 个人分 配到

m 个单位（每个单位至少一人， 各单位人数可以不相等 .n >m）,

一共有多少种不同的分法.显然，这一问题的结果除 以m !就是上面分堆问题的结果.

设将 n 个人分配到 m 个单位 （每个单位至少一人， 各单 位人数可以不相等.n > m）, 一共有f （n, m）种不同的分法. 易得：

f（ n， 1） =1；

当 m=2 时， n 个人中的每个人都有 2 种分配方案，总共 有

2x 2X-X 2=2n种方法，减去只到了其中一个单位的 2 种方法，就

有

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

当 m=3 时， n 个人中的每个人都有 3 种分配方案，总共 有

3x 3x・・・x 3=3n种方法，减去只到了其中2个单位的C23

（2n-2）种方法，还有只到了其中 1个单位的3种方法，就 f

( n, 3) =3n-C23 (2n-2) -C13=3n-C23X 2n+C13;

当 m=4 时， n 个人中的每个人都有 4 种分配方案，总共 有4X 4X-X 4=4n种方法，减去只到了其中3个单位的C34 (3n-C23X 2n+C13)种方法，只到了其中2个单位的C24(2n-2) 种方法，还有只到了其中 1 个单位的 4种方法，就有

f(n， 4)=4n-C34[3n-C23 (2n-2)-C13]-C24 (2n-2) -C14=4n-C34X 3n+C24X 2n-C14……

我们猜想：

(f n， m)=mn-Cm-1mX( m-1 )n+Cm-2mX( m-2)n-Cm-3m X( m-3) n+…+ (-1) m-1C1m

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

① 当 m=1 时，左 =右 =1 ，结论显然成立 . ② 假设m < k时结论都成立，即

这表明当 m=k+1 时结论成立， 由归纳原理知原结论成立 . 就是说，将 n 个不同元素分成 m 堆(每堆至少一个， 每 堆个数可以不相等， m < n)，一共有[mn-Cm-1m X( m-1)

n+Cm-2m X( m-2) n-Cm-3m X( m-3) n+…+ (-1) m-1C1m] -m !种

不同的分法.

参考文献

[1]严明军•分堆问题[J].中学数学杂志(高中版)，2011( 3): 37-39

[2]杨素慧.分堆问题的完美解决[J]•中学数学杂志（高中

， 2011（ 9）：65 版）