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

肖支普

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

1.直接使用擋板法

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

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

2.允許有“空組”問題

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

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

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

3.受限制分組問題

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

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

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

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

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

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