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

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

《排列组合问题中的重复计算剖析.doc》由会员分享，可在线阅读，更多相关《排列组合问题中的重复计算剖析.doc（3页珍藏版）》请在冰点文库上搜索。

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

在解答排列组合问题中，易犯的错误是遗漏与重复。

遗漏多半比较明显，而重复较为隐蔽。

本文对一些隐蔽的重复计算错误举例剖析。

研究失误的原因，寻求补正和预防的方法。

例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种

例3n个不同的球放入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！