探究球入盒類型的排列組合題

華騰飛

排列組合中，有一類類似于球入盒問題，如何快速、準(zhǔn)確地求解此類問題呢？求解此類問題的關(guān)鍵是要弄清楚：球的“同”與“不同”、盒子的“同”與“不同”. 下面分類例析，相信同學(xué)們定會從中受到啟示，掌握求解此類問題的技巧，從而提高分析問題和解決問題的能力.

將不同小球放入不同的盒中

1. 球少盒多型

求解此種類型的問題，通常利用分步計數(shù)原理或排列的方法.

例1 若將3個不同的小球放入4個不同的盒子里，有幾種不同的放法？

解析 可分三步完成，由于每一個球都有4種放法，所以共有[43=64]種不同的放法.

例2 若將3個不同的小球放入4個不同的盒子中，每盒至多放一個，有多少種不同的放法？

解析 將盒子看作元素，即從4個不同的盒子里任意取3個放入3個不同的小球，這顯然是排列問題. 因此共有[A34=24]種不同的放法.

2. 球多盒少且每盒至少放一球型

求解此類問題的方法是先分組，然后排列.

例3 把4本不同的書獎給3名同學(xué)，每個人至少得1本，共有多少種不同的獎勵方法？

解析 分配方案為“2，1，1”，即一個盒子放2個球，另兩個盒子各放一個球. 將某兩個球合為一體，球的搭配有[C24]種方法. 盒子的選擇則為三個數(shù)字的全排列，即[A33]. 綜上可得，[C24?A33=36]種不同的獎勵方法.

例4 將4個不同的小球放入編號為1，2，3，4的四個盒子中，則恰有一個空盒的放法共有多少種？

解析 “恰好型”問題實際上確定了分配方案. 本題的分配方案為“2，1，1，0”，共有[C24?A34=144]種不同的放法.

3. 球與盒個數(shù)相同

例5 若將4個不同的小球放入4個不同的盒子里，每盒至少放一個，有多少種不同的放法？

解析 本題是4個不同小球的全排列問題，所以有[A44=24]種不同的方法.

例6 甲、乙兩隊各出7名隊員按事先排好的順序出場參加圍棋擂臺賽，雙方先由1號隊員比賽，負(fù)者被淘汰，勝者再與負(fù)方2號隊員比賽，……一直到一方隊員全被淘汰為止，另一方獲得勝利，形成一種比賽過程. 那么所有可能出現(xiàn)的比賽過程的種數(shù)是多少？

解析 從勝方（如甲方）角度考慮，由于甲方是勝方，不論甲方出場參賽有多少人，對方參戰(zhàn)肯定是7人，且全部負(fù)一場.可將勝方7人看成7個盒子，負(fù)方7人看成7個小球，每輸一場就向勝方隊員對應(yīng)的盒內(nèi)放1球，于是問題變成7球放入7盒問題. 因此一方取勝可能出現(xiàn)的種數(shù)有[C613]種，故共有[2C613=3432]種.

將相同小球放入不同類型的盒中

對于此類問題，可看成[x1+ x2+…+xm=n]的正整數(shù)解的個數(shù)，故用隔板法處理.

例7 將6個“三好”分配給四個班級，每個班級至少有一個名額，試問有多少種分配方案？

解析 本題等于求“6個相同的球放入4個不同的盒子且每個盒子不空”的放法. 即有[C4-16-1=C35=10]種分配方案.

例8 將5個相同球放入4個不同的盒子里，恰有一空盒，共有幾種不同放法？

解析 第一步：指定一個空盒，有[C14]種方法.

第二步：設(shè)剩下的3個盒子里分別放[x1，x2，x3]個小球，則[x1+x2+x3=5，x1≥1，x2≥1，x3≥1，]所以共有[C24]種不同的方法.

例9 把20個相同的小球全部放入編號為1，2，3，4的四個盒子中，要求每個盒內(nèi)的球數(shù)不小于它的編號數(shù)，試問共有多少種不同的放法？

