利用递归思想解决计数问题

1、利用递归思想解决计数问题 福建省永定第一中学简绍煌 我们常会遇到一些看似排列组合应用题的计数问题，但其复杂的情形有时令人无从下 手，若是利用递归思想建立递归方程加以求解，则往往能够迎刃而解. 【例1】有一楼梯共10级，如果规定每步只能跨上一级或二级，要上10级，共有多少 种走法？ 解 设上n级楼梯共有an种走法，当n =1时，a1 ；当n =2时，a2 . 当有n(n . 2)级楼梯时，其走法分两类. 第一类：走完前面 n-1级楼梯有an j种走法，走第n级只有1种走法； 第二类：走完前面n2级楼梯有an,种走法，走第n1级与第n级楼梯时一步走，也 是1种走法. 由分类计数原理，知 n级楼梯的

2、走法为an =an_2 - anJ( nN,且n 2). 由此可以算出a10 =89 . 点评其通项公式可用换元法转化为一阶线性递归数列求解. 令Cn二an .1 -Xn，使数列 Ci是以X?为公比的等比数列(X?待定). 即 an 2 - xan 1= X2(an 1- 乂*)，an2 =(X1X2)an- x/za*.对照已给递归式， 有 X-I X2 = 1, X1X -1，即X2 是方程 X2 - X -1 = 0 的两个根. 从而X5 , X2=15 ；或I 5 , 2 2 2 1-亦1+屁1-亦 、 an 2an 1(an 1an) 22 2 151 - 51.5 或 an 2an

3、 1(an 1an ) 2 1 - 5 n 1 + 75 由式得an彳-an 2 由式得an彳 an 1(an 1-小 2 2 3 *、5；1 * 5n )； 2 2 3-、5 .,1 -、5冲 ( ) 2 2 1 -、5 3 一5 ,1 .5、 丁) nA 3 _ V5 /1 _、nI 一丁 (b) an4)(n3). nan4an/(n - 1归心 八= n! 1 消去an卅，得an = 【例2】将数字1,2,3, * , n填入标号为1,2,3，n的n个方格内，每格一个数字，则 标号与所填数字均不同的填法共有多少种？ 解 设这n个自然数的错排数为 an . 当 n = 1 时，ai =

4、0 ;当 n = 2 时，a2 =1 . 当n 一3时，n个自然数的错排数可以分两类情况计算. 第一类：自然数k(1岂k空n-1)与n互换，这时错排数为 an ； 第二类：自然数n在第k位上，但自然数不在第 n位上.这时就把第 n位看做第k位， 相当于将n以外的n -1个自然数进行错排，错排数为 an/. 所以，自然数n在第k位上的错排数共有an, - an 4种，由于k可以是1,2, , n-1共 n -1种可能，故n个自然数的错排数为 an =(n- 1)(an 由式得，an-an4 二-an斗-(n - 1叽，二 a n! an an _J n! (n -1)! 邑 n (n -1)!

5、(n -2)! 用累乘法得色（一 I），丄（1）n丄； n! （n_ 1）!n!n! 再用累加法得 別=丄_丄丄一 .（_i）2丄, n! 2!3!4!n! 故an n! 2! 史”（_1）n巴 3!4!n! = C；(n 一2)! C；(n 一3)! C：(n 一4)! 一(-1)七： 利用此递推式，可以计算 1993年的一道高考试题： 同室四个各写一张贺年卡，先集中起来，然后每人从中拿一张别人送出的贺年卡，则四 张贺年卡不同的分配方式有几种？ 解 a 0， a2 =1，a3 = 2佝 a2） = 2， a4 = 3（a2 a3） = 9 .所以，四张贺年卡不 同的分配方式有9种或直接用公式

6、计算. 【例3】有三根杆子A, B, C. A杆上有64个穿孔圆盘，盘的尺寸由下往上依次变小.要 求按下列规则将所有圆盘移至C杆：1.每次只能移动一个圆盘；2.大盘不能叠在小盘上 面问最少要移动多少次？ 解设最少需要移动的次数为 an .我们这样来操作： 最底下的一个圆盘先不动它，把上面余下n -1个圆盘按规则移至 B杆（其移动次数为 anA）,然后把最底下的那个圆盘移至C杆，最后再把n-1个圆盘转移到 C杆这样，总共 移动的次数为an =2an4 - 1（n _2） 下面我们求它的通项公式. 方法1 （转化为an 1p = q（anp）型递归数列）.显然，a 1 . - an =2an1（n

7、 一2） , /务 T =2（an1）（n 一 2） . 又 印 1 = 2 ,故数列 1 是首项为2,公比为2的等比数列. an，1 = 2n，即an = 2n T .故a64 = 2641 （次）. 方法2.转化为a. 2 - a. .1 =q（an 1 -a.）型递推数列. an 2an1（n - 2）,- an 1 二 2an 1 一，得 an 1 - an = 2（an - an 4）（ n 亠 2），故an 1 - an是首项为比 - a1 = 2 , 公比为2的等比数列，即an. -a2-2nJ =2n ,再用累加法得 可=2n -1 . 方法3 （用迭代法）. 2 an =2a

8、n41 =2（2anq 1）1 =2 令21 八 =2n4a1 2n 2n，川“卜21 =2n _1. 此外，此题也可用归纳猜想法求之，但要用数学归纳法证明. 点评这是著名的汉诺塔问题（又称河内塔问题）.据说创世紀时 Ben ares有一座波罗 教塔，是由三支钻石棒（Pag）所支撑，开始时神在第一根棒上放置64个由上至下依由小至 大排列的金盘（Disc）,並命令僧侣将所有的金盘从第一根石棒移至第三根石棒，且搬运过 程中遵守大盘子在小盘子之下的原则，若每日仅搬一个盘子，则当盘子全数搬运完毕之时， 此塔将损毁，而也就是世界末日來临之时 根据上面的结果，如果一秒钟能移动一块圆盘，仍将需5845.54

9、亿年.目前按照宇宙大 爆炸理论的推测，宇宙的年龄仅为137亿年. 【例4】四个人互相传球，由甲开始发球，这称为第一次传球，经过5次转球后，球仍 然回到甲手中，试求所有不同的传球方式有多少种？ 解 设第n次传球时球仍然回到甲手中的不同方式共有an种，显然，ai = 0 .第 n -1（n -2）次传球时共有 3n4种，而只有当球不在甲手中时才有可能传给甲，所以有 an = - an j . 将式化为= _!(-a-1)(n_2)，令bn -n- -n 511 设bn-(bn j - )，比较系数，可得= -4 1)11 所以, 曰 疋， 故an a1 专，则 bn=-;(bn1-1). -n-

10、_ 11 (bn j)(n 一 2). -4 bn是以首项为 ，公比为的等比数列, /44- bnj W)2，即 bn ”一-严 44-4- - 1 = (-1)n3n (n_2). 44 3 1 当n =1时，由式可得& =0，所以，an =1)n - 4 4 .3n(n N*). 当 n =5时，有 an =(-1)5 - 35 44 1 点评 亦可有方程x (x-9) - 个特例.传球次数对应为多边形的边数， =60 .故所有不同的传球方式有 60种. (不动点)直接求得.此传球问题是染色问题的一 人的个数对应为使用颜色的种数，球不传给自己对 指定 m(m亠3)种颜色给n(n亠3)边形染色，要 an，则 应为多边形相邻点染不同颜色，球每次只传到一个人手里对应为每个点只染一种颜色, 从甲发