隔板法就是在n个元素间的(n-1)个空中插入 k个板,可以把n个元素分成k+1组的方法。
应用隔板法必须满足三个条件:
(1) 这n个元素必须互不相异
(2) 所分成的每一组至少分得一个元素
(3) 分成的组别彼此相异例1:高二年级8个班级协商组成年级篮球队,共需10名队员,每个班级至少要出一名,有多少种不同的组成方式?
分析:将10名队员理解成10个球,排成一列,共形成9个空隙,设想有7个隔板,将排成一列的10个球隔成8段,注意:任意两块隔板不能相邻!故为C7//9=36种。
例2:方程X+Y+Z+w=23有多少正整数解。
分析:我们设想有23个无区别的球排成一列,共形成22个空,可以理解为有3块隔板,将排成一列的球隔成4段,共有C3/22=1540个正整数解。
例3:
(待解)注意:例5的思考可以借鉴。
对某些不讨符合上述隔板法条件的一些问题可以通过一些技巧“转化”为符合条件的隔板问题。
技巧一:添加球数用隔板法
例4:求方程X+Y+Z+w=23的非负整数解的个数。
分析:注意到x、y、z可以为零,故上题解法中的限定“每空至多插一块隔板”就不成立了,怎么办呢?只要添加四个球,给x、y、z、w各一个球。这样原问题就转化为求X+Y+Z+w=26的正整数解的个数了,故解的个数为C3/26=2600(个)。 评述:本例通过添加球数,将问题转化为如例1中的典型隔板法问题。
例5:20个相同的球分给3个人,允许有人不取,但必须分完,有多少种分法?
分析:问题转化为:20个相同的球分给1,2,3编号的盒子,允许有盒为空,但必须分完,有多少种分法?解析:将20个球拍成一排,包括两端一共有21个空隙(因为这里可以盒为空,就是隔板可以“挤进”一个空隙里,所以不能以空隙计算!!),将2个隔板插入这些空隙中,则每一种隔板位置对应了一种分法。这里球和隔板共有22个,C2/22=231种.
或者利用例4的思考方式:添加3个球,给3个人每人一个,问题转化为:23个相同的球分给3个人,每人至少分一个球,且必须分完,有多少种分法?也就是23个球有22个空隙,2块隔板分成三部分,C2/22=231种。
评述:这个问题是典型的玻瑟——爱因斯坦(Bose-Einstein)统计模型:要将k个相同的球放入n个不同的盒子,每盒所放球数不限,有多少种不同放法?请注意。
技巧二:减少球数用隔板法
例6:将20个相同的小球放入编号分别为1,2,3,4的四个盒子中,要求每个盒子中的球数不少于它的编号数,求放法总数。
分析:先在编号1,2,3,4的四个盒子内分别放0,1,2,3个球,剩下14个无区别的球,问题等价于将14个球放入4个编号为1,2,3,4的四个盒子里,每个盒子至少有一个球的问题。
剩下14个无区别的球排成一列,共形成13个空,可以理解为有3块隔板,将排成一列的球隔成4段,每段至少1个,有C3/13=286(种)。