计数中的递推关系

利用递推关系求解计数问题是处理排列组合问题的一种有效方法，可从简单的情形着手，逐步递推到一般的情形.现在举例说明如何挖掘和利用计数中的递推关系：

一、一阶递推式之整点个数问题

例1在直角坐标系中，定义横纵坐标都为整数的点为“整点”，则集合M={(x,y)||x|+|y|≤n,n∈N*}所表示的区域中有多少个整点？

分析：可从n分析到n+1进行解决．

解：如图，设正方形Gn所确定的整点个数为f(n)，则容易知道f(1)=5，当n增加到n+1时，在第一象限就增加了n个整点，由对称性：

f(n+1)=f(n)+4n+4，累加知道f(n)=2n2+2n+1，故在n=5时所确定的整点的个数共有f(5)=61个．

点评：从f(n)到f(n+1)来分析点的个数的变化．

二、一阶递推式之涂色问题

例2把一个圆分成n个扇形（n≥2），依次记为D1、D2、……、Dn－1、Dn，每个扇形都可以用三种不同颜色中的任何一种涂色，要求相邻的扇形颜色不同，若n=4，则共有种不同涂色方法．

分析：设涂色方法共有f(n)种，当n=2时，f(2)=6，下面寻求f(n)的递推关系即可．

解：D1有3种涂色方法，D2有2种涂色方法，……，Dn－1有2种涂色方法，Dn仍然有2种涂色方法（不论是否与D1同色），这样共有3×2n－1种涂色方法，这3×2n－1种涂色方法可分为两类：（1）Dn与D1同色，虽然与要求不符合，但可以认为Dn与D1合为一个扇形，此时涂色方法有f(n－1)种；（2）Dn与D1不同色，此时涂色方法有f(n)种．

于是3×2n－1=f(n)+f(n－1)，利用数列求和可得到：f(n)=2n+2・(－1)n(n≥2)．

则当n=4时，f(4)=18，共有18种不同涂色方法．

点评：利用递推式可找出D1、D2、…、Dn－1、Dn之间的关系，从而确定不同的涂色方法．

三、二阶递推式

例3一楼梯共有12级，每步可以向上跨1级或2级，共有种上楼梯的方法．

分析：设跨到n级楼梯共有f(n)种走法，由题意，跨到n级楼梯需要从n－2级跨到，或从n－1级跨到，前者有f(n－2)种走法，后者有f(n－1)种走法．

解：由分类计数原理可以知道f(n)=f(n－1)+f(n－2)，则容易知道f(1)=1，f(2)=2，f(3)=3，

f(4)=5，…，故共有f(12)=f(11)+f(10)=233种上楼梯的方法．

点评：从解答中可以看到若求f(12)，则必须知道f(11)和f(10)才能解答．

四、双元递推式

例4用1，2，3这3个数字来构造四位数，但不允许相邻的1出现在四位数中，则这样的四位数共有个．

分析：设用1，2，3这3个数字来构造n位数：末位数字为1的有f(n)个，末位数字不为1的有g(n)个，则所有满足条件的n位数共有f(n)+g(n)个，再分这两种情况分析．

解：考虑由1，2，3构成的n+1位数：（1）末位数字为1，此类数可由满足要求的n位数中末位不为1的数末位添上1而得到的，故此类数有g(n)个；

（2）末位数字不为1，此类数可由满足要求的n位数中末位添上2或3而得到的，故此类数有2［f(n)+g(n)］个．

于是f(n+1)=g(n)g(n+1)=2［f(n)+g(n)］ ，由f(1)=1g(1)=2 ，得到n=4时，f(4)+g(4)=60．

点评：通过f(n+1)和g(n+1)双元递推，则问题比较容易解决．

（作者：周文国，江苏张家港职业教育中心)