欢迎来到天天文库
浏览记录
ID:57250275
大小:441.50 KB
页数:14页
时间:2020-08-07
《隔板法知识讲解.ppt》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
1、隔板法隔板法又称隔墙法、插板法,是处理名额分配、相同物体的分配等排列组合问题的重要方法。隔板法就是在n个元素间的(n-1)个空中插入若干个(b)个板,可以把n个元素分成(b+1)组的方法。应用隔板法必须满足三个条件:(1)这n个元素必须相同(2)所分成的每一组至少分得一个元素(3)分成的组别彼此相异一、将n件相同物品(或名额)分给m个人(或位置),每人(或位置)必须有物品问题例如:某校组建一球队需16人,该校共10个班级,且每个班至少分配一个名额,共有几种情况?解:C[(16-1),(10-1)]=C(15,9)=1816214400种归纳
2、:练习、将20个优秀学生名额分给18个班,每班至少1个名额,有多少种不同的分配方法?二、将n件相同物品(或名额)分给m个人(或位置),允许若干个人(或位置)为空的问题.例2、将10个大小形状完全相同的小球放入3个不同的盒子,允许有盒子为空,但球必须放完,有多少种不同的方法?分析:本题中的小球大小形状完全相同,故这些小球没有区别,问题等价于将小球分成三组,允许有若干组无元素,用隔板法.归纳:练习:把8个相同的球放入4个不同的盒子,有多少种不同方法?应用1.(1)12个相同的小球放入编号为1、2、3、4的盒子中,问每个盒子中至少有一个小球的不同
3、放法有多少种?(2)12个相同的小球放入编号为1、2、3、4的盒子中,每盒可空,问不同的放法有多少种?(3)12个相同的小球放入编号为1、2、3、4的盒子中,要求每个盒子中的小球数不小于其编号数,问不同的放法有多少种?解:(1)将12个小球排成一排,中间有11个间隔,在这11个间隔中选出3个,放上“隔板”,这样每一种隔板的插法,就对应了球的一种放法,即每一种从11个间隔中选出了3个间隔的组合对应于一种放法,所以不同的放法有C(11,3)=165(种)。2)由隔板法可知:C(15,3)=455种。(3)解法一:用(1)的处理问题的方法。将1个
4、、2个、3个小球放入编号为2、3、4的盒子中,将余下的6个小球放在4个盒子中,每个盒子至少一个小球,据(1)有C(5,3)=10(种)。解法(2):用(2)的处理问题的分法。将1个、2个、3个、4个小球分别放在编号为1、2、3、4的盒子中,将余下的2个小球放在四个盒子中,每盒允许有空盒,据(2)有C(5,3)=10(种)。隔板法1、4个相同的球放入3个不同的盒子中,不允许出现空盒有多少种不同的方法?2、某市从8个中学的篮球队中选12人组成该市的中学生篮球代表队,每校至少一人参加,名额分配方案共有多少种?3、从5个学校选出8名学生组成代表团,
5、每校至少有一人的选法种数是多少?4、变式:多面手问题例:翻译8人,其中3人只会英语,2人只会日语,还有3人英语、日语都会,现从这8个人中选取3名英语,2名日语翻译,有多少种不同的选法?练习在10名工人中,有4人只能当钳工,4人只能当车工,另外2人既能当钳工又能当车工,现从10人中选出4人当钳工,4人当车工,有多少种不同的选法?
此文档下载收益归作者所有