组合数学课件第六章递推关系

组合数学课件目录（1）第1章什么是组合数学1.1引例 1.2组合数学研究对象、内容和方法第2章鸽巢原理2.1鸽巢原理：简单形式2.2鸽巢原理：加强形式2.3Ramsey定理2.4鸽巢原理与Ramsey定理的应用本章小结习题第3章排列与组合3.1两个基本的计数原理3.2集合的排列与组合3.3多重集的排列与组合本章小结习题第四章二项式系数4.1二项式定理4.2组合恒等式4.3非降路径问题4.4牛顿二项式定理4.5多项式定理4.6基本组合计数的应用本章小结习题第五章包含排斥原理5.1包含排斥原理5.2多重集的r-组合数5.3错位排列5.4有限制条件的排列问题5.5有禁区的排列问题本章小结习题目录目录（2）第六章递推关系6.1Fibonacci数列6.2常系数线性齐次递推关系的求解6.3常系数线性非齐次递推关系的求解6.4用迭代和归纳法求解递推关系本章小结习题第七章生成函数7.1生成函数的定义和性质7.2多重集的r-组合数7.3正整数的划分7.4指数生成函数与多重集的排列问题7.5Catalan数和Stiring数本章小结习题第八章Polya定理8.1置换群中的共轭类与轨道8.2Polya定理的特殊形式及其应用本章小结习题**********************课程第6章递推关系本章主要介绍递推关系的建立及几种常见的求解方法： 6.1Fibonacci数列 6.2常系数线性齐次递推关系的求解 6.3常系数线性非齐次递推关系的求解 6.4用迭代和归纳法求解递推关系第6章递推关系教学目标：1．掌握几种递推关系的建立方法；2．理解并掌握常系数线性齐次及非齐次递推关系的求解方法；3．能运用迭代归纳法求解递推关系；4．记住并理解Fibonacci数的定义及递推公式，会推导Fibonacci数的一些性质，能运用它们解决一些组合计数问题。重点：递推关系的建立方法、常系数线性齐次及非齐次递推关系的求解方法、Fibonacci数和Catalan数的定义、递推公式及性质难点：Catalan数的定义、递推公式及性质第6章递推关系§6.1递推关系定义§6.1递推关系的建立定义6.1设{H(n)}为一序列，把该序列中H(n)和它前面几个H(i)(0≤i≤n-1)用等号（或大于、小于号）关联起来的方程称做一个递推关系（递归关系）。如第3章的错排数Dn=(n-1)(Dn-1+Dn-2)，(n≥3)和关系式an=3an-1，(n≥1)都是递推关系。如a0=d0,a1=d1,…,ak=dk，di为常数(i=0,1,…,k)，称为递推关系的初值。如D1=0,D2=1作为初值即可惟一的确定序列(D0,D1,…,Dn,…)，a0=1作为初值即可惟一的确定序列(1,3,32,…,3n,…)。将递推关系和初值结合起来称为带初值的递推关系。如§6.1递推关系建立例1-1§6.1递推关系的建立（Fibonacci数列）例题例1、在一个平面上有一个圆和n条直线，这些直线中的每一条在圆内都同其他的直线相交。如果没有多于三条的直线相交于一点，试问这些直线将圆分成多少个不同区域？§6.1递推关系建立例1-2§6.1递推关系的建立例题§6.1递推关系建立例2§6.1递推关系的建立例题例2、在一个平面中，有n个圆两两相交，但任二个圆不相切，任三个圆无公共点，求这n个圆把平面分成多个区域？解：设这n个圆将平面分成an个区域。如图。易见，a1=2,a2=4。现在假设前n-1个圆将平面分成了an-1个区域，当加入第n个圆时，由题设这个圆与前面的n-1个圆一定交于2(n-1)个点，这2(n-1)个点把第n个圆分成2(n-1)条弧，而每条弧正好将前面的n-1个圆分成的区域中的其经过的每个区域分成2个区域，故新加入的第n个圆使所成的区域数增加了2(n-1)。因此可以建立如下带初值的递推关系：求解这个递推关系可以得到问题的解答。§6.1递推关系建立例3-1§6.1递推关系的建立例题例3、“Fibonacci兔子问题”也是组合数学中的著名问题之一。这个问题是指：从某一年某一月开始，把雌雄各一的一对兔子放入养殖场中，从第二个月雌兔每月产雌雄各一的一对新兔。每对新兔也是从第二个月起每月产一对兔子。试问第n个月后养殖场中共有多少对兔子？§6.1递推关系建立例3-1表示幼兔表示成兔实线表示成长虚线表示生殖1:12:13:24:35:56:87:13§6.1递推关系的建立§6.1递推关系建立例3-2§6.1递推关系的建立例题注：以上各例均为经典组合数学问题，在算法分析中常用；对普通的递推关系无一般规则可解。§6.1Fibonacci数列应用及性质例：确定2×n棋盘用多米诺牌完美覆盖的方法数hn。规定h0=1.容易看到h1=1，h2=2，h3=3。hn=hn1满足斐波那契递推关系。hn是斐波那契数。§6.1递推关系的建立Fibonacci数列在组合计数中的应用+hn2  再如，一个人站在“梯子格”的起点处向上跳，从格外只能进入第1格，从格中，每次可向上跳一格或两格，问：可以用多少种方法，跳到第n格？§6.1递推关系的建立Fibonacci数列在组合计数中的应用解：设跳到第n格的方法有种。由于他跳入第1格，只有一种方法；跳入第2格，必须先跳入第1格，所以也只有一种方法，从而而能一次跳入第n格的，只有第和第两格，因此，跳入第格的方法数，是跳入第格的方法数，加上跳入第格的方法数之和。即。综合得递推公式容易算出，跳格数列就是斐波那契数列1，1，2，3，5，8，13，21，34，…§6.1递推关系的建立Fibonacci数列在组合计数中的应用§6.1Fibonacci数列应用及性质 斐波那契螺旋线数§6.1递推关系的建立类似的例子奇妙的斐波那契序列6.1Fibonacci数列应用及性质 树杈的数目13853211§6.1递推关系的建立类似的例子§6.1Fibonacci数列应用及性质（1）§6.1递推关系的建立Fibonacci数列性质1.Fibonacci数可以表示为二项式系数之和，即证明当时，有，即，所以只要证明下面的等式成立，即证用归纳法。当时，有成立。假设对等式都成立，则有§6.1Fibonacci数列应用及性质由归纳法，命题成立。§6.1递推关系的建立Fibonacci数列性质§6.1Fibonacci数列应用及性质（2）§6.1递推关系的建立Fibonacci数列性质2.Fibonacci数证明把以上各式的左边和右边分别相加，得§6.1Fibonacci数列应用及性质（3-4）§6.1递推关系的建立Fibonacci数列性质3.Fibonacci数证明把以上各式的左边和右边分别相加，得4.Fibonacci数证明由性质2和3即得.§6.1Fibonacci数列应用及性质（5）§6.1递推关系的建立Fibonacci数列性质5.证明把以上各式的左边和右边分别相加，得§6.1Fibonacci数列应用及性质（6）§6.1递推关系的建立Fibonacci数列性质6.证明由归纳法，等式成立。对进行归纳.当时，有成立，假设对一切有等式成立，则§6.1Fibonacci数列应用及性质§6.1递推关系的建立Fibonacci数列性质关于Fibonacci数列的性质还有许多，习题上也列出了一部分，这里就不一一介绍。利用这些性质，我们可以将比较大的n的Fibonacci数化成较小的的Fibonacci数，从而使计算更为方便。§6.2常系数线递推关系次递推关系§6.2常系数线性齐次递推关系定义6.2若{H(n)}中相邻k+1项满足H(n)=a1H(n-1)+a2H(n-2)+…+akH(n-k)，(n≥k)称之为{H(n)}的k阶常系数线性齐次递推关系。其中ai(i=1,2,…,k)是常数，且ak≠0。该递推关系还可以写作H(n)-a1H(n-1)-a2H(n-2)-…-akH(n-k)=0.H(0)=d0,H(1)=d1,…,H(k-1)=dk-1称为初始条件，其中di(i=0,2,…,k-1)是常数；定义6.3C(x)=xk-a1xk-1-a2xk-2-…-ak称为上述递推关系的特征多项式；C(x)=0称为上述递推关系的特征方程；该方程的k个根q1,q2,…qk称为上述递推关系的特征根.其中qi(i=1,2,…,k)是复数.§6.2常系数线递推关系次递推关系定理6.1对此，有下面的定理定理6.1§6.2常系数线性齐次递推关系设k阶常系数线性齐次递推关系{H(n)}为若q≠0,H(n)=qn是上述递推关系的解，当且仅当q是上述特征方程的解。证明：若q0,H(n)=qn是递推关系的解qn=a1qn-1+a2qn-2+…+akqn-k(n≥k)qk=a1qk-1+a2qk-2+…+akq是特征方程xk-a1xk-1-a2xk-2-…-ak=0的根。证毕。§6.2常系数线递推关系次递推关系定理6.2定理6.2若都是齐次递推关系的解，那么也是齐次递推关系的解。证:由是齐次递推关系的解知§6.2常系数线性齐次递推关系§6.2常系数线性齐次相异特征根定理6.3§6.2常系数线性齐次递推关系6.2.1相异特征根的解法定理6.3若q1,q2,…,qk,为上述递推关系的特征根（相异），c1,c2,…,ck为任意常数，则an=c1q1n+c2q2n+…+ckqkn为上述递推关系的解。§6.2常系数线性齐次相异特征根定义6.4§6.2常系数线性齐次递推关系6.2.1相异特征根的解法定义6.4如果对于递推关系H(n)=b1H(n-1)+b2H(n-2)+…+bkH(n-k)的每个解h(n)都可以选择一组常数使得成立，则称是递推关系的通解，其中为任意常数。§6.2常系数线性齐次相异特征根定理6.4§6.2常系数线性齐次递推关系6.2.1相异特征根的解法定理6.4若q1,q2,…,qk为上述递推关系的特征根（相异），则an=c1q1n+c2q2n+…+ckqkn为上述递推关系的通解，其中ci由初始条件确定。§6.2常系数线性齐次例1§6.2常系数线性齐次递推关系5.2.1相异特征根的解法例题§6.2常系数线性齐次例2§6.2常系数线性齐次递推关系6.2.1相异特征根的解法例题§6.2常系数线性齐次例3-1§6.2常系数线性齐次递推关系6.2.1相异特征根的解法例题例3、用字母a,b和c组成长度是n的字，如果要求没有两个a相邻，问这样的字有多少个？解设h(n)是所求的字的个数，n≥1.易见，长为1的且没有两个a相邻的字有a,b和c，所以h(1)=3.长为2的没有两个a相邻的字有ab,ac,ba,bb,bc,ca,cb,cc.所以h(2)=8.设n≥3,如果字中的第一个字母是a，那么第二个字母只能是b或c,其余的字母可以有h(n-2)种方式来选择，因此以a开头的字有2h(n-2)个.如果字中的第一个字母是b,那么这样的字有h(n-1)个，同理以c开头的字也有h(n-1)个，由加法法则得§6.2常系数线性齐次例3-2§6.2常系数线性齐次递推关系6.2.1相异特征根的解法例题例3、用字母a,b和c组成长度是n的字，如果要求没有两个a相邻，问这样的字有多少个？§6.2常系数线性齐次相同特征根定理6.5§6.2常系数线性齐次递推关系6.2.2相同特征根的解法定理6.5若q为上述递推关系的特征方程C(x)=0的一个m重特征根，则qn,nqn,…,nm-1qn为该递推关系的解。证明：令P(x)=xk-b1xk-1-b2xk-2-…-bk，Pn(x)=xn-kP(x)=xn-b1xn-1-b2xn-2-…-bkxn-k。由于q是P(x)=0的m重根，故q也是Pn(x)=0的m重根，由高等代数的知识知，q也是P'n(x)=0的(m-1)重根，那么q也是xP'n(x)=0的(m-1)重根，即q是方程nxn-b1(n-1)xn-1-b2(n-2)xn-2-…-bk(n-k)xn-k=0的(m-1)重根。类似地，q是方程n2xn-b1(n-1)2xn-1-b2(n-2)2xn-2-…-bk(n-k)2xn-k=0的(m-2)重根。…一般地，对任意的i,i＜m,q是方程nixn-b1(n-1)ixn-1-b2(n-2)ixn-2-…-bk(n-k)ixn-k=0的(m-i)重根。即有niqn-b1(n-1)iqn-1-b2(n-2)iqn-2-…-bk(n-k)iqn-k=0。分别令i=1,2,…,m-1，知nqn,n2qn,…,nm-1qn都是递推关系an=b1an-1+b2an-2+…+bkan-k的解，而qn是递推关系an=b1an-1+b2an-2+…+bkan-k的解在定理6.1中已经证明。故定理得证。§6.2常系数线性齐次相同特征根定理6.6-1§6.2常系数线性齐次递推关系6.2.2相同特征根的解法定理6.6§6.2常系数线性齐次相同特征根定理6.6-2§6.2常系数线性齐次递推关系5.2.2相同特征根的解法§6.2常系数线性齐次例4§6.2常系数线性齐次递推关系6.2.2相同特征根的解法例题§6.2常系数线性齐次例5§6.2常系数线性齐次递推关系6.2.2相同特征根的解法例题§6.2常系数线性齐次例6§6.2常系数线性齐次递推关系6.2.2相同特征根的解法例题§6.2常系数线性齐次例7§6.2常系数线性齐次递推关系5.2.2相同特征根的解法例题§6.2常系数线性齐次注意事项§6.2常系数线性齐次递推关系6.2.2相同特征根的解法注意：建立递推关系关系时可考虑某个特定数值，如第一个、最后一个等；k次递推关系需要k个初值，一般从a0开始（不妨假设）；结果需要验证（n=k+1,k+2,…）。§6.3常系数线性非齐次定义§6.3常系数线性非齐次递推关系定义6.4若{H(n)}中相邻k+1项满足:H(n)=b1H(n-1)+b2H(n-2)+…+bkH(n-k)+f(n)，(n≥k)称之为{H(n)}的k阶常系数线性非齐次递推关系。其中bi(i=1,2,…,k)是常数，且bk≠0，f(n)≠0。若f(n)=0，称=b1H(n-1)+b2H(n-2)+…+bkH(n-k)为上述递推关系导出的常系数线性齐次递推关系。§6.3常系数线性非齐次定理6.7-1§6.3常系数线性非齐次递推关系定理6.7设非线性齐次递推关系为：an=b1an-1+b2an-2+…+bkan-k+f(n)§6.3常系数线性非齐次定理6.7-2§6.3常系数线性非齐次递推关系定理6.7§6.3常系数线性非齐次定理6.7-3§6.3常系数线性非齐次递推关系定理6.7 注：定理6.7指出，若要求一个常系数线性非齐次递推关系式的通解，必须先求出这个递推关系所导出的常系数线性齐次递推关系的通解，然后再求这个递推关系式的一个特解，将其相加即可。然而，求一个非齐次线性递推关系的特解，通常没有系统的方法，但当函数f(n)是某些特殊形式时，才有一些规范的求法。§6.3常系数线性非齐次特殊形式§6.3常系数线性非齐次递推关系 可针对f(n)的某些特定形式，转化为齐次性。§6.3常系数线性非齐次例1§6.3常系数线性非齐次递推关系例题§6.3常系数线性非齐次例2-1§6.3常系数线性非齐次递推关系例题例2、“Hanoi塔”问题：n个大小不一的圆盘依半径的大小，从下而上的套在柱子A上。如图所示。现要求将所有的圆盘从柱子A上全部移到柱子C上，每次只允许从一根柱子上转移一个圆盘到另一根柱子上，且在转移过程中不允许出现大圆盘放到小圆盘上。试问至少要转移多少次才能将柱子上的n个圆盘全部转移到柱子C上去？§6.3常系数线性非齐次例2-2§6.3常系数线性非齐次递推关系例题§6.3常系数线性非齐次例2-3§6.3常系数线性非齐次递推关系例题§6.3常系数线性非齐次例3§6.3常系数线性非齐次递推关系例题§6.3常系数线性非齐次例4§6.3常系数线性非齐次递推关系例题例4、求递归关系an+2an-1+an-2=2n的通解。§6.3常系数线性非齐次例5§6.3常系数线性非齐次递推关系例题例5、求递归关系an-4an-1+4an-2=2n的通解。§6.3常系数线性非齐次例6§6.3常系数线性非齐次递推关系例题例6、求Sn=1+2+3+…+n。§6.3常系数线性非齐次例7§6.3常系数线性非齐次递推关系例题例7、求Sn=12+22+32+…+n2。§6.3常系数线性非齐次例8§6.3常系数线性非齐次递推关系例题例8、求Sn=13+23+33+…+n3。§6.4迭代法例1§6.4迭代法与归纳法针对上述k阶常系数线性（非）齐次递推关系求解方法，当k较大时，面临着解高次方程和高阶线性方程组的困难；而且对一般的非齐次递推关系无系统的方法。例题§6.4迭代法例2-1§6.4迭代法与归纳法例题例2、给定n个实数a1,a2,…,an,可以用多少种不同的方法构成它们的乘积？在这里我们认为相乘的顺序不同也是不同的方法，如(a1×a2)×a3与a1×(a2×a3)是不同的方法.解：设h(n)表示这n个数构成乘积的方法数.显然h(1)=1.假设n-1个数a1,a2,…,an-1的乘积已经构成，有h(n-1)个.任取其中的一个乘积，它是由n-2次乘法得到的.对于其中的某一次相乘的两个因式，把an乘到一个因式的左边或右边，或乘到另个因式的左边或右边，共有四种加入an的方法.再根据加法法则，对于这个乘积加入an的方法是4(n-2)种.此外，还可以把an分别乘在整个乘积的左边或右边，所以加入an的方法数是4(n-2)+2=4n-6.根据以上的分析可以得到该问题的递推关系§6.4迭代法例2-2§6.4迭代法与归纳法例题§6.4迭代法例3§6.4迭代法与归纳法例题§6.4归纳法例4§6.4迭代法与归纳法例题§6.4归纳法例5§6.4迭代法与归纳法例题第6章小结本章小结本章讨论了如何使用递推关系的方法解决组合问题，这种方法适合利用计算机进行一步一步的计算。主要介绍了常系数齐次递推关系、常系数非齐次递推关系、迭代法、归纳法等常用的方法，最后介绍了几种经典的递推关系。通过学习，应该了解到一个序列既可以用它的母函数来表示，也可以用对应的递推关系来表示，只是各自的侧重点不同，利用上述方法解决组合问题是具有一定的技巧性的。同时希望能培养了解各种解法之间的相互关系的能力。重点需要掌握根据实际问题列出递推关系的技巧，列出递推关系的关键，常常是如何对所要计数的对象进行合理的分类，也就是要确定一个合理的分类。同时需要掌握解某几种线性、非线性常系数递推关系的方法，掌握几个经典的递推关系及其组合含义。第6章习题习题P1131、3、5、10、11、12。结束