分球入盒问题例析

■浙江省绍兴市上虞区上虞中学 章舜龙

在求解排列、组合问题的过程中,我们经常会遇到一类“分球入盒”的问题或可转化为“分球入盒”模型的问题。不少同学由于不能正确对待“球”和“盒”的顺序而导致错解。下面例析“分球入盒”问题,以期帮助同学们厘清思路,顺利解答该类问题。

一、球同盒同

例1将7个相同的小球,放入4个相同的箱子中。

(1)每个箱子中至少有一个小球(即箱子不空),有多少种不同的放法?

(2)若箱子允许空,又有多少种不同的放法?

分析:箱子相同时不需要考虑箱子的顺序,球相同也无须考虑球的差别,只要考虑各个箱子中放入小球的数量多少,故可用“穷举法”求解。

解:(1)箱子不空有3 种放法:{1,1,1,4},{1,1,2,3},{1,2,2,2}。

(2)箱子允许空共有11种放法:

{0,0,0,7},{0,0,1,6},{0,0,2,5},{0,0,3,4},{0,1,1,5},{0,1,2,4},{0,1,3,3},{0,2,2,3},{1,1,1,4},{1,1,2,3},{1,2,2,3}。

点评:“穷举法”是求解排列组合问题中最常见的数学思想方法。此时,“无招胜有招”。

二、球同盒不同

例2将7个相同的小球,放入4个不同的箱子中。

(1)箱子不空,有多少种不同的放法?

(2)若箱子允许空,有多少种不同的放法?

分析:本题与例1 的不同点是这里的4个箱子是不同的,需考虑箱子间的顺序,若还用穷举法解就显得繁杂,可将问题转化为方程正整数解的问题,进而利用“插空法”求解。

解:(1)设第i个箱子里放入mi(i=1,2,3,4)个球,则问题转化为求不定方程m1+m2+m3+m4=7(*)的正整数解的个数。

将7个小球排成一排,用3 个隔板将7个小球分成四份,每一种分隔方法对应一种放法,7个小球之间有6个间隙,在其中任选3个插入隔板,有C36=20(种)方法。故共有20种不同的放法。

(2)箱子允许有空,等价于求(*)式的非负整数解个数。

设xi=mi+1(i=1,2,3,4),问题转化为求不定方程x1+x2+x3+x4=11的正整数解的个数。

对于(2)也可这样思考,此时把7个小球与3个隔板等同看待,认为共有10 个元素,将它们排成一列,每一个排列对应一种放法,如OOOOO||OO|对应的放法就是:{5,0,2,0},10个位置任选3个放隔板,其余7个位置放小球,共有=120(种)不同方法。

点评:求解相同元素的分配问题用“隔板法”,将n个相同的元素分成m份(n,m为正整数),每份至少一个元素,可以用m-1 块隔板,插入n个元素排成一排的n-1个空隙中,所有分法数为。

三、盒同球不同

例3将7个不同的小球,放入4个相同的箱子中。

(1)箱子不空,有多少种不同的放法?

(2)箱子允许空,有多少种不同的放法?

分析:此情形中要注意球是不同的,需考虑其差异,而箱子是相同的就不需要考虑其顺序,故常用“分类累加法”求解。

解:(1)箱子不空,分为以下三类:

放法共有35+210+105=350(种)。

(2)箱子允许空,分为下面四类。

①4个箱子均不空,由(1)知有350种放法。

②4 个箱子中有1 个是空的,则分为下面四种情形。

此时共有不同的放法数为21+105+70+105=301。

③4 个箱子中有2 个是空的,又分为下面三种情形。

ⅲ)4个箱子中小球数是{0,0,3,4},不同的放法有C37C44=35(种)。

此时共有不同的放法数为7+21+35=63。

④4个箱子中有3个是空的仅有一种情形{0,0,0,7},共有1种放法。

综上所述,共有350+301+63+1=715(种)不同放法。

点评:本题属于分组问题,分组的类型包括整体均分、部分均分和不等分三种,无论分成几组,都应注意只要有元素的个数相等的组存在,就需要考虑均分的现象(即:整体平均分组;或部分平均分组)。

四、球盒均不同

例4将7个不同的小球,放入4个不同的箱子中。

(1)箱子不空,有多少种不同的放法?

(2)箱子允许空,有多少种不同的放法?分析:与例3 比较,需考虑箱子的差异,即箱子间的顺序。

解:(1)由例3 可知7 个不同的小球,放入4 个相同的箱子中,箱子不空时共有350种放法。故将7 个不同的小球,放入4 个不同的箱子中,箱子不空,共有350A44=8 400(种)不同的放法。

(2)用“分步法”求解。将7 个不同的小球,放入4 个不同的箱子中,箱子允许空,每一个小球都有4种不同的放法,故共有47=16 384(种)不同的放法。

点评:重复排列问题要区分两类元素,一类可以重复,另一类不能重复,把不能重复的元素看作“客”,把能重复的元素看作“店”,通过“住店法”可顺利解题。在使用住店策略解决这类问题时,关键是正确判断哪个是底数,哪个是指数。