排列组合问题中的重复“隐患”

例50件产品中有4件次品，现从中任意抽取5件，问至少抽到3件次品的取法有几种？

错解： 根据分步计数原理，分两步完成.第一步，先确保有3件次品，从4件次品中取3件，有[C4][3]种取法；第二步，从余下的47件产品中任取2件，有[C47][2]种不同的取法，所以共有[C4][3]・[C47][2]=4324种不同取法.

错因分析： 上解包含了一种极具隐蔽性的重复错误.为了说明这个问题，我们不妨将4件次品分别设为A1，A2，A3，A4，46件正品分别设为B1，B2，B3，…，B46.按错解中的取法，可能会出现以下情况：（1） 第一步抽出A1，A2，A3，第二步抽出A4，B1；（2） 第一步抽出A1，A2，A4，第二步抽出A3，B1. 这两种情况虽然抽取顺序不同，但结果相同，都是{A1，A2，A3，A4，B1}，应属于同一种取法，而错解却将它当成了两种取法.错误的实质是对A1，A4按抽取顺序的先后进行了隐性排列，造成了重复.明白了问题所在，我们就不难得出正确解法.

正解1： [C4][3][C47][2]种取法中有重复，因此可减去重复的取法，求出答案.分析可知，当4件次品是分第一次3件、第二次1件两次取出时，第二次取出的1件次品总会和第一次取出的3件次品中的1件因隐性排列产生重复，因此，重复的取法共有[C3][1][C46][1]=138种，所以共有[C4][3][C47][2]-[C3][1][C46][1]=4324-138=4186种取法.

正解2： 用分类讨论的方法，将取法分成恰好取到3件次品和恰好取到4件次品两类.恰好取到3件次品有[C4][3][C46][2]种取法；恰好取到4件次品有[C4][4][C46][1]种取法，故共有[C4][3][C46][2]+[C4][4][C46][1]=4186种取法.

“重复”是求解排列组合问题中的常见错误，错解中出现的重复选取错误是常见的隐性重复错误之一.对于这类含有“至多”“至少”条件的问题，采用正解2所示的分类法求解，思路更清晰，掌握更容易，并能避免隐性排列的发生.

除了上面谈到的重复选取错误，排列组合问题中还包含以下几类常见的隐性重复错误.

重复分配错误. 分配问题属于典型的排列组合问题，在分配时也存在类似分步求解时可能产生的重复“隐患”.比如对于“将5本不同的书分给4名同学，每人至少一本，问共有几种分法”这个问题，有些同学这样解：先从5本书中取出4本，分给4名同学，再把剩下的1本书分给4人中的一人，得出[A5][4][A4][1]=480种分法.这种解法实际上和错解犯了同样的错误.比如甲同学第一次分到语文书、第二次分到数学书，和他第一次分到数学书、第二次分到语文书的结果是相同的，只能算一种分配方法.因此答案[A5][4][A4][1]=480种显然多算了一倍，正确答案是240种分法.

要避免重复分配错误，最好采用先分组后分配的方法，即把5本书分成4组，其中一组有两本，共有[C5][2]=10种分法，再分配给4人，所以共有[C5][2][A4][4]=240种方法.

重复分组错误. 在平均分组时，也容易发生分组顺序不同、但分组结果相同的重复错误.比如对于问题“将5本不同的书按2 ∶ 2 ∶ 1分成三组，问共有几种分法”，如果简单地用[C5][2][C3][2][C1][1]求解，就会出现这样的重复错误：（1）第一次分组后，语文书和数学书为一组，第二次分组后，物理书和历史书为一组，剩下的地理书为一组；（2）第一次分组后，物理书和历史书为一组，第二次分组后，语文书和数学书为一组，剩下的地理书为一组.（1）（2）实际是同一种情况.

要解决这个问题，最好在分组结束后除以平均分组个数的全排列数，消除因平均分组的顺序不同而产生的重复.上面这个“将5本不同的书按2 ∶ 2 ∶ 1分成三组”的例子中，平均分组的个数是2，故应有种分法.

重复运算结果. 在有关数字运算的排列组合问题中，常常会发生选取对象不同但运算结果相同的情况.比如对于问题“在1，2，3，4这4个数中任取两个数相加，问共有几个不同的结果”，同学们往往会直接用[C4][2]来解答，却忘了题中存在1+4=5，2+3=5这两种结果相同的情况.

要避免这类隐性重复错误，我们可用枚举法找出重复的个数，并从总数中减去重复的个数.

以上我们列举了排列组合问题中常见的重复“隐患”，其产生原因大多是因为题目要求的“共有几种不同的方法”与顺序无关，而分步求解却会产生不同的顺序，从而导致顺序不同但结果相同的重复错误.除了采取前面介绍的方法和策略来避免出错以外，同学们还应加强对题目的理解，将题目中较为综合的表述具体化、细化，比如将“至少从5个产品中取出3个”转化为“从5个产品中取出3个、4个或5个”，使问题成为我们熟悉的、需要运用分类讨论思想求解的模型，必要时可通过试验、画图、代入小数字简化等手段帮助思考.