分球入盒問題例析

■浙江省紹興市上虞區(qū)上虞中學(xué) 章舜龍

在求解排列、組合問題的過程中,我們經(jīng)常會遇到一類“分球入盒”的問題或可轉(zhuǎn)化為“分球入盒”模型的問題。不少同學(xué)由于不能正確對待“球”和“盒”的順序而導(dǎo)致錯解。下面例析“分球入盒”問題,以期幫助同學(xué)們厘清思路,順利解答該類問題。

一、球同盒同

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

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

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

分析:箱子相同時不需要考慮箱子的順序,球相同也無須考慮球的差別,只要考慮各個箱子中放入小球的數(shù)量多少,故可用“窮舉法”求解。

解:(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}。

點(diǎn)評:“窮舉法”是求解排列組合問題中最常見的數(shù)學(xué)思想方法。此時,“無招勝有招”。

二、球同盒不同

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

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

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

分析:本題與例1 的不同點(diǎn)是這里的4個箱子是不同的,需考慮箱子間的順序,若還用窮舉法解就顯得繁雜,可將問題轉(zhuǎn)化為方程正整數(shù)解的問題,進(jìn)而利用“插空法”求解。

解:(1)設(shè)第i個箱子里放入mi(i=1,2,3,4)個球,則問題轉(zhuǎn)化為求不定方程m1+m2+m3+m4=7(*)的正整數(shù)解的個數(shù)。

將7個小球排成一排,用3 個隔板將7個小球分成四份,每一種分隔方法對應(yīng)一種放法,7個小球之間有6個間隙,在其中任選3個插入隔板,有C36=20(種)方法。故共有20種不同的放法。

(2)箱子允許有空,等價于求(*)式的非負(fù)整數(shù)解個數(shù)。

設(shè)xi=mi+1(i=1,2,3,4),問題轉(zhuǎn)化為求不定方程x1+x2+x3+x4=11的正整數(shù)解的個數(shù)。

對于(2)也可這樣思考,此時把7個小球與3個隔板等同看待,認(rèn)為共有10 個元素,將它們排成一列,每一個排列對應(yīng)一種放法,如OOOOO||OO|對應(yīng)的放法就是:{5,0,2,0},10個位置任選3個放隔板,其余7個位置放小球,共有=120(種)不同方法。

點(diǎn)評:求解相同元素的分配問題用“隔板法”,將n個相同的元素分成m份(n,m為正整數(shù)),每份至少一個元素,可以用m-1 塊隔板,插入n個元素排成一排的n-1個空隙中,所有分法數(shù)為。

三、盒同球不同

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

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

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

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

解:(1)箱子不空,分為以下三類:

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

(2)箱子允許空,分為下面四類。

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

②4 個箱子中有1 個是空的,則分為下面四種情形。

此時共有不同的放法數(shù)為21+105+70+105=301。

③4 個箱子中有2 個是空的,又分為下面三種情形。

ⅲ)4個箱子中小球數(shù)是{0,0,3,4},不同的放法有C37C44=35(種)。

此時共有不同的放法數(shù)為7+21+35=63。

④4個箱子中有3個是空的僅有一種情形{0,0,0,7},共有1種放法。

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

點(diǎn)評:本題屬于分組問題,分組的類型包括整體均分、部分均分和不等分三種,無論分成幾組,都應(yīng)注意只要有元素的個數(shù)相等的組存在,就需要考慮均分的現(xiàn)象(即:整體平均分組;或部分平均分組)。

四、球盒均不同

例4將7個不同的小球,放入4個不同的箱子中。

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

(2)箱子允許空,有多少種不同的放法?分析:與例3 比較,需考慮箱子的差異,即箱子間的順序。

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

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

點(diǎn)評:重復(fù)排列問題要區(qū)分兩類元素,一類可以重復(fù),另一類不能重復(fù),把不能重復(fù)的元素看作“客”,把能重復(fù)的元素看作“店”,通過“住店法”可順利解題。在使用住店策略解決這類問題時,關(guān)鍵是正確判斷哪個是底數(shù),哪個是指數(shù)。