隔板法题型总结隔板法就是在n个元素间的(n-1)个空中插入若干个(b)个板,可以把n个元素分成(b+1)组的方法。应用隔板法必须满足三个条件:(1)这n个元素必须相同(2)所分成的每一组至少分得一个元素(3)分成的组别彼此相异组合不排列的情况可以用隔板法例如:某校组建一球队需16人,该校共10个班级,且每个班至少分配一个名额,共有几种情况?解:C[(16-1),(10-1)]=C(15,9)=1816214400种例1.求方程X+Y+Z=10的正整数解的个数。[分析]将10个球排成一排,球与球之间形成9个空隙,将两个隔板插入这些空隙中(每空至多插一块隔板),规定由隔板分成的左、中、右三部分的球数分别为x、y、z之值(如下图)。则隔法与解的个数之间建立了一一对立关系,故解的个数为C92=36(个)。实际运用隔板法解题时,在确定球数、如何插隔板等问题上形成了一些技巧。下面举例说明。技巧一:添加球数用隔板法。○○○∣○○○∣○○○○例2.求方程X+Y+Z=10的非负整数解的个数。[分析]注意到x、y、z可以为零,故上题解法中的限定“每空至多插一块隔板”就不成立了,怎么办呢?只要添加三个球,给x、y、z各一个球。这样原问题就转化为求X+Y+Z=13的正整数解的个数了,故解的个数为C122=66(个)。[点评]本例通过添加球数,将问题转化为如例1中的典型隔板法问题。技巧二:减少球数用隔板法:例3.将20个相同的小球放入编号分别为1,2,3,4的四个盒子中,要求每个盒子中的球数不少于它的编号数,求放法总数。解法1:先在编号1,2,3,4的四个盒子内分别放0,1,2,3个球,剩下14个球,有1种方法;再把剩下的球分成4组,每组至少1个,由例1知方法有C133=286(种)。解法2:第一步先在编号1,2,3,4的四个盒子内分别放1,2,3,4个球,剩下10个球,有1种方法;第二步把剩下的10个相同的球放入编号为1,2,3,4的盒子里,由例2知方法有C133=286(种)。[点评]两种解法均通过减少球数将问题转化为例1、例2中的典型问题。技巧三:先后插入用隔板法。例4.为宣传党的十六大会议精神,一文艺团体下基层宣传演出,准备的节目表中原有4个歌舞节目,如果保持这些节目的相对顺序不变,拟再添两个小品节目,则不同的排列方法有多少种?[分析]记两个小品节目分别为A、B。先排A节目。根据A节目前后的歌舞节目数目考虑方法数,相当于把4个球分成两堆,由例2知有C51种方法。这一步完成后就有5个节目了。再考虑需加入的B节目前后的节目数,同理知有C61种方法。故由分步计数原理知,方法共有C51*C61(种)。例5将20个大小形状完全相同的小球放入3个不同的盒子,允许有盒子为空,但球必须放完,有多少种不同的方法?分析:本题中的小球大小形状完全相同,故这些小球没有区别,问题等价于将小球分成三组,允许有若干组无元素,用隔板法.解析:将20个小球分成三组需要两块隔板,因为允许有盒子为空,不符合隔板法的原理,那就人为的再加上3个小球,保证每个盒子都至少分到一个小球,那就符合隔板法的要求了(分完后,再在每组中各去掉一个小球,即满足了题设的要求)。然后就变成待分小球总数为23个,球中间有22个空档,需要在这22个空档里加入2个隔板来分隔为3份,共有C(22,2)=231种不同的方法.例6:有广西橘子,烟台苹果,莱阳梨若干,从中随意取出四个,问共有多少种不同取法?问题等价于有四个水果篮,将其分为三组向里面加入不同水果,且允许篮子为空。答案C(6,2)=15种总结对n件相同物品(或名额)分给m个人(或位置),允许若干个人(或位置)为空的问题,可以看成将这n件物品分成m组,允许若干组为空的问题.Cn+m-1m-1种排法