趙天玉，張 威 (長江大學(xué)信息與數(shù)學(xué)學(xué)院，湖北 荊州 434023)

球與盒的分配問題求解研究

趙天玉，張 威 (長江大學(xué)信息與數(shù)學(xué)學(xué)院，湖北 荊州 434023)

在組合數(shù)學(xué)與概率論的發(fā)展歷史中，球與盒的分配模型起著非常重要的作用，有著廣泛的應(yīng)用。采用母函數(shù)與組合分析方法，借助于正整數(shù)的無序分拆數(shù)和第二類Stirling數(shù)，對球與盒的分配問題的14種情況進行了系統(tǒng)研究，給出了它們的分配方案的計數(shù)答案。

分配問題；母函數(shù)；無序分拆數(shù)；Stirling數(shù)

在組合數(shù)學(xué)和概率論的發(fā)展歷史中，把球放入盒子里的模型起著非常重要的作用，這類問題稱為球與盒的分配問題。球與盒的分配問題有著廣泛的應(yīng)用，如根據(jù)偶然事件在一周內(nèi)發(fā)生的日期分類這些偶然事件時，球是偶然事件的類型而盒子是這一周的各天；在宇宙射線的實驗中，盒子是計數(shù)器而球是到達計數(shù)器的粒子；在編碼理論中，可以通過對以代碼字為盒子，以誤差為球的研究，得到k個代碼字上的傳輸誤差的可能分布；在圖書出版中，可以通過對以頁碼為盒子，以球作為誤印的研究而得到可能的k頁上的誤印分布；在生物學(xué)的照射研究中，撞擊視網(wǎng)膜的光粒子對應(yīng)于小球，視網(wǎng)膜的細胞對應(yīng)于盒子；在禮券收集中，小球?qū)?yīng)于特定的禮券，而盒子對應(yīng)于禮券的類型[1]。雖然這類問題在一些教科書中也有論述[1-2]，但內(nèi)容組織不連續(xù)，敘述過于分散；一些文獻用初等方法對這類問題的某些特殊情況進行了求解[3-4]，但求解方法不具有普遍性，很難推廣；文獻[5]對分配模型進行了討論，但不夠全面。下面，筆者采用母函數(shù)與組合分析方法，借助于正整數(shù)的無序分拆數(shù)和第二類Stirling數(shù)，對球與盒的分配問題的14種情況進行了系統(tǒng)研究，給出了它們的分配方案的計數(shù)答案。

1 球與盒的分配問題

有n個小球和m個盒子，把小球分裝到盒子中，其分配的方案數(shù)是所要研究的問題，該問題稱為球與盒的分配問題。需要說明的是這里的球可相同可不同，盒子可有標(biāo)記可無標(biāo)記，盒子的容量可有限制可無限制，盒子可空也可非空，球在盒中的次序可考慮也可不考慮，盒子的次序可考慮也可不考慮等。因此，這是一個比較復(fù)雜的組合問題。

2 預(yù)備知識

2.1多重集排列與組合的母函數(shù)

2.2正整數(shù)的無序分拆數(shù)

定理2[6]正整數(shù)n的k-無序分拆數(shù)(最大數(shù)為k數(shù)列{Pk(n)} 的普母函數(shù)為:

正整數(shù)n無序分拆為小于等于k項(最大數(shù)≤k)的所有分拆數(shù)數(shù)列{P≤k(n)}的普母函數(shù)為：

2.3第二類Stirling數(shù)與集合的無序分拆

定理3[6]n元集無序分拆為k個不相交的非空子集的方法數(shù)為S2(n,k)。

3 求解方法

3.1球不可區(qū)分而盒子可區(qū)分

1)每盒球數(shù)不限，盒可空 顯然，分配方案數(shù)序列的普母函數(shù)為：

2)每盒至少有一個球，即盒非空 這時，分配方案數(shù)序列的普母函數(shù)為：

3.2球可區(qū)分且盒子也可區(qū)分

1)每盒球數(shù)不限，盒可空(不考慮球在盒中的順序) 這時，分配方案數(shù)序列的普母函數(shù)為：

