中图分类号：G4 排列组合应用题是现行中学数学教学大纲的一项重要内容。递推法是解排列组合应用题的一个重要方法，许多问题用这一方法来解显得精练简洁，并往往能得到解决同类问题的通用解法或得到一个应用较广的递推公式。
（1994年高考题）同室4人各写一张贺年卡，先集中起来，然后每人从中拿一张别人送出的贺年卡，则4张贺年卡不同的拿法有
A.6种 B.9种 C.11种 D.23种
下面介绍包括“构造法”在内的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）四个人均拿到自己写的贺年卡的情况：这种情况有1种。
（2）有且只有两个人拿到自己写的贺年卡的情况：有C42×1=6种。
（3）有且只有一个人拿到自己写的贺年卡的情况：有C41×2=8种。
故共有：24-1-6-8=9（种）
“构造法”运用巧妙，但这种解法比较难思考，有较大的局限性，也比较难进一步推广，假如把4个人改为5个人、6个人或更多的，用“构造法”恐怕很复杂。经深入研究和探讨，发现用递推的思想解这道题，可以找到一般的递推关系，并可以利用这种递推关系解决更为复杂的一些问题。
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 （1）
考察在dn中的排列，它们都是2I2 I3… In的形式，其中Ij≠j，j=2，3，…，n.我们进一步把这些排列分成两类，称I2=1的为第一子类，并把其中的排列个数记为dnˊ；称I2≠1的为第二子类，它的排列个数记为dn〞，那么有 dn= dnˊ+ dn〞 （2）
在第一子类中的排列具有21 I3I4… In的形式，Ij≠j，j=3，4，…，n。所以dnˊ就是3，4，…，n，这n-2个元素的错位排列数Dn-2。在第二子类中的排列具有2I2 I3… In的形式，其中I2≠1，Ij≠j，j=3，4，…，n。所以dn〞就是1，3，4，…，n，这n-1个元素的错位排列数Dn-1。因此得到 dn = Dn-2 +Dn-1 （3）
把（3）代入（1）得Dn=（n-1）（Dn-2 +Dn-1）
于是我们得到递推公式 （4）
Dn=（n-1）（Dn-2 +Dn-1）
D1=0，D2=1
解法五：利用递推公式（4），我们有
D3=（3-1）（D1 +D2）=2×（0+1）=2，
D4=（4-1）（D2 +D3）=3×（1+2）=9，
故有9种方法。
显然，与前述数种方法相比，递推法更具有一般性，利用递推公式（4），我们还可以较易地解决一些中学里常见的排列组合题。
例1.设有编号为1，2，3，4，5，6的六个球和编号为1，2，3，4，5，6的六个盒子，现将这六个球放入这六个盒内，要求每个盒子内投放一个球，并且恰好有两个球的编号与盒子编号相同，试求这样投放方法的种数。
解：从编号为1，2，3，4，5，6的六个球中任选两个的方法数为C62。我们把选出的两个球放在与它编号相同的盒子里，剩下的四个球的投放方法满足递推公式（4）的条件。所求的投放方法数为
C62×D4=15×9=135（种）。
例2.八人坐成一排，现要调换五个人的位置，其余三个人位置不动，共有（ ）种调换方法。
解：五个人调换位置，即五个人都不坐在原来的位置上。所以任意五个人调换位置的方法数D5满足递推公式（4）的条件。
由例1知D5=44。
∴共有C85×D5=56×44=2464（种）
另一方面，掌握递推的数学思想对解某些其它应用性问题也是很有帮助的。例如下面的问题用递推的思想来解答将很明了。
综观上述，可见运用递推法求解某些排列组合应用题，思路明了，并可以找到一般的递推关系用于解决同类问题，有助于培养逻辑思维能力。
