为顺应“大众数学”的国际数学教育改革潮流，我国对排列组合知识的引入和应用介绍也越来越重视，解决这类问题的方法灵活，切入点多，且抽象性强，在做题过程中发生重复或遗漏现象不易被发现，所以成为学习难点之一。对此类问题的探讨有助于提高学生分析问题、解决问题的能力。除了课本介绍的常用方法外，用递推法来解某些排列组合应用题更具有一般性和规律性，鉴于这一方法在各类考试包括公务员考试和竞赛中应用越来越广泛，掌握和运用这种方法，就显得更加重要。
　　文[1]中有这样一道经典的排列组合问题：
　　同室4人各写一张贺年卡，先集中起来，然后每人从中拿一张别人送出的贺年卡，则4张贺年卡不同的拿法有（）．
　　A．6种B．9种C．11种D．23种
　　本题可用直接法（乘法原理）、间接法（四人逐一分析）、列举法（列表格）、构造法（构造三棱椎）和递推法作答。对前四种解法在此不一一赘述。经研究，发现用递推的思想解这道题，可以找到一般的递推关系，并可以利用这种递推关系解决同类型的的一些问题。下面详细介绍递推法。
　　递推法
　　我们先把文中题目所涉及的问题换一种说法．即把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类，显然每一类的排列数相等。令表示第一位是2的排列数。那么有Dn=（n-1）dn（1）
　　考察在dn中的排列，它们都是2I2I3…In的形式，其中，Ij≠j，j=2，3，…，n.我们进一步把这些排列分成两类，称I2=1的为第一子类，并把其中的排列个数记为dn'；称I2≠1的为第二子类，它的排列个数记为dn''，那么有dn=dn'+dn''（2）
　　在第一子类中的排列具有21I3I4…In的形式，Ij≠j，j=3，4，…，n。所以dn'就是3，4，…，n，这n-2个元素的错位排列数Dn-2。在第二子类中的排列具有2I2I3…In的形式，其中I2≠1，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组成形如a1a2a3a4a5的五位数，但, a1≠1,a2≠2,a3≠3,a4≠4,a5≠5试求这样的五位数的个数.(选自《名校名师数学教学与训练荟萃》，原文用分析法.)
　　解:设这样的五位数的个数为D5．由递推公式（4）
　　Dn=（n-1）（Dn-2+Dn-1）D1=0,D2=1
　　得D3=2，D4=9，D5（5-1）（2+9）=44．
　　故这样的五位数有44个．
　　例2．一牧羊人赶着一群羊通过99个关口，每过一个关口，守关人将拿走当时羊的一半，然后退还一只，过完这些关口后牧羊人只剩2只羊，问原来牧羊人赶多少只羊？
　　分析:每道关口的守关人留羊的方法相同，即留下当时羊的一半再退还一只，因而牧羊人剩下当时羊的一半多一只。设过第n关后牧羊人剩下an+1只羊，则过第n关前的羊数为an只，由分析可建立数列{an}的递推关系式：
　　an+1=+1．即：2an+1=an+2,
　　由递推关系式可得：an=2(an+1-1)．
　　将a100=2代入上式可得：a99=a98=…=a1=2,
　　即为牧羊人原来羊的只数——2只．
　　例3.有排成一行的ｎ个方格，用红、黄、蓝三色涂每个格子，每格涂一色，要求任何相邻的格不同色，且首尾两格也不同色，问有多少种涂法？（江苏省数学夏令营）
　　解：设共有an种涂法，易见a1=3,a2=6,a3=6，且当n≥4时，将ｎ个格子依次编号后，格1与格（n-1）不相邻．
　　 情形1：格（n-1）涂色与格1不同，此时格ｎ只有一色可涂，且前（n-1）格满足首尾两格不同色，故有种涂色方法．
　　情形2：格（n-1）涂色与格１相同，此时格（n-2）与格1涂色必然不同，不然，格（n-1）与（n-2）相同，于是前（n-2）格有an-2种涂色法．因为格ｎ与格1不同色，有两种涂色法，故共有2an-2种涂色法．
　　综上，可得递推公式：
　　 an=an-1+2an-2(n≥4)a1=3,a2=6,a3=6，
　　解得an=2n+2(-1)n．（n≥2，n∈N）
　　综上所述，运用递推法求解某些排列组合应用题，思路清晰，并可以找到一般的递推公式用于解决同类型的问题，既简洁又明了，有助于培养逻辑思维能力。
　　
　　参考文献：
　　[1]吉一凡.用构造法巧解排列组合题[J].数学通报,1997,(5)．
　　[2]赵玉勇.有条不紊—递推法破解难题[M].电脑报,2004,(7).
　　[3]卢开澄,卢华明.组合数学(第4版),清华大学出版社,2006,(12).