选自公众号“许康华竞赛优学”，本文作者:王仕奎。“许康华竞赛优学”每天推送精彩竞赛及培优数学文章，为数学的普及与提高贡献一份力量。
组合数学的一个很重要的内容是计数, 柯召和魏万迪在其经典名著《组合论》(上册)前言中对计数的定义是: “当符合要求的安排显然存在或已被证明存在时，求出这样的安排的(全部或其中不等价的)个数”. 计数问题似易实难, 我曾提出两个计数问题征解, 即11月3日的《一个组合计数问题征解》和11月5日的《又一个组合计数问题征解》, 一些组合学名家都说两题有一定难度.
许多计数问题可以化为递推关系求解, 得到递推关系之后,有两种处理: 一是求出通项公式(又叫“一般公式”), 这是最理想的情况; 二是不能求出通项时, 用计算机计算, 或者对通项估计其数量级. 如果前两种方法都不管用的话, 那么只能用计算机进行蒙特.卡洛仿真了.
下面三个问题都可以用递推法归结为斐波拉契数列的求解:
① 有雌雄一堆兔子, 假定出生两个月后每月又能繁殖一对兔子, 问n个月后有几对兔子?
② 有10级台阶, 每次可以上1级或者2级, 问从平底上到第10级台阶, 一共有多少种不同的走法?
③ 2 X n棋盘用n块1 X2的多米诺骨牌覆盖, 有多少种方法把棋盘完全盖住? 假定棋盘的方格编了号(如下图).
前两个问题较为简单, 下面分析第③题的算式递推推导过程.
设所求完全覆盖方法种数为Fn. 分两种情况.
① 1, 2两格被一块1 X 2的多米诺骨牌盖住, 此时余下的2 X(n - 1)棋盘被n - 1块多米诺骨牌完全覆盖, 有Fn - 1种方法.
② 1, 3两格被一块1 X 2的骨牌盖住, 此时2, 4两格也被1X 2的骨牌盖住, 而余下的2 X (n - 2)棋盘被n - 2张1 X2的骨牌完全覆盖, 有Fn - 2种方法. 因此, Fn = Fn – 1 + Fn- 2 (n ≥ 3), 又显然F1 = 1, F2 = 2.
上述三个问题, 都可以归结为如下数列
{y(n), n≥ 1}
的通项的求解, 即已知
y(1) = 1, y(2) = 1, y(n+ 2) = y(n + 1) + y(n) (n≥ 1)
求y(n)的一般表达式. y(n)即为著名的斐波拉契(Fibonacci)数列.(斐波拉契数列的初始值可以为1, 1, 也可以为1, 2, 略有不同.)
卢开澄的《组合数学》(第4版, 清华大学出版社, 2006)采用母函数工具求解斐波拉契数列的通项. 另一种更常见的方法是特征方程法.
下面提供斐波拉契数列通项的四种求法, 其中第一种方法是中学生可以理解的方法, 用待定系数法“凑”等比数列,最后得到两个等式, 联立求解得到通项; 第二种方法就是最常见的特征方程法, 也是一般的《信号与系统》课程中介绍的时域求法; 第三、四种方法是《信号与系统》课程中介绍的变换域方法, 即z变换法, 一个是前向差分方程的z变换, 一个是后向差分方程的z变换. 四种方法的结果是一样的, 正所谓 “条条大道通罗马”.
为了介绍用变换域求解差分方程(即斐波拉契数列), 简单介绍一些背景知识, 即离散系统的z变换, 它是电子信息类专业本科必修专业基础课《信号与系统》的基本内容.
z变换是研究离散系统响应及系统特性的基本工具，z变换的地位和拉氏变换(又叫s变换)相似: 拉氏变换可以将微分方程变成代数方程求解, 而z变换可以将差分方程变成代数方程. 利用z变换求解差分方, 主要用到单边z变换的移位特性及逆z变换. 差分方程又分前向差分方程和后向差分方程, 两者基本是等价的, 在计算时略有不同.
下面是分别用前向差分方程和后向差分方程求解斐波拉契数列的一般公式.
联系客服
