一道排列组合题的解法探讨
 
2006-06-21 11:10:28 1

   望城县靖港中学 熊安

  同室4人各写一张贺年卡,先集中起来,然后每人从中拿出一张别人送出的贺年卡,则4张贺年卡不同的拿法有(1994年高考题):

  A.6种B.9种C.11种D.23种

  该文可用“构造法”给出解答。但这种解法有较大的局限性,难进一步推广,假如把4个人改为5个人、6个人或更多的,用“构造法”恐怕很复杂。经常深入研究和探讨,发现用递推思维的思想解这道题,可以找到一般的递推关系,并利用这种递推关系解决更复杂的一些问题。下面介绍包括“构造法”在内的5种解法。

  1.构造法:构造法的关键是针对问题的实际意义,构造一个三棱锥,记这4个人为A,B,C,D,每人所写的贺年卡对应为a,b,c,d(如左图),设法把每个人和他写出的贺年卡同放在三棱锥的一个顶点上,则4个顶点刚好分配完。规定每条棱表示2种顺序拿法。例如AB表示A拿b或B拿a。根据题意全部拿法分为两类:第一类是4人中有2人交换着拿,例如A拿b,B拿a,这时另2人也只能交换着拿,这种拿法在三棱锥中表示为成异面直线关系的两条棱,而这样的棱在三棱锥中共有3对,所以这类拿法有3种。第二类是4人顺序循环拿,例如A拿b,B拿c,C拿d,D拿a(或反序循环:A拿d,D拿c,C拿b,B拿a),这在图中表示为4条首尾顺次相接的棱构成的空间四边形ABCD。而余下的2条棱也恰好为1对“异面直线棱”。由于三棱锥共有3对这样的“异面直线棱”,所以图中共有3个不同的空间四边形,而每个四边形有2种循环序表示2种拿法。故第二类拿法共有3×2=6种。因此,两类拿法共表示9种不同的分配方式。

  2.列举法:当问题比较简单时可做具体分析。设4人A,B,C,D,写的贺年卡分别记为a,b,c,d。可从第一个人A考虑起,当A取b时,其它三人可去的情况见右表。由表可知A取b时有三种分配方法。同样A取c,d时也各有三种方法。这样由A的取法可分三类,由加法原理,得3+3+3=9(种)。

  3.直接法:用乘法原理。即让四人依次拿一张贺年卡,分四步进行。

  第一步:A先拿有3种方法;

  第二步:叫被A取走的他写的贺年卡的人再拿,也有三种取法;

  第三步:剩下的两张贺年卡中至少有一张是还没拿的两个人中的某个人写的,让这个人拿只有一种拿法;

  第四步:一张贺年卡一个人只有一种拿法。

  由乘法原理得:3×3×1×1=9(种)

  4.间接法:先不考虑要求,四个人拿四张不同的贺年卡,每人一张的方法数为P44=24种,其中不合要求的情况有:

  ⑴四个人均拿到自己写的贺年卡的情况:这种情况有1种。

  ⑵有且只有两个人拿到自己写的贺年卡的情况:有C42×1=6种。

  ⑶有且只有一个人拿到自己写的贺年卡的情况:有C41×2=8种。

  故共有:24-1-6-8=9(种)

  5.递推法:我们先把文中题目所涉及的问题换一种说法。即把1,2,3,4四个数字排成一排,使得I不能排在I位,I=1,2,3,4。求符合条件的排列数。

  我们再把这问题推广为一般的模式。把1,2,3,…,n这n个数字排列成一排,使得I不能排在I位,I=1,2,3,…,n。求符合条件的排列数。

  设n个数字的这种排列数为Dn,若能推出Dn的通项公式或递推公式,那么上面的问题就迎刃而解且能解决一些较为复杂的问题。利用递推的数学思想分析如下:

  容易知道D1=0,D2=1,n≥3,考虑1,2,3,…n这个n数字的所有符合条件的排列数(以下称为n个元素的错位排列数)。我们根据在排列中的第一位数字是2,3,…n,而将这些排列分成n-1类,显然每一类的排列数相等。令dn表示第一位是2的排列数。那么有Dn=(n-1)dn⑴

  考察在dn中的排列,它们都是2I2I3…In的形式,其中Ij≠j,j=2,3,…n。我们进一步把这些排列分成两类,称I2=1的为第一子类,并把其中的排列个数记为dn';称I2≠1的为第二子类,它的排列个数记为dn'',那么有dn=dn'+dn''⑵

  在第一子类中的排列具有21I3I4…In的形式,Ij≠j,j=3,4,…n。所以dn'就是3,4,…,n,这n-2个元素的错位排列数Dn-2。在第二子类中的排列具有2I2I3…In的形式,其中I2≠1,Ij≠j,j=3,4,…,n。所以Dn''就是I,3,4,…,n,这n-1个元素的错位排列数Dn-1。因此得到Dn=Dn-2+Dn-1⑶把⑶代入⑴得Dn=(n-1)=(Dn-2+Dn-1)于是我们得到递推公式⑷Dn=(n-1)=(Dn-2+Dn-1)n≥3D1=0,D2=1解法五:利用递推公式⑷,我们有D3=(3-1)=(D1+D2)=2×(0+1)=2,D1=(4-1)=(D2+D3)=3×(1+2)=9,故有9种方法。

  显然,与前述数种方法相比,递推法更具有一般性,利用递推公式⑷,我们还可以较易地解决一些中学里常见的排列组合题。

 

  

(责编:刘金兰 作者:)

关闭窗口