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