隔板法在排列组合中的应用

王录远

排列组合在历年来的高考中占的比分很高，在20分左右.它联系实际、题型多变、解法灵活、能力要求高、每年高考得分率极低.而排列组合中的分配问题，是排列组合问题中的重点与难点，对于排列组合中涉及相同物品的分配或名额分配的问题，若采用隔板法，则可起到简化解题的功效.下面笔者通过三种类型题来介绍一下隔板法的应用.

类型一：10个相同的排球分给三个班级，每个班级至少得一个排球的分法.

解析：将10个相同的排球排成一列，则10个排球之间出现9个空当，用2块隔板插入空当，将其分成3份，每份至少一个排球，每个班级依次分到对应位置的排球，因此在9个空当插入2块隔板，共有C3-110-1=C29=36种分法.

点评：对于相同元素的分组分配问题，常规解法繁琐且易错，若掌握隔板法，则操作方便且易懂.

一般模式：将n件相同物品（或名额）分给m（m

【例1】学校在高二年级的8个班中，组织一个12个人的年级学生分会，每班要求至少1人，名额分配方案有多少种？

解析：因为该题满足类型一的三个条件，所以可用隔板法，故共有C8-112-1=C711种分法.

类型二（添加球数隔板法）：10个相同的排球分给三个班级，允许有些班级没有分到排球的分法.

解析：因为允许有班级没有分到排球，没有满足隔板法具备的条件（2）.为了满足“每人至少分到一个排球”的条件，可先从每班收回一个排球，这样原来打算不分的，也要还一个排球回去，问题就转化成“13个排球分配给3个班，每个班至少得到一个排球，有多少种分法”，用隔板法求解，则共有C3-113-1=C212=66

种分配方法.

点评：本例通过添加球数，将问题转化为类型一中的隔板法问题.

一般模式：将n件相同物品（或名额）分给m（m

【例2】求（a+b+c）9的展开式中共有多少项？

解析：由于展开式的每一项都形如maxbycz且x+y+z=9，其中x、y、z都是非负整数，因此问题等阶于求方程x+y+z=9有多少组不同的非负整数解，因为x+y+z=9，所以问题转化为“把9个相同的球分配给三个班，允许有些班没有分到球，共有几种分配方案”，用添加球数隔板法求解，则共有C3-19+3-1=C211=55种分配方案.

类型三（减少球数隔板法）：10个相同的排球分给三个班级，每个班级至少得两个排球的分法.

解析：因为每个班级至少有两个排球，没有满足类型一具备的条件（2）.为了满足这一条件，可给每个班级先分一个排球，这样就转化成“7个排球分配给3个班级，每个班级至少有一个排球，有多少种分法”的问题，用隔板法求解，则共有C3-17-1=C26=15种分配方法.

点评：本例通过减少球数，将问题转化为类型一中的隔板法问题.

一般模式：将n件相同物品（或名额）分给m（m

【例3】12个相同的小球放入编号为1、2、3、4的盒子中，要求每个盒子中的小球数至少为2个，问有多少种放法？

解析：题干中要求每个盒子中的小球数至少为2个，这满足类型三的减少球数隔板法，我们可以直接利用公式解决，故共有C4-112-4-1=C37=35种放法.

【例4】20个不加区别的小球放入编号为1号、2号、3号的三个盒子里，要求每个盒内的球数不小于盒子的编号数，问有多少种放法？

解法一：先取出3个球，其中1个球放入2号盒内，再将其余2个球放入3号盒内.则此题转化为“17个球放入3个不同的盒内，每盒至少一球，有多少种放法”，即转化为类型一的隔板法，故有C3-117-1=C216=120种放法.

解法二：先取出6个球，其中1个球放入1号盒内，2个球放入2号盒内，其余3个球放入3号盒内.则此题转化为“14个球放入3个不同盒内，允许有些盒没有分到球，有多少种放法”，即转化为类型二的添加球数隔板法，故有C3-114+3-1=C216=120种放法.

【例5】某人准备用7步走完一个10级的台阶，且每步至多可跨3级台阶，则此人共多少种不同的走法？

解析：令此人每一步所跨的台阶数依次为x1，x2，…x7，则x1+x2+…+x7=10，由隔板法可知C69=84，又因为有“每步至多跨3级”的要求，则排除

7种

一步跨4级的可能性，所以此人共有84-7=77种走法.

总之，对于排列组合中涉及相同物品的分配或名额分配的问题，即处理相同元素有序分组的问题时，我们都可采用隔板法.采用隔板法会取得事半功倍的效果.

（责任编辑钟伟芳）