组合数学ch06省公开课一等奖全国示范课微课金奖课件

第六章递推关系计算机科学与技术学院吉林大学第1页主要内容§6.1递推关系建立§6.2常系数线性齐次递推关系求解§6.3常系数线性非齐次递推关系求解§6.4用生成函数求解递推关系§6.5用迭代和归纳法求解递推关系第2页§6.1递推关系建立错排数Dn递推关系

第3页Stirling数递推关系:S2（n+1,k)=S2(n,k-1)+k*S2(n,k)第三章性质3.5.1第4页定义6.1

给定一个数列H(0),H(1),…,H(n),…

若存在整数n0，使当n≥n0时，能够用等号（或大于号，小于号）将H(n)与其前面一些项H(i)，0≤i≤n，联络起来式子叫做一个递推关系。递推关系(用等号)也称递归关系，递归方程。

第5页从本质上讲，递推关系是研究整变量函数或者说是研究数列，与此对应是连续论域中微分方程。所以，我们能够类似方法对它们进行研究。

第6页f(n)代表了某个组累计数问题解，所以递推关系是组累计数主要工具求出序列通项表示式f(n)求不出f(n)显式，能够计算出f(n)值或者范围第7页递推关系惯用求解方法（1）特征根法；(§6.2,§6.3)（2）迭代法和归纳法；(§6.5)（3）生成函数法；（§6.4）第8页例6.1.2Fibonacci数列问题是一个古老数学问题，是于1202年提出。问题表述以下:把一对兔子（雌、雄各一只）在某年开始放到围栏中，每个月这对兔子都生出一对新兔，其中雌、雄各一只。由第二个月开始，每对新兔每个月也生出一对新兔，也是雌、雄各一只。问n个月后围栏中有多少对兔子？这是一个数学模型形象表示，不能真正用来表示兔子繁殖规律。第9页棋盘覆盖问题，用多米诺骨牌（能够看成一个2×1大小方格）完全覆盖一个2×n棋盘。覆盖方案数等于Fibonacci数f(n).另外一个例子，也表达出递推关系思想：例6.1.1有n级台阶，某人从下向上走，若每次只能跨1级或者2级，问他从地面走到第n级有多少种不一样方法?甚至是更详细问题，比如n=10.第10页例6.1.3（Hanoi塔问题）现有A，B，C三根立柱以及n个大小不等中空圆盘，这些圆盘自小到大套在A柱上形成塔形，如图6.1.1所表示，要把n个圆盘从A柱上搬到C柱上，并保持原来次序不变，要求每次只能从一根立柱上拿下一个圆盘放在另一根立柱上，且不允许大盘压在小盘上，问最少要搬多少次？

第11页第12页

解：记f(n)为n个圆盘从A柱搬到C柱所需最小次数.整个搬运过程可分成三个阶段；（1）将套在A柱上面n-1个圆盘从A柱按要求搬到B柱，搬动次数为f(n-1);（2）把A柱上最下面那个圆盘搬到C柱上，搬动次数为1;（3）把B柱上n-1个圆盘按要求搬到C柱上，搬动次数为f(n-1);由加法标准知，f(n)=2f(n-1)+1又显然f(1)=1，所以有以下带有初值递推关系:

f(n)=2f(n-1)+1f(1)=1

第13页则称作k阶常系数线性齐次递推关系(6.2.1)定义6.2.1设k是给定正整数，若数列相邻k+1项间满足关系:假如满足下面三个条件都是常数

第14页(6.2.2)

假如有一个数列代入递推关系（6.2.1），使得其对任何n≥k都成立，则称这个数列是递推关系（6.2.1）解。

常系数线性齐次递推关系普通形式为

第15页定义6.2.2方程

(6.2.2)

叫做递推关系(6.2.2)特征方程，它k个根q1，q2……qk叫做该递推关系特征根。其中qi(i=1,2,…,k)是复数。§6.2常系数线性齐次递推关系求解

特征根法第16页(一)无重特征根引理6.2.1

设q是一个非零复数，则f(n)＝qn是递推关系(6.2.2)一个解当且仅当q是它一个特征根。引理6.2.2设h1(n)和h2(n)是递推关系(6.2.2)两个解，b1和b2是任意常数，则b1h1(n)＋b2h2(n)也是递推关系(6.2.2)解。第17页定义6.2.3

假如对于递推关系(6.2.2)每个解h(n)都能够选择一组常数c1’，c2’，c3’，……ck’,使得h(n)＝c1’q1n＋c2’q2n＋……＋ck’qkn成立，则称b1q1n＋b2q2n＋……＋bkqkn是递推关系通解，其中b1b2……bk为任意常数。第18页定理6.2.1

设q1，q2，……qk是递推关系(6.2.2)k个不相等特征根，则

f(n)＝b1q1n＋b2q2n＋……＋bkqkn是递推关系(6.2.2)通解.第19页例6.2.1求解关于Fibonacci数递推关系第20页第21页第22页第23页例6.2.2求解递推关系

第24页第25页第26页(二)有重特征根定理6.2.2设q1，q2，……qt是递推关系(6.2.2)不相等特征根，ei是qi重数,则递推关系(6.2.2)通解

f(n)=f1(n)+f2(n)+……+ft(n)其中第27页例6.2.4求解递推关系第28页对第29页对通解为解方程组，得c1=5,c2=2,c3=-4所以原递推关系解为f（n)=5*2n+2n*2n-4*3n第30页补例求解递推关系第31页(一)普通形式§6.3常系数线性非齐次递推关系求解(6.3.1)(6.3.2)

对应齐次递推关系为

第32页定理6.3.1

k阶常系数线性非齐次递推关系（6.3.1）通解是递推关系（6.3.1）特解加上其对应齐次递推关系（6.3.2）通解。

第33页对于普通g(n)没有普遍解法，只对一些简单情况能够用待定系数法求f*(n)

。第34页例6.3.1求解递推关系

第35页比较等式两边解：因为4不是特征方程根，所以该递推关系非齐次特解为，将其代入递推关系，得系数，得

从而a=2.第36页而对应齐次递推关系通解为由定理6.3.1知，非齐次递推关系通解为

由初值得从而

故第37页例6.3.2

求解递推关系解因为3是特征方程根，所以该递推关系特解为

将它代入递推关系，得到a=6第38页从而非齐次递推关系通解为再由初值求得于是第39页