登录
2020-09-25 10:01:07

隔板法 免费编辑 添加义项名

B 添加义项
?
义项指多义词的不同概念,如李娜的义项:网球运动员、歌手等;非诚勿扰的义项:冯小刚执导电影、江苏卫视交友节目等。 查看详细规范>>
所属类别 :
科学名词
科学名词
编辑分类

在组合数学中,隔板法(又叫插板法)是排列组合的推广,主要用于解决不相邻组合与追加排列的问题。

基本信息

  • 中文名称

    隔板法

  • 又名

    插板法

折叠 编辑本段 定义

隔板法就是在n个元素间插入(b-1)个板,即把n个元素分成b组的方法。

折叠 编辑本段 问题解析

例1将20个大小形状完全相同的小球放入3个不同的盒子,允许有盒子为空,但球必须放完,有多少种不同的方法?

分析:本题中的小球大小形状完全相同,故这些小球没有区别,问题等价于将小球分成三组,允许有若干组无元素,用隔板法。

解析:将20个小球分成三组需要两块隔板,因为允许有盒子为空,不符合隔板法的原理,那就人为的再加上3个小球,保证每个盒子都至少分到一个小球,那就符合隔板法的要求了(分完后,再在每组中各去掉一个小球,即满足了题设的要求)。然后就变成待分小球总数为23个,球中间有22个空档,需要在这22个空档里加入2个隔板来分隔为3份,共有C(22,2)=231种不同的方法。

点评:对n件相同物品(或名额)分给m个人(或位置),允许若干个人(或位置)为空的问题,可以看成将这n件物品分成m组,允许若干组为空的问题.将n件物品分成m组,需要m-1块隔板,将这n件物品和m-1块隔板排成一排,占n+m-1位置,从这n+m-1个位置中选m-1个位置放隔板,因隔板无差别,故隔板之间无序,是组合问题,故隔板有Cn+m-1 m-1种不同的方法,再将物品放入其余位置,因物品相同无差别,故物品之间无顺序,是组合问题,只有1种放法,根据分步计数原理,共有Cn+m-1 m-1×1=Cn+m-1 m-1种排法。

折叠 编辑本段 水果分篮问题

例2:有广西橘子,烟台苹果,莱阳梨若干,从中随意取出四个,问共有多少种不同取法?

问题等价于将四个水果放入三个不同的水果篮,且允许篮子为空,{这里是逆向思维逻辑}

将4+3=7个水果分为3个组,分组需2个隔板,隔板共有6个放置位置,

故有C(4+2, 2)个选择,即15种。

折叠 编辑本段 物品问题

例3将20个优秀学生名额分给18个班,每班至少1个名额,有多少种不同的分配方法?

分析:本题是名额分配问题,用隔板法.

解析:将20个名额分配给18个班,每班至少1个名额,相当于将20个相同的小球分成18组,每组至少1个,将20个相同的小球分成18组,需要17块隔板,先将20个小球排成一排,因小球相同,故小球之间无顺序,是组合,只有1种排法,再在20个小球之间的19个空档中,选取17个位置放隔板,因隔板无差别,故隔板之间无序,是组合问题,故隔板有C(19, 17)种不同的放法,根据分步计数原理,共有C(19 ,17)种不同的方法,因17块隔板将20个小球分成18组,从左到右可以看成每班所得的名额数,每一种隔板与小球的排法对应于一种分法,故有C(n-1, m-1)种分法.

对相同物品分配问题,注意某若干组能否为空,能为空和不能为空,方法不同,要体会和掌握.

阅读全文

为您推荐