第二十二章组合计数方法 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 塔变种，柱子个数增加，允许盘子相等. 递推方程的实例（续）