“隔板法”巧解排列组合题

罗忠菊

摘 要：“隔板法”适用于相同元素的分配问题，如投球进盒、名额或指标的分配、部分不定方程的整数解的组数等，解决时通常设计一个问题情景，构造一个隔板模型。将复杂的问题简单化，抽象的问题具体化，从而实现解题的目的。

关键词：隔板；空档；问题情景；构造；模型；正整数解；排列组合

“隔板法”是解决组合问题中关于若干个相同元素的分组问题的一种常用方法，用这种方法解决此类问题，过程简洁明了，富有创意性和趣味性。这类问题的类型就是把n（n≥1）个相同的元素分配到k（1≤k≤n）个不同的组，使得每组中都至少有一个元素，求一共有多少种不同的分法的问题。在这n个相同元素中找“空档”（不含两端），在n-1个“空档”中插入k-1个隔板，把n个元素分成k“堆”，把“堆”看作排列组合中的元素，这样问题就用Ck-1n-1来解决。直接应用“隔板法”必须满足三个条件：

①这n个元素必须相同；

②所分成的每一组至少分得一个元素；

③分成的組别彼此相异。

“隔板法”适用于相同元素的分配问题，如投球进盒、名额或指标的分配、部分不定方程的整数解的组数等，解决时通常设计一个问题情景，构造一个隔板模型。将复杂的问题简单化，抽象的问题具体化，从而实现解题的目的。

【例1】 高二年级8个班级协商组成年级篮球队，共需10名队员，每个班级至少要出一名，有多少种不同的组成方式？

【分析】 将10名队员理解成10个相同的球，排成一列，共形成9个空档，设想有7块隔板，将排成一列的10个球隔成8段，注意：任意两块隔板不能相邻，只能插入空档，在9个空档中插入7块隔板，故有C79=36（种）。这个问题也可转化为求不定方程x1+x2+…+x8=10，有多少组不同的正整数解。

【例2】 不定方程x+y+z+w=10有多少组正整数解？

【分析】 我们设想有10个相同的球排成一列，共形成9个空档，可以理解为有3块隔板，将排成一列的10个球隔成4段，注意：任意两块隔板不能相邻，只能插入空档，在9个空档中插入3块隔板，故有C39=84组正整数解。

对某些不符合上述“隔板法”条件的问题可以通过一些技巧转化为符合条件的隔板问题。

技巧一：添加球数用“隔板法”

【例3】 不定方程x+y+z+w=10有多少组非负整数解？

【分析】 注意到x、y、z、w可以为0，故例2解法中的限定“每个空档至多插入一块隔板”就不成立了，怎么办呢？只要添加4个球，给x、y、z、w各一个球。这样原问题就转化为求不定方程x+y+z+w=14的正整数解的组数，故方程解的组数为C313=286。

【评述】 本例通过添加球数，将问题转化为例2中的典型“隔板法”问题。

【例4】 将9个相同的球分给3个人，允许有人不取，但必须分完，有多少种分法？

问题转化为：9个相同的球分给编号为1，2，3的盒子，允许有盒子为空，但必须分完，有多少种分法？

【解法一】 将9个球排成一列，包括两端一共有10个空档，因为这里允许有盒子为空，就是隔板可以“挤进”同一个空档里，所以不能以空档计算。将2个隔板插入这些空档中，则每一种隔板位置对应一种分法。这里球和隔板共有11个，则有C211=55种分法。

【解法二】 添加3个球，给3个人每人一个，问题转化为：12个相同的球分给3个人，每人至少分一个球，且必须分完，有多少种分法？也就是将12个球排成一列，有11个空档，插入2块隔板分成三段，则有C211=55种分法。

【评述】 这个问题的解法是典型的玻色─爱因斯坦（BoseEinstein）统计模型：要将n（n≥1）个相同的球放入k（1≤k≤n）个不同的盒子，每盒所放球数不限，有多少种不同放法？用组合公式Ck-1n+k-1来解决。

技巧二：减少球数用“隔板法”

【例5】 将9个相同的球放入编号为1，2，3的盒子中，要求每个盒子中的球数不少于它的编号数，有多少种放法？

【分析】 先在编号1，2，3的盒子内分别放入0，1，2个球，剩下6个相同的球，问题转化为：将6个相同的球放入编号为1，2，3的盒子里，每个盒子至少有一个球的问题。

剩下6个相同的球排成一列，共形成5个空档，可以理解为有2块隔板，将排成一列的6个球隔成3段，每段至少有1个，则有C25=10（种）。

【评述】 本例通过减少球数，使得每个盒子中至少放入一个球，将问题转化为典型“隔板法”问题。

以上是我从教学实际中列举的几个用“隔板法”解决的排列组合题，解题时通常设计一个问题情景，构造一个隔板模型，套用公式Ck-1n-1或Ck-1n+k-1，使解题过程简洁明了，富有创意性和趣味性。

参考文献：

[1]徐帮利.巧用隔板法解排列组合题[J].数学爱好者（高考版），2007，（12）.

[2]程小芳.“隔板”法与一类排列组合题[J].中学数学教学，2006，（04）.