故分配方案數(shù)為mn。該問題等價于第1個球可放到m個盒中的任一盒中，第2個球亦可放到m個盒中的任一盒中，第n個球亦可放到m個盒中的任一盒中。依乘法原理，分配方案數(shù)為m×m×…×m=mn。

2)每盒至多有一個球，盒可空(不考慮球在盒中的順序) 分配方案數(shù)序列的普母函數(shù)為：

3)每盒至少有一個球，即盒非空(不考慮球在盒中的順序) 由第二類Stirling數(shù)的普母函數(shù)得到分配方案數(shù)序列的普母函數(shù)為：

故分配方案數(shù)為m!S2(n,m)。實際上，相當(dāng)于先將n個不同的球放到m個無標(biāo)記的盒中，由于盒子有標(biāo)記，再對m盒子進行全排列即可。

4) 第i盒中恰放置ni個球，1≤i≤m，n1+n2+…nm=n(不考慮球在盒中的順序) 由定理1知，分配方案數(shù)序列的普母函數(shù)為：

3.3球可區(qū)分而盒子不可區(qū)分

1)每盒至少有一個球，盒非空(不考慮球在盒中的順序) 該問題等價于把n元集無序分拆為m個不相交的非空子集。所以由定理3知分配方案數(shù)為S2(n,m)。

3.4球不可區(qū)分且盒子也不可區(qū)分

1)每盒球數(shù)不限(盒可空) 顯然，該問題的每一種分配方式對應(yīng)于下列不定方程非負整數(shù)解的一組解，1x1+2x2+…+mxm=n,(xi≥0,1≤i≤m)。解的組數(shù)序列的普母函數(shù)為：

由定理2知，恰好與正整數(shù)n的m-無序分拆數(shù)(最大數(shù)為m)數(shù)列{Pm(n)} 的普母函數(shù)相同，故分配方案數(shù)為Pm(n)=P≤m(n)-P≤m-1(n)。

4 結(jié) 語

球與盒的分配問題是組合數(shù)學(xué)討論的經(jīng)典內(nèi)容，有著廣泛的應(yīng)用。筆者采用母函數(shù)與組合分析方法，借助于正整數(shù)的無序分拆數(shù)和第二類Stirling數(shù)，對球與盒的分配問題的14種情況進行了系統(tǒng)研究，不但給出了它們的分配方案的計數(shù)答案，而且對絕大多數(shù)情況的計數(shù)答案闡述了其組合意義。這樣將組合數(shù)學(xué)中相對獨立的知識塊如非重集的排列組合、重集的排列組合、母函數(shù)、正整數(shù)的分拆和Stirling數(shù)等有機地結(jié)合起來，更顯示出母函數(shù)在求解問題中的強大功能，對學(xué)習(xí)組合數(shù)學(xué)的讀者有一定的參考價值。

[1]Fred S R，Barry T. 應(yīng)用組合數(shù)學(xué)[M]. 第2版.馮速譯.北京：機械工業(yè)出版社，2007：35-39.

[2]孫世新，張先迪. 組合原理及其應(yīng)用[M]. 北京：國防工業(yè)出版社，2006：172-175.

[3]王克亮. 對一類相同元素分配問題的探究[J]. 中學(xué)教研(數(shù)學(xué))，2009(9)：19-20.

[4]劉付亮，郭俊美. “不可辨”條件下的“分球入盒”問題[J]. 中學(xué)數(shù)學(xué)雜志(高中)，2003(2)：36-37.

[5]顏剛，李彬，王濤. 多角度處理分裝模型的計數(shù)與概率計算[J]. 大學(xué)數(shù)學(xué)，2010，26(5)：184-188.

[6]田秋成. 組合數(shù)學(xué)[M]. 北京：電子工業(yè)出版社，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

湖北省教育廳高等學(xué)?？茖W(xué)技術(shù)基金項目(D20111305)。

趙天玉(1958-)，男，1981年大學(xué)畢業(yè)，碩士，教授，現(xiàn)主要從事組合數(shù)學(xué)方面的教學(xué)與研究工作。