巧用“擋板法”解排列組合問題

肖支普

擋板法用于解決元素分組問題,靈活運(yùn)用擋板法能處理一些較復(fù)雜的排列組合問題,但使用時有三點(diǎn)要求:①元素相同;②每組均“非空”,即每組中至少分一個元素;③不能有剩余元素.

1.直接使用擋板法

【例1】 現(xiàn)有10個完全相同的球全部放入7個不同的盒子,每個盒子至少1個,問共有多少種不同的方法?

分析:該問題用分類計數(shù)法較復(fù)雜,但可以將10個球排成一行,10個球中間就出現(xiàn)9個空擋,再用6個擋板把10個球分成有序的7份,每個班級就依次按班級序號分到對應(yīng)的n個球(可能是1個﹑2個﹑3個﹑4個).即在9個空擋中插入6個擋板,由6個擋板把球分成7份,共有C⁶₉種方法.

2.允許有“空組”問題

【例2】 8個完全相同的球全部放入3個不同的盒子中,有_________種不同的分法.

分析:這道題很多學(xué)生會填錯,錯誤原因是直接使用擋板法而忽略了使用條件,這與例1區(qū)別在于:例1中每組都要求非空,而例2允許有空盒.即8個球可能分在2個甚至1個盒中.

但此類題型還是可以用擋板法,只需做一些小變化,可以假想從每個盒子中借一個球,這樣共有11個球,然后用擋板法.這11個球中間10個空擋用2個擋板,故答案為C²₁₀種方法.這類題型我們稱為“先借后還”.當(dāng)盒中分到一個球后還回1個球,該盒實(shí)際上是空盒;分到2個球,該盒實(shí)際上只含一個球,依此類推,可以避免復(fù)雜的分類.

3.受限制分組問題

【例3】 8個完全相同的球全部放入編號為1、2、3的3個盒子中,要求每個盒子內(nèi)的球數(shù)不少于其編號數(shù),則有___種不同的分法.

分析:這類題型是受限制的分組問題,也可以用擋板法.先在3個盒子內(nèi)分別放入0個、1個、2個球,這樣保證每個盒子中只需要再至少加入1個球就可以達(dá)到要求.所以對剩余的5個球用擋板法分組有C²₄種分法.故答案為C²₄=6.

4.處理某些集合中的對應(yīng)問題

【例4】 已知兩個實(shí)數(shù)集A={a₁,a₂,…,a₅₀},B={b₁,b₂,…,b₂₅},若從A到B的映射f滿足B中每個元素都有原象,且f(a₁)≥f(a₂)≥…≥f(a₅₀),則這樣的映射共有_________個.

分析:這里直接分組較復(fù)雜,可以將a₁,a₂,…,a₅₀按順序排成一排,把b₁,b₂,…,b₂₅按照從大到小的順序去對應(yīng),只要將a₁,a₂,…,a₅₀分成25份即可.利用擋板法求得有C²⁴₄₉種.

(責(zé)任編輯:金 鈴)