排列组合问题中的重复计算剖析.doc

排列组合问题中的重复计算剖析在解答排列组合问题中，易犯的错误是遗漏与重复遗漏多半比较明显，而重复较为隐蔽本文对一些隐蔽的重复计算错误举例剖析研究失误的原因，寻求补正和预防的方法例1 某天有六节不同的课，若第一节排数学，或第六节排体育，问共有多少种不同的排法？ 错解 数学排第一节的排法有种，体育排第六节的排法也有种，根据加法原理，第一节排数学或排体育的排法共有＋＝2＝240种剖析 在数学排第一节的排法中，存在着体育排第六节的排法，在排体育第六节的排法中，存在着数学排第一节的排法，它重复计算了数学排第一节，同时体育排第六节的排法，即多算种正确结果是：＋－＝216种例2 从4名男生3名女生中选3人成立科技小组，问当选者中至少有一名男生和一名女生的选法有几种？错解 先选一名男生，有种选法，再选一名女生，有种选法，最后从余下的5名学生中选一名有种选法，故共有选法＝60种剖析 上述解法中，每一种选法都符合要求，但是否有重复计算呢？为此我们不妨设4名男生为A1，A2，A3，A4，3名女生为B1，B2，B3，把上面选法中含有一名男生的选法分为4类在含有男生A1的一类的选法有：A1，B1，A2，即先选A1，再选B1，最后选A2；在含有男生A2的一类中有A2， B1，A1，即先选A2，再选B1，最后选A1。

显然这两种选法被重复计算了因此上述解法是错误的错误的原因在于没有将符合要求的选法进行正确分类，分类要不重不漏正解 以男生人数分类，则符合条件的有且仅有两类，一类是男生一名女生两名，有种选法，另一类是男生两名女生一名，有故共有＋＝30种例3 n个不同的球放入n－1个不同的盒子，假设每个盒子都有足够大的容量，问每个盒子中至少有一个球的放法共有多少种？错解 先在每盒子中放入一球共有种放法，再将剩下的一球放入，有n－1种放法由乘法原理，共有放法（n－1）＝（n－1）n！种.剖析 将这n个球和n－1个盒子均依次编号，设先在每盒中放入一球时，有一种放法是第I号盒子恰好放入第I号球，其中I＝1，2，…，n－1，然后再考虑剩下的第n号球的放法，假设第n号球恰好放入第1号盒，这样，除1号盒中放有第一号与第n号两个球外，其余各盒均只放有一个与盒子同号的球，若先在每盒中放入一球时，第n号球恰好放入第1号盒，，而其余各盒所放的球均与盒子同号，这样，再将剩下的1号球放入盒中时，必有一种放法是恰好放入1号盒，这时，出现与前一次完全相同的结果，但在上面的解法中被当成两种不同的放法来计算，故重复正确的解法是：先从n个球中任取2个组成一组，共有种方法；然后把这2个球当作1份，另外n－2个球每个球算1份，共有n－1份，把这n－1份分放在n－1个盒子中，且使每盒中恰有1份，共有种放法，由乘法原理，符合题意的放法种数为＝n！。