递推法解排列组合问题

摘要

[例1] 走上10级的阶梯,每步可一级或两级,问有多少种不同的走法? 解法1 按每种走法中一步上两级的步数k（k=0,1,2,3,4,5）分成6类,走上10级阶梯的步数是10-k,这一类的走法数是C10-kk。由加法原理,不同走法总数为 N=C100+C91+C82+C72+C64+C55=89。下面是递推法。解法2 设走上n级阶梯的走法有an种,易知a1=1,a2=2,当n2时,若第一步上一级则有an-1种走法,第一步上两级则有an-2种走法,故an=an-1+an-2（n≥3）。于是当阶梯级数n=1,2,…,10时,走法数依次是 1,2,3,5,8,13,21,34,55,89。即a10=89。注意到解法2中的数列{an}就是菲波那奇数列。