4.3插空法与隔板法.ppt

插空法与隔板法 主讲 陈蕾 1．掌握插空法、隔板法概念，注重两种方法的异同. 2．掌握利用插空法、隔板法解决排列组合问题.（重点） 插空法：指在解决对于某几个元素要求不相邻的问题， 先将其他元素排好，再将指定的不相邻元素插入已安排 好元素的间隙或两端位置 若有ABCDE五人排队，要求AB两人必须不站在一起，有多少种方法？ 解析：题中要求AB两人不站在一起，所以可以 先排除A和B之外的3个人排成一排方法数 ， 然后再将A和B分别插入其余3人排队所形成的4个空中， 也就是说从4个空中挑出两个并排上两个人， 其方法数为 ，因此总数为 . 解析：甲乙相邻，可以捆绑看作一个元素，但这个整体元素 又和丙不相邻所以先不排这个甲乙丙，而是先排剩下的5个人， 方法数为 ，然后再将甲乙构成的整体元素及丙这两个元素 插入到此前5人所形成的6个空里，方法数为 ， 另外甲乙两个人内部还存在排序要求为 。 故方法数为 8人排成一队，要求甲乙必须相邻且与丙不相邻，有多少种方法？ 练习： 隔板法：指在解决若干相同元素分组，要求每组 至少一个元素，采用将比所需分组数目少1的板插入 元素之间形成分组的解题策略。 有9颗相同的糖，每天至少吃一颗，要四天吃完，有多少种吃法？ 解析：只需要用3个板插入到9颗糖形成的8个内部空隙，将9颗糖 分成4组且每组数目不少于1 即可。因而3个板互不相邻， 其方法数为 练习： 8个完全相同的球放到3个不同的盒子，有多少种方法？ 解析：此题中没有要求每个盒子中至少放一个球。 因此解法上不同于上面的插板法，但依旧是插入2个板，分成3组。 但在分组的过程中，允许两板之间没有球。其考虑思维为插入两块板后，与原来的8个球一共10个元素。所有方法数实际是这10个元素的一个队列，但因为球之间无差别，板之间无差别，所以方法数实际是这10个元素所占的10个位置中挑2个位置放上2个板，其余位置全部放球即可。因此方法数为 *