巧用隔板法解相同元素的组合问题ppt课件.ppt

巧用隔板法解相同元素的组合问题,广东省深圳市建文中学高中数学老师欧阳文丰制作,隔板法：又称剪截法。,在排列组合中，对于将不可分辨的球装入到可以分辨的盒子中而求装入方法数的问题，常用隔板法。 解题思路： n个 相同小球放入m(mn)个盒子里,要求每个盒子里至少有一个小球的放法等价于n个相同小球排列成一排从间隙里插入m-1个隔板形成m段.因此放法数为: 。 注意事项：隔板法的应用条件有二。 首先, n个 相同小球放入m(mn)个不同盒子里, 这是最重要的条件, 否则不能运用隔板法。 其次, 每个对象至少分得一个, 这样就可以在n个相同小球串成一串从间隙里插入m-1个隔板, 依此将这些元素分给不同的对象。,例题学习,例1 10个三好学生名额分到7个班级，每个班级至少一个名额，有多少种不同分配方案？解析：10个名额分到7个班级，就是把10个名额看成10个相同的小球分成7堆，每堆至少一个，可以在10个小球的9个空位中插入6块木板，每一种插法对应着一种分配方案，故共有不同的分配方案为 种.,例题学习,例2：某单位订阅了30份学习材料发放给3个部门，每个部门至少发放9份材料，问一共有多少种不同的发放方法?A.7 B.9 C.10 D.12解析：选C。分析题意, 将30份相同的学习材料分给不同的部门, 满足隔板法应用的条件, 棘手的在于每个部门至少9份, 如何转化为每个部门至少1份呢?这时我们就可以每个部门先发8份, 再将剩下的6份发给三个部门, 每个部门至少发1份, 这样就满足题意了, 所以这道题的答案是 , 10种方法。,例题学习,例3：将7个大小形状相同的小球放进三个不同的盒子，允许有盒子为空，但球必须放完，问共有多少方法?A.12 B.24 C.36 D.48解:将7个小球分成三组需要两块隔板, 因为允许有盒子为空，不符合隔板法的原理。那就人为的再加上3个小球, 保证每个盒子都至少分到一个小球, 这样就符合隔板法的要求了, 等到分完后再把3个小球拿走就可以了。这样就变成了求10个小球放入3个不同的盒子, 每个盒子至少放1个小球的放法了。即共有 =36种放法。,例题学习,例4.某校准备参加今年高中数学联赛,把16个选手名额分配到高三年级的1-4 个教学班,每班的名额不少于该班的序号数,则不同的分配方案共有_种.解： 问题等价于先给2班1个，3班2个，4班3个，再把余下的10个相同小球放入4个盒子里,每个盒子至少有一个小球的放法种数问题. 将10个小球串成一串，截为4段有 种截断法，对应放到4个盒子里. 因此，不同的分配方案共有84种 .,例题学习,例5(2002年全国高中数学联赛试题5)已知两个实数集合Aa1，a2，a100与Bb1，b2，b50，若从A到B的映射f使得B中每个元素都有原象，且 f(a1)f(a2)f(a100)则这样的映射共有( ）(A) (B) (C) (D),本题等价于将集合A划分为50个非空的子集，我们将A中的元素作如下排列：a1、a2、a3、a99、a100它们之间共有99个空，在这99个空中插入49个隔板，即可将其分为50组，共有C种插法，不妨设b1b2b50,注意到f(a1)f(a2)f(a100)，所以以上对集合A的每一个划分都与b1、b2、b50是一一对应的，故这样的映射共有 个。,例题学习,例6. 求方程 的正整数解的个数。分析将10个球排成一排，球与球之间形成9个空隙，将两个隔板插入这些空隙中（每空至多插一块隔板），规定由隔板分成的左、中、右三部分的球数分别为x、y、z之值（如下图）。则隔法与解的个数之间建立了一一对立关系，故解的个数为 （个）。,练习题,1、一串糖葫芦共6颗，每颗大小形状都相同，分给三个小朋友吃，每个小朋友至少分得一颗，问共有多少种分法?A.4 B.6 C.8 D.102、某校准备参加今年高中数学联赛,把16个选手名额分配到高三年级的1-4 个教学班,每班至少一个名额,则不同的分配方案共有_种.3、将20个相同的小球放入编号分别为1，2，3，4的四个盒子中，要求每个盒子中的球数不少于它的编号数，求放法总数。,练习题,4、若集合A=1,2,3,4,5,B=6,7,8, 从A到B的映射f中，满足 f(a1)f(a2)f(a3) f(a4)f(a5)则这样的映射共有多少个映射？5、求方程 的非负整数解的个数。,