《组合数学》教案 3章(递推关系)

《《组合数学》教案 3章(递推关系)》由会员分享，可在线阅读，更多相关《《组合数学》教案 3章(递推关系)（71页珍藏版）》请在金锄头文库上搜索。

1、组合数学 第三章 递推关系172第 三 章 递 推 关 系1. 递推关系及其分类2. 建立应用问题的递推关系的方法3. 求解线性常系数递推关系的特征根方法4. 求解递推关系的其它方法5. 三个典型数列及其应用3.1 基本概念（一） 递 推 关 系【定义 3.1.1】（隐式）对数列 和任意自然数 n，0ia一个关系到 和某些个 的方程式，称为递推关系，nani记作 ,10F例 02212 naann31【定义 3.1. 】 （显式） 对数列 ，把 与其之 ina前若干项联系起来的等式对所有 nk 均成立（ k 为某个给定的自然数） ，称该等式为 的递推关系，记为ia（3.1.1）knnnFa,2

2、1例 13aa组合数学 第三章 递推关系272（二） 分 类（1） 按常量部分： 齐次递推关系：指常量0，如；21nnF 非齐次递推关系，即常量0，如 。12nh（2） 按 的运算关系：ia 线性关系，F 是关于 的线性函数，如（1）中的ia与 均是如此；nh 非线性关系，F 是 的非线性函数，如i。121hnn（3） 按 的系数：ia 常系数递推关系，如（1）中的 与 ；nF 变系数递推关系，如 ， 之前的系数1np是随着 n 而变的。（4） 按数列的多少： 一元递推关系，其中的方程只涉及一个数列，如（3.1.1）和（3.1.1）均为一元的； 多元递推关系，方程中涉及多个数列，如 17nna

3、ba（5）显式与隐式： 1112nnyxhy组合数学 第三章 递推关系372（三） 定 解 问 题【定义 3.1.2】（定解问题）称含有初始条件的递推关系为定解问题，其一般形式为（3.1.2）110, kndadaF解递推关系，指根据式（3.1.1）或（3.1.2）求 an 的与a0、a 1、a n1 无关的解析表达式或数列a n的母函数。（四） 例【例 3.1.1】（Hanoi 塔问题）n 个圆盘按从小到大的顺序一次套在柱 A 上。规定每次只能从一根柱子上搬动一个圆盘到另一根柱子上，且要求在搬动过程中不允许大盘放在小盘上，而且只有 A、B 、C 三根柱子可供使用。用 an 表示将 n 个盘从

4、柱 A 移到柱 C 上所需搬动圆盘的最少次数，试建立数列的递推关系。naA B C（解）特例：a 11，a 23，对于任何 n3。一般情形：第一步，将套在柱 A 的上部的 n1 个盘按要求移到柱B 上，共搬动了 次；1n组合数学 第三章 递推关系472第二步，将柱 A 上的最大一个盘移到柱 C 上，只要搬动一次；第三步，再从柱 B 将 n1 个盘按要求移到柱 C 上，也要用 次。1na由加法法则： 1,2an（3.1.3）求解 na12【例 3.1.2】（Lancaster 战斗方程）两军打仗，每支军队在每天战斗结束时都清点人数，用 a0 和 b0 分别表示在战斗打响前第一支和第二支军队的人数

5、，用 an 和 bn 分别表示第一支和第二支军队在第 n 天战斗结束时的人数，那么，an 1 an 就表示第一支军队在第 n 天战斗中损失的人数，同样，b n1 bn 表示第二支军队在第 n 天战斗中损失的人数。假设：一支军队所减少的人数与另一支军队在每天战斗开始前的人数成比例，则 11nnBabAa常量 A、B度量每支军队的武器系数（3.1.4）11nn含有两个未知量的一阶线性递归关系组。【例 3.1.3】设 ，求a n所满足的递推关20nkkra组合数学 第三章 递推关系572系。（解） 下整数函数。即不大于 x 的最大整数。xn 为偶数： na2r-n1-02nrn 为奇数： n 2-2

6、1-r分两种情况：当 n 为偶数时，令 n2m ，则 m 121an mkkr0 1kmr 021mk krm前两项求和： 101220kkmk rr组合数学 第三章 递推关系6721210nnkkar后两项求和：20mj jrjr 1mr 10j jj20nj j2na na12nr当 n 为奇数时也成立。求初值：a 0a 11。则 1r， r 1 2r，2032a r (12r)r (1r) 13r432 2r r (13r )r (12r)14r35a22r【例 3.1.4】设 0 出现偶数次的 n 位八进制数共有 个，0na出现奇数次的数共有 个。求 和 满足的递推关系。bab对 0

