隔板法(课堂PPT).ppt

隔板法又称隔墙法、插板法，是隔板法又称隔墙法、插板法，是处理名额分配处理名额分配、相同相同物体的分配物体的分配等排列组合问题的重要方法。等排列组合问题的重要方法。隔板法就是在n个元素间的（n-1）个空中插入 若干个（b）个板，可以把n个元素分成（b+1）组的方法。应用隔板法必须满足三个条件：（1）这n个元素必须相同（2）所分成的每一组至少分得一个元素（3）分成的组别彼此相异 一、将一、将n件相同物品（或名额）分给件相同物品（或名额）分给m个人（或位个人（或位置），每人（或位置）必须有物品问题置），每人（或位置）必须有物品问题例如：某校组建一球队需16人，该校共10个班级，且每个班至少分配一个名额,共有几种情况？解:C（16-1），（10-1）=C（15，9）=1816214400种 归纳：归纳：练习、将练习、将20个优秀学生名额分给个优秀学生名额分给18个班，每班至少个班，每班至少1个名额，有多少种不同的分配方法？个名额，有多少种不同的分配方法？二、二、将将n n件相同物品（或名额）分给件相同物品（或名额）分给m m个人（或位个人（或位置），允许若干个人（或位置）为空的问题置），允许若干个人（或位置）为空的问题.例例2、将将10个大小形状完全相同的小球放入个大小形状完全相同的小球放入3个不同个不同的盒子，允许有盒子为空，但球必须放完，有多少的盒子，允许有盒子为空，但球必须放完，有多少种不同的方法？种不同的方法？分析：本题中的小球大小形状完全相同，故这些分析：本题中的小球大小形状完全相同，故这些小球没有区别，问题等价于将小球分成三组，允小球没有区别，问题等价于将小球分成三组，允许有若干组无元素，用隔板法许有若干组无元素，用隔板法.归纳：归纳：练习：把8个相同的球放入4个不同的盒子，有多少种不同方法？应用应用1(1)12个相同的小球放入编号为个相同的小球放入编号为1、2、3、4的盒子中，问的盒子中，问每个盒子中至少有一个小球的不同放法有多少种每个盒子中至少有一个小球的不同放法有多少种?(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个、个、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 1、4 4个相同的球放入个相同的球放入3 3个不同的盒子中，不允许个不同的盒子中，不允许出现空盒有多少种不同的方法？出现空盒有多少种不同的方法？2 2、某市从、某市从8 8个中学的篮球队中选个中学的篮球队中选1212人组成该市的人组成该市的中学生篮球代表队，每校至少一人参加，名额中学生篮球代表队，每校至少一人参加，名额分配方案共有多少种？分配方案共有多少种？3 3、从、从5 5个学校选出个学校选出8 8名学生组成代表团，每校至名学生组成代表团，每校至少有一人的选法种数是多少？少有一人的选法种数是多少？4、变式：变式：多面手问题多面手问题例：翻译例：翻译8 8人，其中人，其中3 3人只会英语，人只会英语，2 2人只会日语，人只会日语，还有还有3 3人英语、日语都会，现从这人英语、日语都会，现从这8 8个人中选取个人中选取3 3名英语，名英语，2 2名日语翻译，有多少种不同的选法？名日语翻译，有多少种不同的选法？练习练习在在1010名工人中，有名工人中，有4 4人只能当钳工，人只能当钳工，4 4人只能当车人只能当车工，另外工，另外2 2人既能当钳工又能当车工，现从人既能当钳工又能当车工，现从1010人人中选出中选出4 4人当钳工，人当钳工，4 4人当车工，有多少种不同人当车工，有多少种不同的选法？的选法？