隔板法课件.ppt

1隔板法又称隔墙法、插板法，是隔板法又称隔墙法、插板法，是处理名额处理名额分配分配、相同物体的分配相同物体的分配等排列组合问题的等排列组合问题的重要方法。重要方法。应用插板法必须满足三个条件：应用插板法必须满足三个条件：（1）这这n个元素必须互不相异个元素必须互不相异（2）所分成的每一组至少分得一个元素所分成的每一组至少分得一个元素(3)分成的组别彼此相异分成的组别彼此相异21、将、将n件相同物品（或名额）分给件相同物品（或名额）分给m个人（或位个人（或位置），每人（或位置）必须有物品问题置），每人（或位置）必须有物品问题3例例1、将、将20个优秀学生名额分给个优秀学生名额分给18个班，每班至少个班，每班至少1个名额，有多少种不同的分配方法？个名额，有多少种不同的分配方法？4例2有8个相同的球放到三个不同的盒子里，允许盒子为空，共有（）种不同方法.A35B28C21D45一、一、将将n n件相同物品（或名额）分给件相同物品（或名额）分给m m个人（或位个人（或位置），允许若干个人（或位置）为空的问题置），允许若干个人（或位置）为空的问题.5一、一、将将n n件相同物品（或名额）分给件相同物品（或名额）分给m m个人（或位个人（或位置），允许若干个人（或位置）为空的问题置），允许若干个人（或位置）为空的问题.（可以逐次插入再消序可以逐次插入再消序）例例1、将将20个大小形状完全相同的小球放入个大小形状完全相同的小球放入3个不同个不同的盒子，允许有盒子为空，但球必须放完，有多少的盒子，允许有盒子为空，但球必须放完，有多少种不同的方法？种不同的方法？分析：本题中的小球大小形状完全相同，故这些分析：本题中的小球大小形状完全相同，故这些小球没有区别，问题等价于将小球分成三组，允小球没有区别，问题等价于将小球分成三组，允许有若干组无元素，用隔板法许有若干组无元素，用隔板法.6应用应用1(1)12个相同的小球放入编号为个相同的小球放入编号为1、2、3、4的盒子中，问的盒子中，问每个盒子中至少有一个小球的不同放法有多少种每个盒子中至少有一个小球的不同放法有多少种?(2)12个相同的小球放入编号为个相同的小球放入编号为1、2、3、4的盒子中，每的盒子中，每盒可空，问不同的放法有多少种盒可空，问不同的放法有多少种?(3)12个相同的小球放入编号为个相同的小球放入编号为1、2、3、4的盒子中，要的盒子中，要求每个盒子中的小球数不小于其编号数，问不同的求每个盒子中的小球数不小于其编号数，问不同的放法有多少种放法有多少种?7解：解：(1)将将12个小球排成一排，中间有个小球排成一排，中间有11个间隔，个间隔，在这在这11个间隔中选出个间隔中选出3个，放上个，放上“隔板隔板”，这样，这样每一种隔板的插法，就对应了球的一种放法，即每一种隔板的插法，就对应了球的一种放法，即每一种从每一种从11个间隔中选出了个间隔中选出了3个间个间隔的组合对应隔的组合对应于一种放法，所以不同的放法有于一种放法，所以不同的放法有=165(种种)。（2)由隔板法可知：由隔板法可知：=455种。种。(3)解法一：用解法一：用(1)的处理问题的方法。的处理问题的方法。将将1个、个、2个、个、3个小球放入编号为个小球放入编号为2、3、4的盒子中，将余的盒子中，将余下的下的6个小球放在个小球放在4个盒子中，每个盒子至少一个个盒子中，每个盒子至少一个小球，据小球，据(1)有有=10(种种)。82、从、从5个学校选出个学校选出8名学生组成代表团，每校至少名学生组成代表团，每校至少有一人的选法种数是多少？有一人的选法种数是多少？解析：按常规，从解析：按常规，从5个学校选个学校选8名学生，要考虑名学生，要考虑5个学校人员的分配，需要分类讨论，太繁琐。个学校人员的分配，需要分类讨论，太繁琐。逆向思考，假设逆向思考，假设8名学生的代表团已组建好，现名学生的代表团已组建好，现将其返回到将其返回到5个学校，个学校，每校至少一人，每校至少一人，这样这样问题转化为将问题转化为将8个学生分成个学生分成5组，每组至少一人，组，每组至少一人，在上图中，在上图中，7个空档中插入个空档中插入4块隔板即可将其分块隔板即可将其分成成5组，故有组，故有=35种选法。种选法。93:将10个相同的小球放人编号为1，2，3的三个盒子中，要求每个盒子中的小球数不小于该盒子的编号数，则不同的放法共有多少种?分析：先在2号盒子内放人1个小球，在3号盒子内放人2个小球，则原题意可转化为：“将7个相同的小球放入编号为1，2，3的三个盒子中，每个盒子中至少1个小球，不同的放法共有多少种?”，可知共有C(6,2)=15种不同的放法10