解析 先在編號為1，2，3，4的四個盒子中依次放入1，2，3，4個球，還剩10個球. 原題變?yōu)椤扒?0個相同的球放入四個不同的盒子”的放法，即有[C310+3=286]種.

將不同小球放入相同的盒中

求解此類問題，通常采用分組的方法.

例10 若將3個不同的小球放入4個相同的盒子里，有幾種不同的放法？

解析 3個不同的小球分成一組有1種方法，分成兩組有[C13]種方法，分成3組一種方法. 因為盒子是相同的，所以都放入一個盒子里有1種放法，放入兩個盒子里有[C13]種放法（一盒1個，一盒2個），放入3個盒子里有1種方法（選3個盒子，一盒1個球），共有5種方法.

例11 若5個不同的小球放入4個相同的盒子里，恰有1個空盒，有幾種不同的放法？

解析 第一步：指定1個空盒，有1種方法；第二步：5個不同小球5個小球分成3組，有[（C15C14C33A22+C15C24C22A22）]種不同的方法；

第三步：將3組小球放到3個不同的盒子里，有1種方法.

由分步計數(shù)原理可知，一共有[（C15C14C33A22+C15C24C22A22）][=25]種不同的方法.

例12 將3個不同小球放入4個相同的盒子，每盒至多一個，有幾種不同放法？

解析 分3組，每組一個球，所以只有1種放法.

例13 若將5個不同的小球放入4個相同的盒子里，每盒至少放1個，有多少種不同的放法？

解析 將5個小球先分成4組，根據(jù)題意，每組分別是2個、1個、1個、1個，有[C25]種不同的方法；然后再放到4個相同的盒子里，只有一種方法. 故共有[C25=10]種不同的方法.

將相同小球放入相同盒中

此類問題的實質(zhì)是小球分成若干組有多少種情況.

例14 將5個相同球放入4個相同的盒子，每盒至少1個，有幾種不同的放法？

解析 第一步：因為是相同的小球，所以分成4組，只有一種方法（2+1+1+1=5）；第二步：又因為是相同的盒子，所以4組小球放入盒子中只有一種放法. 故只有一種放法.

例15 求方程[x1+x2+x3+x4=7]的正整數(shù)解的組數(shù).

解析 可將整數(shù)7看成7個相同的小球（每球表示整數(shù)1），將變量[x1，x2，x3，x4]看成4個盒子，那么7個小球入4個盒子且無空盒的不同放法種數(shù)，就是方程正整數(shù)解的組數(shù)，故可得正整數(shù)解的組數(shù)為[C36=20]組.

點撥 若要求的是方程非負(fù)整數(shù)解的組數(shù)，則同理可求得方程非負(fù)整數(shù)解的組數(shù)為[C310]組.

例16 若6個相同球放到3個相同的盒子里，每盒至少1個球，有多少種不同的放法？

解析 因為1+2+3=6，2+2+2=6，1+1+4=6. 故共有3種不同的放法.

例17 [△ABC]的三個內(nèi)角都是[π12]的整數(shù)倍，且三個內(nèi)角不全相等，這樣的三角形有多少個？

解析 三角形內(nèi)角和為[π]，它是[π12]的12倍，將這12個[π12]的角全部分配到三角形的內(nèi)角內(nèi)，其不同的分配方法（除去正三角形一種），就是所求的三角形的個數(shù). 于是問題變成將12個球放入3個盒子沒有空盒且3盒內(nèi)球數(shù)不全相等的放法問題，所以符合條件的三角形有[C212-1=65]個.

點撥 一般地，將[n]個同樣的小球隨機(jī)地放入[m（m≤n）]個盒子內(nèi)的不同放法有[Cm-1n+m-1]種；若要求[m]個盒子內(nèi)均有球，則不同的放法有[Cm-1n-1]種.

由以上例子可以看出，求解小球放入盒子中問題時，既要注意小球的“同”與“不同”，還要區(qū)分盒子的“同”與“不同”，然后根據(jù)兩個計數(shù)原理加以分析.