组合数学讲义 3章 递推关系

组合数学讲义

第三章 递推关系 §3.1 基本概念

（一） 递推关系

定义3.1.1 （隐式）对数列 aii 0 和任意自然数n，一

个关系到an和某些个ai i n 的方程式，称为递推关系，记作

F a0,a1, ,an 0 (3.1.1)

22222

例 an an 1 an 2 a0 n 0

an 3an 1 2an 2 2a1 1 0

定义3.1.1＇（显式） 对数列 aii 0 ，把an与其之前若干项联系起来的等式对所有n≥k均成立（k为某个给定的自然数），称该等式为 ai 的递推关系，记为

an F an 1,an 2, ,an k (3.1.1)＇

例 an 3an 1 2an 2 2a1 1 （二） 分类

（1） 按常量部分：

① 齐次递推关系：指常量＝0，如

Fn Fn 1 Fn 2；

② 非齐次递推关系，即常量≠0，如hn 2hn 1 1。 （2） 按ai的运算关系：

组合数学讲义

① 线性关系，F是关于ai的线性函数，如（1）中的Fn

与hn均是如此；

② 非线性关系，F是ai的非线性函数，如hn h1hn 1 h2hn 2 hn 1h1。 （3） 按ai的系数：

① 常系数递推关系，如（1）中的Fn与hn；

② 变系数递推关系，如pn npn 1，pn 1之前的系数是随着n而变的。 （4） 按数列的多少：

① 一元递推关系，其中的方程只涉及一个数列，如(3.1.1)和(3.1.1)＇均为一元的；

② 多元递推关系，方程中涉及多个数列，如

an 7an 1 bn 1

bn 7bn 1 an 1

（5）显式与隐式：

yn 1

（三） 定解问题

xn 1

yn h yn 1 2 yn 1

定义3.1.2 （定解问题）称含有初始条件的递推关系为定解问题，其一般形式为

F a0,a1, ,an 0,

(3.1.2)

a0 d0,a1 d1, ,ak 1 dk 1

所谓解递推关系，就是指根据式(3.1.1)或(3.1.2)求an的与a0、a1、 、an－1无关的解析表达式或数列{an}的母函数。

组合数学讲义

（四） 例

例3.1.1 （Hanoi塔问题）这是组合学中著名的问题。n个圆盘按从小到大的顺序一次套在柱A上，如图3.1.1所示。规定每次只能从一根柱子上搬动一个圆盘到另一根柱子上，且要求在搬动过程中不允许大盘放在小盘上，而且只有A、B、C三根柱子可供使用。用an表示将n个盘从柱A移到柱C上所需搬动圆盘的最少次数，试建立数列{an}的递推关系。

A B C

图3.1.1 Hanoi塔问题

（解）特例：a1＝1，a2＝3，对于任何n≥3。 一般情形：：

第一步，将套在柱A的上部的n－1个盘按要求移到柱B上，共搬动了an 1次；

第二步，将柱A上的最大一个盘移到柱C上，只要搬动一次；

第三步，再从柱B将n－1个盘按要求移到柱C上，也要用an 1次。

an 2an 1 1,

由加法法则：

(3.1.3)

a1 1

组合数学讲义

求解 an＝2n 1

例3.1.2 （Lancaster战斗方程）两军打仗，每支军队在每天战斗结束时都清点人数，用a0和b0分别表示在战斗打响前第一支和第二支军队的人数，用an和bn分别表示第一支和第二支军队在第n天战斗结束时的人数，那么，an－1－an就表示第一支军队在第n天战斗中损失的人数，同样，bn－1－bn表示第二支军队在第n天战斗中损失的人数。

假设：一支军队所减少的人数与另一支军队在每天战斗开始前的人数成比例，则

an 1 an Abn 1

bn 1 bn Ban 1

常量A、B——度量每支军队的武器系数

an an 1 Abn 1

(3.1.4)

bn bn 1 Ban 1

——含有两个未知量的一阶线性递归关系组。

n 2

n k k

例3.1.3 设an k r，求{an}所满足的递推关

k 0

系。

（解）

n n

n n-1 n-2 2

2 r2 r rn为偶数：an＝ ＋ ＋ 0 1 2 n 2

组合数学讲义

n 1 n-1 n n-1 n-2 2

2 r2 r ran＝ n为奇数：＋ ＋ 0 1 2 n-1 2

分两种情况：当n为偶数时，令n＝2m，则

n 1 n 2

＝ ＝m－1 2 2

m

2m k k

an＝ k r

k 0

2m m 1 2m k k m m＝ 0 ＋ k r＋ m r k 1 2m m 1 2m k 1 k

r ＝ 0 ＋ k k 1

m 1

2m k 1 k m m

＋ k 1 r＋ m r

k 1

前两项求和：

2m m 1 2m k 1 km 1 2m k 1 k

r r ＝ 0 kk k 1 k 0

n 1

2

k 0

n 1 k k

r an 1 k

后两项求和：

m 1 m 1 2m j 2 j

r r r＋r j m 1 j 0

m 2

2m 2

＝r jj 0

m 1j j

r＝r

n 2 2

j 0

n 2

j j j

r＝ran 2

an＝an 1＋ran 2

组合数学讲义

当n为奇数时也成立。 求初值：a0＝a1＝1。则

a2＝a1＋ra0＝1＋r，a3＝a2＋ra1＝1＋2r， a4＝a3＋ra2＝(1＋2r)＋r (1＋r)＝1＋3r＋r2

a5＝a4＋ra3＝(1＋3r＋r2)＋r (1＋2r)＝1＋4r＋

3r2

例3.1.4 设0出现偶数次的n位八进制数共有an个，0出现奇数次的数共有bn个。求an和bn满足的递推关系。 对0出现偶数次的n位八进制数分两种情况讨论：

（1）最高位是0，则其余n－1位应该含有奇数个0，这类八进制数共有bn 1个。

（2）最高位不是0，则其余n－1位还应该含有偶数个0，这类八进制数共有7an 1个。

因此有an＝7an 1＋bn 1。同理可得bn＝an 1＋7bn 1，所以an、bn满足

an 7an 1 bn 1, b 7b

n 1 an 1, n

a1 7,b1 1例 n＝2

0出现偶数次的数 00，11，12，13，14，15， ，77，共50个

0出现 …… 此处隐藏：4769字，全部文档内容请下载后查看。喜欢就下载吧 ……