7、出现偶数次的 n 位八进制数分两种情况讨论：（1）最高位是 0，则其余 n1 位应该含有奇数个 0，这类八进制数共有 个。1（2）最高位不是 0，则其余 n1 位还应该含有偶数个0，这类八进制数共有 7 个。1na因此有 7 。同理可得 7 ，nabb1na所以 、 满足b组合数学 第三章 递推关系7721,7,1baann例 n20 出现偶数次的数 00，11，12，13，14，15，77，共 50 个0 出现奇数次的数 01，10，02，20，03，30，70，共 14 个【例 3.1.5】用后退的 Euler 公式求常微分方程的数值解。10,yx（解）函数 yy(x)在点 xn 处的真值

8、记为 y(xn)，近似值记为 yn，求数值解即利用数值方法求 y(x)在处 xn 的近似值yn（ n1,2,） 。思想：以直代曲。向前的 Euler 方法： ，其中nyhfy,1h 称为步长 。nx1向后的 Euler 方法：后退的 Euler 公式是指对常微分方程，当已知函数 y 在 处的值时，可通过解代数yxf, nx组合数学 第三章 递推关系872方程 求得函数 y 在 处的11,nnyxhfy 1nx数值解 ，其中 h 是自变量 x 的步长（n0,1,2, ） 。已知原方程为 ，代入 Euler 公式yxfy2,可得函数 y 的数值解为 10 11hnnn（五） 本 章 研 究 内 容

9、1. 建模；2. 求解。3.2 常系数线性递推关系常系数的线性递推关系：（3.2.1）0,21 kknnn cacac组合数学 第三章 递推关系972或（3.2.2）0,21 kknnn cfacac分别称为 k 阶齐次递推关系 和 k 阶非齐次递 推关系。其中f(n)称为自由项。显然，式（3.2.1）至少有一个平凡解 ，而人们更关心的是它的 非零解。,210na结论 ：对于常系数线性递推关系的定解问题，其解必是唯一的。求解方法：首推特征根法。思想：来源于解常系数线性微分方程，因为两者在结构上很类似，所以其解的结构和求解的方法也类似。3.2.1 解 的 性 质【性质 1】设数列 和 是（3.2

10、.1）的解，则1nb2n也是（ 3.2.1）之解。其中 为任意2nrb21r、常数。（证） 、 满足方程（3.2.1） ，即1n2nb,01121 knnbcc 222nn令 r1 r2得：00210201 ki ininikinikiin brcbcbc（规定 c0 1，下同） 。组合数学 第三章 递推关系1072【推广】设 均为（3.2.1）之解，snnnbb、21,则 也是（3.2.1）的解。其中 为任siinr1 sr,21意常数。【性质 2】设 和 是（3.2.2）的解，则1nd2n是（3.2.1 ）的解。1nb【性质 3】若 是（3.2.1）的解， 是（3.2.2）的解，nbnd则

11、 是（3.2.2 ）的解。nd一般情形：设 是（3.2.2）的解，nd分别是（3.2.1）的解，则snb、21,是（3.2.2）的解。siid1【性质 4】设 是递推关系 的解，1ndkiinfac01是递推关系 的解，则2ndkiifac02是递推关系 的解。21nnfckiin2013.2.2 解 的 结 构（一） 概 念（3.2.1）0,21 kknnn cacac【定义 3.2.1】称多项式C(x) kkkkxxx121组合数学 第三章 递推关系1172为齐次递推关系（3.2.1）的特征多项式，相应的代数方程C(x) 0kkkk cxxcx121称为（3.2.1）的特征方程，特征方程的

12、解称为（3.2.1）的特征根。（二） 结 论【定理 3.2.1】数列 （3.2.1）的非零解的充分必要条nqa件是 q 为（ 3.2.1）的特征根。（证） 是（3.2.1）的解n01kncc kq 是方程 C(x)0 的根，即 q 是（3.2.1）的特征根。意义 ：将求解常系数线性齐次递推关系的问题转化为常系数代数方程的求根问题，从而给出了一个实用且比较简单的解此类递推关系的方法。（三） 通 解【定义 3.2.2】 若 是（3.2.1）的不snnaa,21同解，且（3.2.1）的任何解都可以表为，则称 为（ 3.2.1）的通解。snnrar21其中 为任意常数。s,此处所说的不同解是指将每一个解 都视为一个无穷ina维的解向量，而这些向量之间是线性无关的。说明 通解的特征： 通解 首先是解；na 组成通解的所有解向量线性无关；组合数学