北京大学：《离散数学》离散数学之二《代数结构与组合数学》第22章 组合计数方法 22.1 递推方程的公式解法 22.2 递推方程的其他解法

第二十二章组合计数方法 221递推方程的公式解法 ■222递推方程的其他解法 ■223生成函数的定义及其性质 224生成函数的应用 225指数生成函数及其应用 226高级计数

1 第二十二章 组合计数方法 „ 22.1 递推方程的公式解法 „ 22.2 递推方程的其他解法 „ 22.3 生成函数的定义及其性质 „ 22.4 生成函数的应用 „ 22.5 指数生成函数及其应用 „ 22.6 高级计数

221递推方程的公式解法 递推方程的定义 递推方程的实例 ■常系数线性递推方程的求解 常系数线性递推方程定义 公式解法 递推方程在计数问题中的应用

2 22.1 递推方程的公式解法 „ 递推方程的定义 „ 递推方程的实例 „ 常系数线性递推方程的求解 „ 常系数线性递推方程定义 „ 公式解法 „ 递推方程在计数问题中的应用

递推方程的定义 设序列n,a,…,an…,简记为{an}, 个把an与某些个a;(i<n)联系起来的等式 叫做关于序列{an}的递推方程 当给定递推方程和适当的初值就唯一确定了序列 例: Fibonacci数列:1,1,2,3,5,8, Fibonacci数列的递推方程A=n1+fm2 初值f6=1,f=1 阶乘计算数列:1,2,6,24,5!, 递推方程F(mn)=nF(m-1) 初值F(1)=1

3 递推方程的定义 设序列 a 0, a 1, …, a n, …, 简记为 { a n}, 一个把 a n与某些个 a i （ i < n）联系起来的等式 叫做关于序列 { a n} 的递推方程 当给定递推方程和适当的初值就唯一确定了序列. 例：Fibonacci 数列： 1，1，2，3，5，8，… ， Fibonacci 数列的递推方程 fn = fn-1 + fn-2 初值 f0 = 1，f1 = 1 阶乘计算数列： 1，2，6，24，5！，…, 递推方程 F( n) = nF( n-1) 初值 F(1) = 1

递推方程的实例 例1一个编码系统用8进制数字对信息编码,一个码是有效的 当且仅当含有偶数个7,求n位长的有效码字有多少个? 解设所求有效码字为an个 an=7an-1t 8 n-1 -1 an=0m1+81 1=7 解得an=(6"+8")2 n-1位长的八进制串 第n位 xx=0,1,2,3,4,5,6 含偶数个7ax1 ←y7 含奇数个781-a21

4 例 1 一个编码系统用 8 进制数字对信息编码，一个码是有效的 当且仅当含有偶数个 7, 求 n 位长的有效码字有多少个？ 解 设所求有效码字为 an个 an = 7an-1 + 8n-1− an-1 an = 6an-1 + 8n-1, a1=7 解得 an=(6n+8n)/2 递推方程的实例

递推方程的实例(续) 例2Hano塔问题 B C T(n)=2T(n-1)+1,T(1)=1 解得T(m)=2"-1 1秒移1个,64个盘子要多少时间?(5000亿年) 思考:是否存在更好的解法? Reve难题: Hanoi塔变种,柱子个数增加,允许盘子相等

5 例2 Hanoi 塔 问题 T(n) = 2 T(n-1) + 1，T(1) = 1 解得 T(n) = 2n −1 1 秒移 1 个，64 个盘子要多少时间？（5000 亿年） 思考：是否存在更好的解法？ Reve 难题：Hanoi 塔变种，柱子个数增加，允许盘子相等. 递推方程的实例（续）

递推方程的实例(续) 例3哪种排序算法在最坏情况下复杂度比较低? 插入排序、归并排序 插入排序 W(n)=W(n-1)+n-1 W(1)=0 解得W(n)=On 归并排序,不妨设n=2k W(n)=2W(m/2)+n-1 W(1)=0 解得Wn)=O( nlogn)

6 例 3 哪种排序算法在最坏情况下复杂度比较低？ 插入排序、归并排序 插入排序 W(n) = W(n −1) + n −1 W(1) = 0 解得 W(n) = O(n2). 归并排序，不妨设 n = 2k. W(n) = 2W(n/2) + n－1 W(1) = 0 解得 W(n) = O(nlogn) 递推方程的实例（续）

常系数线性齐次递推方程求解 常系数线性齐次递推方程的定义 H(m)-a1H(n-1)-a2H(n-2)-…-akH(n-k)=0 lH(0)=b,H()=b,H(2)=b2…,H(k-1)=b 其中a1,a2…,ak为常数,ak≠0 称为k阶常系数线性齐次递推方程 b,b1,…,bk1为k个初值 实例: fibonacci数列的递推方程

7 常系数线性齐次递推方程的定义    = = = − = − − − − − − − = 0 1 2 − 1 1 2 ( 0 ) , ( 1 ) , ( 2 ) , ... , ( 1 ) ( ) ( 1 ) ( 2 ) ... ( ) 0 k k H b H b H b H k b H n a H n a H n a H n k 其中 a 1 , a 2,…, a k为常数， a k ≠ 0 称为 k 阶常系数线性齐次递推方程 b 0, b 1, …, b k-1 为 k 个初值 实例：Fibonacci 数列的递推方程 常系数线性齐次递推方程求解

常系数线性齐次递推方程的公式解法 特征方程、特征根 ■递推方程的解与特征根的关系 ■解的线性性质 无重根下通解的结构 ■求解实例 ■有重根下通解结构 求解实例

8 常系数线性齐次递推方程的公式解法 „ 特征方程、特征根 „ 递推方程的解与特征根的关系 „ 解的线性性质 „ 无重根下通解的结构 „ 求解实例 „ 有重根下通解结构 „ 求解实例

特征方程与特征根 H(m)-a1H(n-1)-a2H(n-2) H(n-k)=0 H(0)=b0,H(1)=b1,H(2)=b2,…,H(k-1)=bk-1 特征方程x-a1x1 ak 0 特征方程的根称为递推方程的特征根 实例 递推方程fn=fn1+fm2 特征方程x2x1=0 特征根 +√51-√5 2 2

9 特征方程与特征根    = = = − = − − − − − − − = 0 1 2 − 1 1 2 ( 0 ) , ( 1 ) , ( 2 ) , ... , ( 1 ) ( ) ( 1 ) ( 2 ) ... ( ) 0 k k H b H b H b H k b H n a H n a H n a H n k 特征方程 xk − a 1 xk-1 − … − a k = 0， 特征方程的根称为递推方程的特征根 实例 递推方程 fn = fn-1 + fn-2 特征方程 x 2 −x−1= 0 特征根 2 1 5 , 2 1 + 5 −

递推方程解与特征根的关系 定理1q是非零复数,则q是递推方程的解 兮q是它的特征根 证:q是递推方程的解 n-2 n-k 分q-1q-m2q 0 n-k, k -1 -2 兮q(q-01q 2 k)=0 -2 分q-1q k=0 台q是它的特征根

10 定理 1 q 是非零复数，则 qn是递推方程的解 ⇔ q 是它的特征根 证： qn是递推方程的解 ⇔ q n −a1q n-1 − a2q n-2 − … − akq n-k = 0 ⇔ q n-k(qk −a1qk-1− a2qk-2 − …− ak) = 0 ⇔ q k − a1q k-1 − a2q k-2 − … − ak = 0 ⇔ q 是它的特征根 递推方程解与特征根的关系