《组合数学》 第三章 递推关系
nnnn3?3?3?3?＝??Ax2?3x?2?3x ??6n?06n?0??3?3nn?n3?3＝??2?3?2?3?x
66n?0??????????nnnn3?3?B?x?＝2?3x?2?3x ??6n?06n?0??3nn?n3＝??2?3?2?3?x
6n?0?6??????????3?33?3nna?(2?3)?(2?3)?n66?解为 ?
?b?3(2?3)n?3(2?3)nn?66?§3.4 三种典型数列
Fibonacci数列、Stirling数列和Catalan数列经常出现在
组合计数问题中，是比较典型的三种数列。
其典型性还不在于数列本身，是在于许多实际计数问题的计算关系都与这三种数列是相同或相似的。 §3.4.1 Fibonacci数列
（一） 背景
定义：序列1，1，2，3，5，8，13，21，34，?中，每个数都是它前两者之和，这个序列称为Fibonacci数列。
意义：由于它在算法分析和近代优化理论中起着重要作用，
又具有很奇特的数学性质，因此，1963年起美国就专门出版了针对这一数列进行研究的季刊《Fibonacci Quarterly》. 来源：1202年由意大利著名数学家Fibonacci提出的一个
36／72
《组合数学》 第三章 递推关系
有趣的兔子问题：有雌雄一对小兔，一月后长大，两月起往后每月生 （雌雄）一对小兔。小兔亦同样如此。设一月份只有一对小兔，问一年后共有多少对兔子？ 一般化：问n个月后共有多少对兔子？ 设第n个月的兔子数为Fn，则F1＝F2＝1. 月份 1 小兔子数 1 大兔子数 总数 1 2 1 1 3 1 1 2 4 ?? n－2 n－1 n n＋1 1 Fn－2 2 Fn－2 Fn－1 3 Fn－2 Fn－1 Fn Fn＝前一个月兔子数＋本月新增兔子数＝Fn－1＋Fn－2
?Fn?Fn?1?Fn?2,即 ??F1?F2?1.（二） 求解
n?3 （3.4.1）
1?1?5?1?1?5?1?1?5??????? ?Fn ＝ ≈?????5?2?5?2?5?2??nnn????????或 Fn??????????（三） 应用
1?1?5?????,n为偶数?5?2????1?1?5?????,n为奇数?5?2????nn
【例3.4.1】（上楼梯问题）某人欲登上n级楼梯，若每次只
能跨一级或两级，问他从地面上到第n级楼梯，共有多少种不同的方法？
（解）设上到第n级楼梯的方法数为an。分类统计： （1） 第一步跨一级，则余下的n－1级有an－1种上法；
37／72
《组合数学》 第三章 递推关系
（2） 第一步跨两级，则余下的n－2级有an－2种上法。
n?3?a?an?1?an?2,由加法原理 ?n（反推得a0?1）。
?a1?1,a2?2.F1 F2 F3 F4 F5 F6 1 1 2 3 5 8 ??
a1 a2 a3 a4 A5
an＝Fn?1
n?1n?1??????11?51?5????? ??????2?5??2??????【例3.4.2】（棋盘染色问题）给一个具有1行n列的1×n
棋盘（见图3.4.1）的每一个方块涂以红、蓝二色之一，要求相邻的两块不能都染成红色，设不同的染法共有an种，试求an。 1 2 3 ?? 图3.4.1 1×n棋盘
n－1 n （解）分类统计，对格子1的染色有两种可能：
（1） 染红色：染色方式总数＝1×1×an?2＝an?2；
1 2 3 ?? n?1 n
（2） 染蓝色：染色方式总数＝1×an?1＝an?1．
1
2 3 ?? n?1 （a0n ?an?an?1?an?2,由加法原理??a1?2,a2?3.n?3?1）
F1 F2 F3 F4 F5 F6 1 1 2 3 5 8 ?? 38／72
《组合数学》 第三章 递推关系
a1
a2
a3 a4
n?2n?2??1?5??1?1?5?????? ??an＝Fn?2＝???2?5??2??????类似问题：无两个1相连的n位二进制数共有Fn?2个。
【例3.4.3】（交替子集问题）有限整数集合Sn??1,2,?,n?的一个子集称为交替的，如果按上升次序列出其元素时，排列方式为奇、偶、奇、偶、?。例如{1，4，7，8}和{3，4，11}都是，而{2，3，4，5}则不是。令gn表示交替子集的数目（其中包括空集），证明
gn?gn?1?gn?2
且有gn?Fn?2． （证）
初值：g1?2，对应S1的交替子集Φ和{1}。
g2?3，对应S2的交替子集Φ、{1}、{1，2}。 分析：将Sn的所有子集分为两部分： （1）Sn?1??1,2,?,n?1?的所有子集； （2）Sn?1的每一个子集加入元素n后所得子集。 举例：n＝4，S4??1,2,3,4?的所有子集划分为两类 （i） Φ、{1}、{2}、{3}、{1，2}、{1，3}、{2，3}、{1，2，
3} （ii） {4}、{1，4}、{2，4}、{3，4}、{1，2，4}、{1，3，
4}、{2，3，4}、{1，2，3，4} 第一部分，即Sn?1的交替子集数为gn?1。
第二部分中的交替子集?Sn?2??1,2,?,n?2?的交替子集，有gn?2个。对应关系为给Sn?2的交替子集加上n或n与n－1即可。
39／72
《组合数学》 第三章 递推关系
?加入3，4去掉3，4?3，4?， ?1?加入4去掉4?1，4?， ?1,2?加入3,4去掉3,4?1，2,3,4?
∴ gn的递推关系为 gn?gn?1?gn?2
∴ 解与例3.4.2同 gn?Fn?2
【例3.4.4】（棋盘的（完全）覆盖问题）用规格为1×2的骨牌覆盖p×q的方格棋盘，要求每块骨牌恰好盖住盘上的相邻两格。所谓完全覆盖是指对棋盘的一种满覆盖（即盘上所有格子都被覆盖），而且骨牌不互相重叠。容易看出，一定存在对2×n棋盘的完全覆盖。现在的问题是，究竟有多少种不同的完全覆盖方案？
（解）设所求方案数为gn。对最左面的四格有且仅有两种可能的覆盖方式： （1） 一块骨牌竖着放：等价于2×（n－1）棋盘的完全覆盖问题，有1×gn?1种方案；
11 21
（2） 一块骨牌横着放：等价于2×（n－2）棋盘的完全覆盖问题。有1×1×gn?2种方案。
11 21 12 22 13 23 14 23 ?? ?? 1n 2n 12 22 13 23 14 23 ?? ?? 1n 2n 图3.4.2 2×n棋盘
?gn?gn?1?gn?2,由加法原理 ?
?g1?1,g2?2.∴ gn?Fn?1
40／72