递推方法与排列组合.doc

递推方法与排列组合雷雨田 （广西师范大学附属外国语学校高50班 541004）解决排列组合问题的方法多种多样，不过一般想到的是等价转换后直接运用计数原理做的。其实还可以建立一种递推关系，通过数列来解决。可以看看下面几个例子：走楼梯问题例1：欲登上第10级楼梯，如果规定每步只能跨上一级或两级，则不同的走法共有多少种？这题如果直接分类，就是这样做：第一类：没有一步两级，则只有一种走法；第二类：恰有一步是一步两级，则走完10级要走9步，9步中选一步是一步两级的，有种走法。第三类：恰有两步是一步两级，则走完10级要走8步，8步中选两步是一步两级的，有 种可能走法；依此类推，共有种走法。直接做的话如果想不到这样分类，那头就痛了。其实，我们知道，有时候一个问题可以看成是由多个子问题组成的（就比如Hanoi问题），于是，递推方法就出来了：设走n级台阶有种走法，则这些走法可按第一步分类：第一类：第一步是一步一级，则余下的n-1级有种走法；第二类：第一步是一步两级，则余下的n-2级有种走法；所以易得，又易得，所以推算一下，很快得到。（记得这个问题是在学校统一发的教学与测试（高一数学）（苏州大学出版社）这本书中的阅读材料上看到的。其实材料是为了引出Fibonacci数列，不过编者在不经意间透露出了这种递推方法。有好多同学都想知道做题的方法、方法，想快速提高。其实只要留心一些，方法还是不难找到的。）染色问题再来看看染色问题吧：记得2008年全国I的一道高考题是这样的：如图所示，一环形花坛分成1、2、3、4四块。现有4种不同的花供选择，要求在每块里种一种花，且相邻的2块不能种同一种花，则不同的种法总数为？当然，毕竟数量较少，可以经过分类来处理（谨防重或漏）。现在用递推方法来解决：将这n块按顺时针编号为。设用m种颜色进行染色，不同的染色方法有种，现进行分析：第一步：染 ，有m种染法；第二步：染，有m-1种染法；（避免与A1重复）同理，染均有m-1种染法，最后染，如果仅考虑与不同色（此时没考虑与是否同色），则仍有m-1种染法，相乘得种染法。但要排除同色的染法数，此时可将与合并看成一个点，得出需要排除的染法数为，所以有，可以求出。于是在本题中，m=4，n=4,所以=84。答案即84种种法。（思考：如果经过一个小变化，就是中间那个圆里也要种花，其他要求不变，问现在共有多少种方法？）（这仍然是一道全国高考试题）又想起与这题有关的一道高考题，有兴趣的话可以试试：某城市在中心广场建造一个花圃，花圃分成6个部分(如图2)，现要栽种4种不同颜色的花，每部分栽种一种且相邻部分不能栽种同样颜色的花，不同的栽种方法共有 种。（以数字作答）(2003年天津理科高考试题)错排问题再重新来看看这个老问题吧：有n封信装进n个信封里，结果发现这n封信全部装错了。那么装错的情况总共有多少种？很自然地，设满足这样的装信方式有种，现进行分析：第一步：第一封信不装在原来的第一个位置，有n-1种装法。第二步：假设第一封信装在第2个位置，则第二封信的装法又可以分为两类：第一类，第二封信恰好装在第一个位置，则余下的n-2封信有种装信方式；第二类，第二封信不装在第一个位置，则就是第二封信不装在第一个位置，第三封信不装在第三个位置，第n封信不装在第n个位置，所以有种装信方式。于是，便得到了这样一个递推关系：。现在来解这个数列：把原式部分展开，移项得：然后把右边的套入公式得再把套入公式最后得到：由此得，同样地，有采取累加法，得到这也可以用容斥原理推导过的错位排列公式通过以上几个例子，我们可以知道递推法的关键是按照某种标准找出递推关系式，并求出n取第一个值(或前几个