巧用“挡板法”解排列组合问题

肖支普

挡板法用于解决元素分组问题,灵活运用挡板法能处理一些较复杂的排列组合问题,但使用时有三点要求:①元素相同;②每组均“非空”,即每组中至少分一个元素;③不能有剩余元素.

1.直接使用挡板法

【例1】 现有10个完全相同的球全部放入7个不同的盒子,每个盒子至少1个,问共有多少种不同的方法?

分析:该问题用分类计数法较复杂,但可以将10个球排成一行,10个球中间就出现9个空挡,再用6个挡板把10个球分成有序的7份,每个班级就依次按班级序号分到对应的n个球(可能是1个﹑2个﹑3个﹑4个).即在9个空挡中插入6个挡板,由6个挡板把球分成7份,共有C⁶₉种方法.

2.允许有“空组”问题

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

分析:这道题很多学生会填错,错误原因是直接使用挡板法而忽略了使用条件,这与例1区别在于:例1中每组都要求非空,而例2允许有空盒.即8个球可能分在2个甚至1个盒中.

但此类题型还是可以用挡板法,只需做一些小变化,可以假想从每个盒子中借一个球,这样共有11个球,然后用挡板法.这11个球中间10个空挡用2个挡板,故答案为C²₁₀种方法.这类题型我们称为“先借后还”.当盒中分到一个球后还回1个球,该盒实际上是空盒;分到2个球,该盒实际上只含一个球,依此类推,可以避免复杂的分类.

3.受限制分组问题

【例3】 8个完全相同的球全部放入编号为1、2、3的3个盒子中,要求每个盒子内的球数不少于其编号数,则有___种不同的分法.

分析:这类题型是受限制的分组问题,也可以用挡板法.先在3个盒子内分别放入0个、1个、2个球,这样保证每个盒子中只需要再至少加入1个球就可以达到要求.所以对剩余的5个球用挡板法分组有C²₄种分法.故答案为C²₄=6.

4.处理某些集合中的对应问题

【例4】 已知两个实数集A={a₁,a₂,…,a₅₀},B={b₁,b₂,…,b₂₅},若从A到B的映射f满足B中每个元素都有原象,且f(a₁)≥f(a₂)≥…≥f(a₅₀),则这样的映射共有_________个.

分析:这里直接分组较复杂,可以将a₁,a₂,…,a₅₀按顺序排成一排,把b₁,b₂,…,b₂₅按照从大到小的顺序去对应,只要将a₁,a₂,…,a₅₀分成25份即可.利用挡板法求得有C²⁴₄₉种.

(责任编辑:金 铃)