球与盒的分配问题求解研究

赵天玉，张 威 (长江大学信息与数学学院，湖北 荆州 434023)

球与盒的分配问题求解研究

赵天玉，张 威 (长江大学信息与数学学院，湖北 荆州 434023)

在组合数学与概率论的发展历史中，球与盒的分配模型起着非常重要的作用，有着广泛的应用。采用母函数与组合分析方法，借助于正整数的无序分拆数和第二类Stirling数，对球与盒的分配问题的14种情况进行了系统研究，给出了它们的分配方案的计数答案。

分配问题；母函数；无序分拆数；Stirling数

在组合数学和概率论的发展历史中，把球放入盒子里的模型起着非常重要的作用，这类问题称为球与盒的分配问题。球与盒的分配问题有着广泛的应用，如根据偶然事件在一周内发生的日期分类这些偶然事件时，球是偶然事件的类型而盒子是这一周的各天；在宇宙射线的实验中，盒子是计数器而球是到达计数器的粒子；在编码理论中，可以通过对以代码字为盒子，以误差为球的研究，得到k个代码字上的传输误差的可能分布；在图书出版中，可以通过对以页码为盒子，以球作为误印的研究而得到可能的k页上的误印分布；在生物学的照射研究中，撞击视网膜的光粒子对应于小球，视网膜的细胞对应于盒子；在礼券收集中，小球对应于特定的礼券，而盒子对应于礼券的类型[1]。虽然这类问题在一些教科书中也有论述[1-2]，但内容组织不连续，叙述过于分散；一些文献用初等方法对这类问题的某些特殊情况进行了求解[3-4]，但求解方法不具有普遍性，很难推广；文献[5]对分配模型进行了讨论，但不够全面。下面，笔者采用母函数与组合分析方法，借助于正整数的无序分拆数和第二类Stirling数，对球与盒的分配问题的14种情况进行了系统研究，给出了它们的分配方案的计数答案。

1 球与盒的分配问题

有n个小球和m个盒子，把小球分装到盒子中，其分配的方案数是所要研究的问题，该问题称为球与盒的分配问题。需要说明的是这里的球可相同可不同，盒子可有标记可无标记，盒子的容量可有限制可无限制，盒子可空也可非空，球在盒中的次序可考虑也可不考虑，盒子的次序可考虑也可不考虑等。因此，这是一个比较复杂的组合问题。

2 预备知识

2.1多重集排列与组合的母函数

2.2正整数的无序分拆数

定理2[6]正整数n的k-无序分拆数(最大数为k数列{Pk(n)} 的普母函数为:

正整数n无序分拆为小于等于k项(最大数≤k)的所有分拆数数列{P≤k(n)}的普母函数为：

2.3第二类Stirling数与集合的无序分拆

定理3[6]n元集无序分拆为k个不相交的非空子集的方法数为S2(n,k)。

3 求解方法

3.1球不可区分而盒子可区分

1)每盒球数不限，盒可空 显然，分配方案数序列的普母函数为：

2)每盒至少有一个球，即盒非空 这时，分配方案数序列的普母函数为：

3.2球可区分且盒子也可区分

1)每盒球数不限，盒可空(不考虑球在盒中的顺序) 这时，分配方案数序列的普母函数为：

故分配方案数为mn。该问题等价于第1个球可放到m个盒中的任一盒中，第2个球亦可放到m个盒中的任一盒中，第n个球亦可放到m个盒中的任一盒中。依乘法原理，分配方案数为m×m×…×m=mn。

2)每盒至多有一个球，盒可空(不考虑球在盒中的顺序) 分配方案数序列的普母函数为：

3)每盒至少有一个球，即盒非空(不考虑球在盒中的顺序) 由第二类Stirling数的普母函数得到分配方案数序列的普母函数为：

故分配方案数为m!S2(n,m)。实际上，相当于先将n个不同的球放到m个无标记的盒中，由于盒子有标记，再对m盒子进行全排列即可。

4) 第i盒中恰放置ni个球，1≤i≤m，n1+n2+…nm=n(不考虑球在盒中的顺序) 由定理1知，分配方案数序列的普母函数为：

3.3球可区分而盒子不可区分

1)每盒至少有一个球，盒非空(不考虑球在盒中的顺序) 该问题等价于把n元集无序分拆为m个不相交的非空子集。所以由定理3知分配方案数为S2(n,m)。

3.4球不可区分且盒子也不可区分

1)每盒球数不限(盒可空) 显然，该问题的每一种分配方式对应于下列不定方程非负整数解的一组解，1x1+2x2+…+mxm=n,(xi≥0,1≤i≤m)。解的组数序列的普母函数为：

由定理2知，恰好与正整数n的m-无序分拆数(最大数为m)数列{Pm(n)} 的普母函数相同，故分配方案数为Pm(n)=P≤m(n)-P≤m-1(n)。

4 结 语

球与盒的分配问题是组合数学讨论的经典内容，有着广泛的应用。笔者采用母函数与组合分析方法，借助于正整数的无序分拆数和第二类Stirling数，对球与盒的分配问题的14种情况进行了系统研究，不但给出了它们的分配方案的计数答案，而且对绝大多数情况的计数答案阐述了其组合意义。这样将组合数学中相对独立的知识块如非重集的排列组合、重集的排列组合、母函数、正整数的分拆和Stirling数等有机地结合起来，更显示出母函数在求解问题中的强大功能，对学习组合数学的读者有一定的参考价值。

[1]Fred S R，Barry T. 应用组合数学[M]. 第2版.冯速译.北京：机械工业出版社，2007：35-39.

[2]孙世新，张先迪. 组合原理及其应用[M]. 北京：国防工业出版社，2006：172-175.

[3]王克亮. 对一类相同元素分配问题的探究[J]. 中学教研(数学)，2009(9)：19-20.

[4]刘付亮，郭俊美. “不可辨”条件下的“分球入盒”问题[J]. 中学数学杂志(高中)，2003(2)：36-37.

[5]颜刚，李彬，王涛. 多角度处理分装模型的计数与概率计算[J]. 大学数学，2010，26(5)：184-188.

[6]田秋成. 组合数学[M]. 北京：电子工业出版社，2006：71-103.

[编辑] 洪云飞

10.3969/j.issn.1673-1409(N).2012.03.001

O157.1

A

1673-1409(2012)03-N001-03

2012-01-12

湖北省教育厅高等学校科学技术基金项目(D20111305)。

赵天玉(1958-)，男，1981年大学毕业，硕士，教授，现主要从事组合数学方面的教学与研究工作。