论文部分内容阅读
摘 要：排列组合问题是数学的重要知识之一，在公务员考试（国考）中也是必考题型，其中递推法是解决排列组合问题的一个重要方法，许多问题均可用此法来解，过程还显得精练与简洁，通常还能得到解决同类问题的通用解法或得到一个应用较广的递推公式。
关键词：构造法；递推法；错位排列；递推公式
中图分类号：G42 文献标识码：A 文章编号：1009-0118（2010）-12-0035-01
为顺应“大众数学”的国际数学教育改革潮流，我国对排列组合知识的引入和应用介绍也越来越重视，解决这类问题的方法灵活，切入点多，且抽象性强，在做题过程中发生重复或遗漏现象不易被发现，所以成为学习难点之一。对此类问题的探讨有助于提高学生分析问题、解决问题的能力。除了课本介绍的常用方法外，用递推法来解某些排列组合应用题更具有一般性和规律性，鉴于这一方法在各类考试包括公务员考试和竞赛中应用越来越广泛，掌握和运用这种方法，就显得更加重要。
文[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).
关键词：构造法；递推法；错位排列；递推公式
中图分类号：G42 文献标识码：A 文章编号：1009-0118（2010）-12-0035-01
为顺应“大众数学”的国际数学教育改革潮流，我国对排列组合知识的引入和应用介绍也越来越重视，解决这类问题的方法灵活，切入点多，且抽象性强，在做题过程中发生重复或遗漏现象不易被发现，所以成为学习难点之一。对此类问题的探讨有助于提高学生分析问题、解决问题的能力。除了课本介绍的常用方法外，用递推法来解某些排列组合应用题更具有一般性和规律性，鉴于这一方法在各类考试包括公务员考试和竞赛中应用越来越广泛，掌握和运用这种方法，就显得更加重要。
文[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).