王正勇

(如皋市搬经中学,江苏 如皋 226561)

组合数学的考题一般都以计数问题为主,而有些计数问题直接去求解并不是那么容易,因为它们是以“建立递推关系”为背景的,也就是说,要先建立递推关系,再去求解通项公式,才能顺利完成计数问题.

1 知识与方法

1.1 递推关系

对于数列{an}(n∈N*),若当n≥k+1时,an与an-1,an-2,…,an-k之间满足函数关系

F(an,an-1,an-2,…,an-k)=0,

①

或an=f(an-1,an-2,…,an-k),

②

则称①或②为k阶递推关系或k阶递归关系.由此递推关系及初值条件a1,a2,…,ak所确定的数列称为k阶递推数列[1].

在k阶递推关系①中,若各项的系数均是与n无关的常数,则称这个递推关系为常系数递推关系;若递推关系中各项的次数相同,则称这个递推关系为齐次递推关系;若递推关系中各项的次数均不超过一次,则称这个递推关系为线性递推关系.

本文主要介绍计数问题的重要方法——建立线性递推关系.

1.2 建立线性递推关系的方法

(1)通过求数列{an}的第1项以及前几项,去寻找任一项an与它的前一项an-1或前几项间的关系式.

(2)分析要计算第n项an的值需要计算哪些项的值,从而得到an与它的前几项间的关系.

建立递推关系进而解递推关系是解决组合计数问题的一种常用而重要的方法.

2 应用

例1(强基计划模拟题)空间有n个平面,最多能把空间分割成____个部分[2].

解析为了将空间分割成最多的部分,n个平面中的任意两个平面都不应平行,任意三个平面都不应共线,其所得交线中任意两条交线都不应平行.

现设n个平面最多能把空间分割成an个部分,易知a1=2,a2=2+2=4.增添第三个平面时,和原来两个平面有两条交线,两条交线把第三个平面分成4个部分,所以使空间增多4个部分,即a3=a2+4=8.增添第四个平面时,和原来三个平面有三条交线,三条交线把第四个平面分成7个部分,所以空间增多7个部分,即a4=a3+7=15,按此规律可得到a5=a4+11=26,并发现

a1=2,

a2=a1+2=a1+(1+1),

a3=a2+4=a2+(1+2+1),

a4=a3+7=a3+(1+2+3+1),

a5=a4+11=a4+(1+2+3+4+1),

……

an=an-1+[(1+2+3+…+n-1)+1].

所以得到下列递推公式

评价本题是通过建立数列的递推关系来求解,对于较为复杂的计数问题,这个方法值得借鉴.

例2(高考模拟题)如图1所示,有标号为1,2,3的三根柱子,在1号柱子上套有n个金属圆片,从下到上圆片依次减小.按下列规则,把金属圆片从1号柱子全部移到3号柱子,要求:①每次只能移动一个金属圆片;②较大的金属圆片不能在较小的金属圆片上面[3].

(1)若n=3,则至少需要移动____次;

(2)将n个金属圆片从1号柱子全部移到3号柱子,至少需要移动____次.

图1 金属圆片

解析(1)当n=1时,只需要把金属圆片从1号柱子移到3号柱子,用符号(13)表示,共移动了1次.

当n=2时,移动的顺序为:(12)(13)(23),共移动3次.

当n=3时,把上面的两个金属圆片作为一个整体,则归结为n=2的情形,移动的顺序是:

(13)(12)(32);(13);(21)(23)(13)

共移动了7次.

(2)记把n个金属圆片从1号柱子移到3号柱子,最少需要移动an次,则由(1)知

a1=1,a2=3,a3=7.

当移动n个金属圆片时,可分别进行下列3个步骤:

①将上面(n-1)个金属圆片从1号柱子移到2号柱子;②将第n个金属圆片从1号柱子移到3号柱子;③将上面(n-1)个金属圆片从2号柱子移到3号柱子.

这样就把移动n个金属圆片的任务,转为移动两次(n-1)个金属圆片和移动1次第n个金属圆片的任务.而移动(n-1)个金属圆片需要移动两次(n-2)个金属圆片和移动1次第(n-1)个金属圆片;移动(n-2)个金属圆片需要移动两次(n-3)个金属圆片和移动1次第(n-2)个金属圆片……如此继续,直到转化为移动1个金属圆片的情形.根据这个过程,可得递推公式:

从而当n≥2时,有an+1=2(an-1+1).

所以{an+1}是以2为公比,2为首项的等比数列.

所以an+1=2n,即an=2n-1.

例3(强基计划模拟题)将一个2021边形的每个顶点染为红、蓝、绿三种颜色之一,使得相邻顶点的颜色互不相同.问:有多少种满足条件的染色方法?

解析记将一个n边形的每个顶点染为红、蓝、绿三种颜色之一,使得相邻顶点的颜色互不相同的方法数为Tn. 易知,T3=6,T4=18.

对于任意一个n(n≥5),记A1,A2,…,An顺次为这个n边形的顶点,则对它按题设要求染色,有两种情况:

①A1,An-1异色,共有Tn-1种;

②A1,An-1同色,共有2Tn-2种.

因此Tn=Tn-1+2Tn-2(n≥5).

该递推公式的特征方程为x2=x+2,解得x1=-1,x2=2.

所以Tn=c1(-1)n+c2·2n.

又因为T3=6,T4=18,解得c1=2,c2=1.

因此Tn=2(-1)n+2n,所以T2021=22021-2.

例4(1995年全国高中数学联赛)将一个四棱锥的每个顶点染上一种颜色,并使同一条棱的两个端点异色. 如果只有5种颜色可供使用,那么不同的染色方法总数是多少?

当S,A,B已染好时,不妨设其颜色分别为1,2,3.下面分C与A同色与异色两种情况讨论:

若C染颜色2,则D可染颜色3,4,5之一,有3种染法;若C染颜色4,则D可染颜色3或5,有2种染法;若C染颜色5,则D可染颜色3或4,有2种染法.

可见,当S,A,B已染好时,C与D还有7种染法. 从而总的染色方法数为60×7=420.

评析我们可把四棱锥推广为n棱锥,颜色数推广为m种(n≥3,m≥4).

事实上,顶点S可用m种颜色中的任一种,并且S上的颜色不能再出现在多边形A1A2…An的顶点上. 问题转化为用m-1种颜色给多边形A1A2…An的顶点染色,相邻的顶点不同色. 设有an种染法,则a3=(m-1)(m-2)(m-3).

对n>3,考虑an的递推公式. 若从顶点A1开始,则A1有m-1种染法,继而A2,A3,…,An-1均有m-2种染法. 最后到An,如果只要求An与An-1不同色,则仍有m-2种染法,于是总共有(m-1)·(m-2)n-1种染法.

在这个计算过程中可以分为两类:一类是An与A1不同色,这符合要求,正是染法数an;另一类是An与A1同色,这不符合要求,但可将An与A1合并成一点,得出染法数an-1.于是

即an=(m-2)n+(-1)n(m-2).

从而n棱锥的染法总数为

N=(m-2)n+(-1)n(m-2).

许多组合计数问题都归结为求某个数列的通项公式,而直接去求数列的通项公式往往比较困难,此时我们可以考虑先求关于该数列的递推关系,然后去解这个递推关系.如果能顺利完成这两个步骤,则问题就得到了解决.