离散数学第十三章课件.ppt

1、1主要内容主要内容l 递推方程的定义及实例递推方程的定义及实例l 递推方程的公式解法递推方程的公式解法l 递推方程的其他解法递推方程的其他解法l 生成函数及其应用生成函数及其应用l 指数生成函数及其应用指数生成函数及其应用第十三章第十三章 递推方程与生成函数递推方程与生成函数213.1递推方程的定义及实例递推方程的定义及实例定义定义13.1 设序列设序列 a0,a1,an,简记为简记为 an.一个把一个把 an 与与某些个某些个ai(i0 and Aix do /行行4-7将将Aj插入插入A1.j 15.Ai+1Ai6.ii 17.Ai+1x 18 0)1(1)1()(WnnWnW特解特解 W

2、*(n)=P1n2+P2n,代入递推方程得代入递推方程得 (P1n2+P2n)P1(n 1)2+P2(n 1)=n 1 化简得化简得 2P1n P1+P2=n 1解得解得 P1=1/2,P2=1/2.通解为通解为 W(n)=c 1n+n(n 1)/2=c+n(n 1)/2代入初值代入初值W(1)=0，得，得c=0，W(n)=n(n 1)/2 19例例7 Hanoi塔塔 T(n)=2T(n 1)+1 T(1)=1 实例实例解解 令令 T*(n)=P代入方程代入方程 P=2P+1解得解得 P=1 T(n)=c 2n1,代入初值得代入初值得 c=1,解为解为 T(n)=2n 1.20特解的形式特解的

3、形式:指数指数f(n)为指数函数为指数函数 n，若若 是是 e 重特征根重特征根(e可以等于可以等于0)，则特，则特解为解为Pne n,其中其中P为待定常数为待定常数.例例8 求解方程求解方程 解解 特解特解 a*n=Pn22n，代入递推方程得代入递推方程得 Pn22n 4P(n 1)22n 1+4P(n 2)22n 2=2n解得解得 P=1/2.原递推方程通解原递推方程通解 代入初值得代入初值得解得解得c1=c2=1，递推方程的解，递推方程的解 5,12441021aaaaannnn1221222 nnnnnncca12222 nnnnnna21l 换元法换元法l 迭代归纳法迭代归纳法l 应

4、用实例应用实例 13.3 递推方程的其他解法递推方程的其他解法22思想：通过换元转化成常系数线性递推方程思想：通过换元转化成常系数线性递推方程 例例9 二分归并排序二分归并排序换元法换元法算法算法 Mergesort(A,p,r)/对数组对数组A的下标的下标p到到r之间的数排序之间的数排序1.if pr 2.then q(p+r)/2 /q为为p到到r的中点的中点3.Mergesort(A,p,q)4.Mergesort(A,q+1,r)5.Merge(A,p,q,r)/把排序数组把排序数组Ap.q与与Aq+1.r归并归并.Merge过程归并两个过程归并两个 n/2规模的子数组至多用规模的子数

5、组至多用 n-1次比较次比较23解解 H(k)=2 H(k1)+2k1 H(1)=1 令令 H*(k)=P1k2k+P2,解得解得 P1=P2=1 H*(k)=k2k+1通解通解 H(k)=c 2k+k2k+1 代入初值得代入初值得 c=1 H(k)=2k+k2k+1 W(n)=n log n n+1 0(1)2 ,1 )/2(2 )(WnnnWnWk求解求解24迭代归纳法：归并排序迭代归纳法：归并排序 0(1)2 ,1 )/2(2 )(WnnnWnWk1log122)12.22(2(1)2.122222)2(2122212)2(221222)2(21212)2(2 2 12 )2 (2 )(

6、2123323222121 nnnkkWWWWWWnWkkkkkkkkkkkkkkkkkkkkkk解解25迭代归纳法：错位排列迭代归纳法：错位排列例例10 Dn=(n1)(Dn1+Dn2)0,)1()1(2)1(.)1(112122211 DnDDDDDnDnDDnnnnnnnnn解：解：!1)1(.!21!111 !)1()1(.)1(4).1()1(3).1(2).1(.)1()1()1)(1()2)(1()1()1(13211232nnnnnnnDnnnnnDnnnnDnnDnnnnnnnnnn 26快速排序算法快速排序算法例例11 快速排序快速排序算法算法 Quicksort(A,p,

7、r)/p 和和 r 分别表示分别表示A首和末元素下标首和末元素下标 1.if p r 2.then qPartition(A,p,r)/划分为划分为Ap.q 1和和Aq+1.r 3.ApAq 4.Quicksort(A,p,q 1)5.Quicksort(A,q+1,r)27划分过程划分过程算法算法 Partition(A,p,r)1.x Ap /选首元素作为划分标准选首元素作为划分标准x2.i p 1 3.j r+14.while true do5.repeat j j 1 6.until A j x /Ai是从前找的第一个比是从前找的第一个比x大的元素大的元素9.if i j /继续搜索继

8、续搜索Ai到到Aj之间的范围之间的范围10 then A i A j /A i 与与A j 交换，回到行交换，回到行411.else return j /结束结束While循环循环28实例实例 27 99 0 8 13 64 86 16 7 10 88 25 90 i j 27 25 0 8 13 64 86 16 7 10 88 99 90 i j 27 25 0 8 13 10 86 16 7 64 88 99 90 i j 27 25 0 8 13 10 7 16 86 64 88 99 90 j i 16 25 0 8 13 10 7 27 86 64 88 99 90 29平均情况时

9、间复杂度分析平均情况时间复杂度分析 0)1(2),()(2)(11TnnOiTnnTni为某个常数为某个常数cnciTnTncniTnnTnini 2122111)()(21)()1()(2)(递推方程递推方程差消法化简差消法化简)()1()1()(nOnTnnnT 1)1(1)(ncnnTnnT30迭代求解迭代求解 31.1112)1(31.1111)(nncTnncnnT)(log2ln)1ln(ln131.1111212nOnxdxxnnnn )log()(nnOnT 31递归树递归树0(1),2 ,1 )/2(2 )(WnnnWnWk12111114141414142121211 kn

10、nnnnnnnnnnW(n)=n k(1+2+2k 1)=nk (2k 1)=n log n n+1分治算法的时间分析分治算法的时间分析T(n)为算法对规模为为算法对规模为n的输入的时间复杂度的输入的时间复杂度,a为子问题个数，为子问题个数，n/b为子问题规模为子问题规模,d(n)为划分和综合过程的工作量为划分和综合过程的工作量 32 1)1()()/()(TbnndbnaTnTk 10221122)/()()/(.)/()/()/(.)()/()/()(kiiikkkkkkkbndaandbnadbndabndabnTandbnadbnTanTankbbnaaloglog 当当d(n)=c时

11、，代入上式得到时，代入上式得到当当d(n)=cn时，代入上式得到时，代入上式得到33 1)(log1)()(11)(loganOkcaanOaOaacanTkakkkb banObabacababacnabannOcnknbanObabacnnbacnabcnaanTakkkkkkakiikikiikbb)(1/1/1)/()log()(1/1)/()()(loglog1010分治算法的时间分析（续）分治算法的时间分析（续）3413.4 生成函数及其应用生成函数及其应用l 牛顿二项式系数与牛顿二项式定理牛顿二项式系数与牛顿二项式定理l 生成函数的定义生成函数的定义l 生成函数的应用生成函数的应

12、用35牛顿二项式系数牛顿二项式系数 0!)1).(1(0100nnnrrrnnnr定义定义13.5 设设 r 为实数，为实数，n为整数，引入形式符号为整数，引入形式符号称为称为牛顿二项式系数牛顿二项式系数.实例实例43234341285!4)321)(221)(121(2142/16!5)(-5)(-6)-2)(-3)(-4(52-！36牛顿二项式定理牛顿二项式定理定理定理13.6（牛顿二项式定理）（牛顿二项式定理）设设 为实数，则对一切实数为实数，则对一切实数x,y，|x/y|1，有，有!)1).(1(,)(0nnnyxnyxnnn 其其中中!)1.(1)(nnmmmnmn ）nnmnnmm

13、mnn1)1(!)1).(1()1(若若=m，其中，其中m为正整数，那么为正整数，那么37重要展开式重要展开式1|1)1()1(1)1(0 zznnmzznnnmm1|1)1(1)1(0 zznnmzznnmm 022)1()1(1,2.111,1nnxnxmxxxm令令x=z，y=1，那么牛顿二项式定理就变成，那么牛顿二项式定理就变成 在上面式子中用在上面式子中用 z代替代替 z，则有，则有 38生成函数定义生成函数定义定义定义13.6 设序列设序列an，构造形式幂级数，构造形式幂级数 G(x)=a0+a1x+a2x2+an xn+称称G(x)为序列为序列an的的生成函数生成函数.例如，例如

14、，C(m,n)的生成函数为的生成函数为(1+x)m给定正整数给定正整数k,kn 的生成函数为的生成函数为 G(x)=1+kx+k2x2+k3x3+=kx 11393222202010112110)1(2)1()(,)1()()1(1)(,1)()(),()()2(xxxxxGxxdxxGxxHxxxdxxHnxxHxHxnxdxxGxnnxnnnnx 例例14 求序列求序列an的生成函数的生成函数 (1)an=7 3n (2)an=n(n+1)xxxxGnnnnn317)3(737)()1(00 解解由序列求生成函数由序列求生成函数40由生成函数求序列通项由生成函数求序列通项xxxxxxxxx

15、xGnnnnn323)2(2321221632(0102 ）1,7321,221nnannxxxxG21632(2 ）例例15 已知已知 an 的生成函数为的生成函数为求求an.解解41生成函数的应用生成函数的应用l 求解递推方程求解递推方程l 计数多重集的计数多重集的 r 组合数组合数l 不定方程的解不定方程的解l 整数拆分整数拆分 42求解递推方程求解递推方程例例16 an 5an 1+6an 2=0，a0=1,a1=2 nnnnnnnnnaxxxxxxxxG3425342531421565171)(002 G(x)=a0+a1x+a2x2+a3x3+5x G(x)=5a0 x 5a1x2

16、 5a2x3-6x2 G(x)=+6a0 x2+6a1x3+(1 5x+6x2)G(x)=a0+(a1 5a0)x 43 12,111hnhhhnkknkn例例17 xxHxhxHxhhhxxhxhxHnnnnnkknknlllkkk )()()(12211112 1)(nnnxhxH解：设解：设 hn 的生成函数为的生成函数为 求解递推方程求解递推方程44 122112212)1(1222)1()4(1222)1(1 212141(21212)41(1)(0,)()(1122112121212nnnhxnnnxnnnxnnnxxxHxxHxHnnnnnnnnnnnnn）求解递推方程求解递推方

17、程45多重集的多重集的 r 组合数组合数S=n1 a1,n2 a2,nk ak 的的 r 组合数就是不定方程组合数就是不定方程 x1+x2+xk=r xi ni i=1,2,k的非负整数解的个数的非负整数解的个数 的展开式中的展开式中 yr 的系数的系数).1).(.1)(.1()(21knnnyyyyyyyG 生成函数生成函数46实例实例例例18 S=3 a,4 b,5 c 的的10 组合数组合数解：生成函数解：生成函数G(y)=(1+y+y2+y3)(1+y+y2+y3+y4)(1+y+y2+y3+y4+y5)=(1+2y+3y2+4y3+4y4+3y5+2y6+y7)(1+y+y2+y3

18、+y4+y5)=(1+3y10+2y10+y10+)N=6 组合方案组合方案 a,a,a,b,b,b,b,c,c,c,a,a,a,b,b,b,c,c,c,c,a,a,a,b,b,c,c,c,c,c,a,a,b,b,b,b,c,c,c,c,a,a,b,b,b,c,c,c,c,c,a,b,b,b,b,c,c,c,c,c 47不定方程解的个数不定方程解的个数 0001)1(!)1).(1)()1()(!)1).(1)()1(1.)1()(rrrrrrrrkkyrrkyrrkkkyrrkkkyyyG rrkN1基本的不定方程基本的不定方程 x1+x2+xk=r，xi 为自然数为自然数 48推广的不定方

19、程推广的不定方程).(.).)(.()(111222111kkknllnllnllyyyyyyyyyyG .)1(.)1.)(1()(2222211 kkppppppyyyyyyyG带限制条件的不定方程带限制条件的不定方程 x1+x2+xk=r，li xi ni带系数的不定方程带系数的不定方程 p1x1+p2x2+pkxk=r，xi N生成函数生成函数生成函数生成函数49l 指数生成函数的定义与实例指数生成函数的定义与实例l 指数生成函数的应用指数生成函数的应用13.5 指数生成函数及其应用指数生成函数及其应用50 000)1()!(!),()(nmnnnnnexxnmxnmnmnxnmPxG

20、例例19 给定正整数给定正整数m,an=P(m,n),an的指数生成函数为的指数生成函数为 0!)(nxneenxxG 例例20 bn=1,则则bn的指数生成函数为的指数生成函数为 0 0nnnenxaxG!)(定义定义13.7 设设an为序列，称为序列，称为为 an 的的指数生成函数指数生成函数.指数生成函数的定义与实例指数生成函数的定义与实例51应用：多重集排列计数应用：多重集排列计数定理定理13.7 设设 S=n1 a1,n2 a2,nk ak为多重集，则为多重集，则 S 的的 r 排列数的指数生成函数为排列数的指数生成函数为kinxxxxfxfxfxfxGinnnnneiik,.,2,

21、1!.!21)()(.)()()(221 52实例实例.!5215!464!318!25)!4!21)(!3!21)(1)(!2()(543242322 xxxxxxxxxxxxxxGe例例21 由由1,2,3,4 组成的五位数中，要求组成的五位数中，要求1出现不超过出现不超过2次，次，但不能不出现，但不能不出现，2出现不超过出现不超过1次，次，3出现可达出现可达3次，次，4出出现偶数次现偶数次.求这样的五位数个数求这样的五位数个数.N=215解解53实例实例213!213!21!3212121)(21.)!21.)(!21()(00032222 nnnnnnnnnnxxxxxeanxnxnx

22、eeeeexxxxG解解 设方案数为设方案数为an 例例22 红、白、兰涂色红、白、兰涂色 1 n 的方格，要求偶数个为白色，的方格，要求偶数个为白色，问有多少方案？问有多少方案？54第十三章第十三章 习题课习题课主要内容主要内容l 递推方程的求解方法：公式法、换元法、迭代归纳法、生递推方程的求解方法：公式法、换元法、迭代归纳法、生成函数法成函数法l 递推方程与递归算法递推方程与递归算法l 生成函数的应用：计算多重集的生成函数的应用：计算多重集的 r 组合数、确定不定方程组合数、确定不定方程的整数解个数、计算拆分方案数、求解递推方程的整数解个数、计算拆分方案数、求解递推方程l 指数生成函数的应

23、用：计算多重集的指数生成函数的应用：计算多重集的 r 排列数排列数l 常用的计数符号：组合数、排列数、多项式系数、错位排常用的计数符号：组合数、排列数、多项式系数、错位排列数、列数、Fibonacci数数l 基本计数模型：选取问题、不定方程的解、非降路径、正基本计数模型：选取问题、不定方程的解、非降路径、正整数拆分、放球等整数拆分、放球等55基本要求基本要求l 能够使用递推方程求解计数问题能够使用递推方程求解计数问题l 能够使用生成函数或指数生成函数求解计数问题能够使用生成函数或指数生成函数求解计数问题l 掌握掌握 Fibonacci数的定义、组合意义以及相关的公式数的定义、组合意义以及相关的

24、公式.56练习练习11.已知已知 a0=0,a1=1,a2=4,a3=12 满足递推方程满足递推方程 an+c1an 1+c2an 2=0，求，求 c1 和和 c2.000211212213acacaacaca 040412121ccc解得解得 c1=4,c2=4.代入代入a0,a1,a2,a3的值得到的值得到根据已知条件得到根据已知条件得到57练习练习22求解递推方程求解递推方程 2731,2)1(01anannannn.0201bbbnnn32)1(321 nnnb 127332)1(3201nannannn用换元法用换元法.令令bn=nan,代入原递推方程得代入原递推方程得 用公式法解得

25、用公式法解得从而得到从而得到58练习练习3 3确定序列确定序列an的生成函数，其中的生成函数，其中an=3n)(61)2)(1(61)2)(1(61)(33030 xBxxnnnxxnnnxAnnnn xxdxnxdxxDxDnxdxxnndxxCxCxnndxxnnndxxBnnnxnxnnxnnxnnnxnx 11)()()1()()()1()2()1()(0001001020002003059练习练习3432)1(6)()()1(2)()()1(1)1(1()(xxCxBxxDxCxxxD 433)1()(61)(xxxBxxA 60练习练习44已知已知)1)(1(1)(2xxxA 是序

26、列是序列an的生成函数，求的生成函数，求an.xCxBAxxxxA 1)1()1)(1(1)(22 0201CBACACB解得解得A=1/4,B=3/4,C=1/4,从而得到从而得到xxxxxA 1141)1(143)1(141)(2261练习练习4 为偶数为偶数，为奇数为奇数nnnnnann22,21)1(21)1(14162练习练习55求下列求下列 n 阶行列式的值阶行列式的值 dn 21000002100012100012 nd.3,222121dddddnnn解得解得 dn=n+1.方程方程63设平面上已经有设平面上已经有n 1条直线条直线.当加入第当加入第n条直线时，它与平面条直线时

27、，它与平面上的前上的前n 1条直线交于条直线交于n 1个点个点.这些点将第这些点将第n条直线分割成条直线分割成n段，每段都增加一个区域，共增加段，每段都增加一个区域，共增加n个区域，因此得到递推个区域，因此得到递推方程方程练习练习56.平面上有平面上有 n 条直线，它们两两相交且没有三线交于一点，条直线，它们两两相交且没有三线交于一点，问这问这 n 条直线把平面分成多少个区域？条直线把平面分成多少个区域？211anaann)2(212 nnan647用三个用三个1、两个、两个2、五个、五个3可以组成多少个不同的四位数？可以组成多少个不同的四位数？如果这个四位数是偶数，那么又有多少个？如果这个四位数是偶数，那么又有多少个？练习练习7)!5!4!3!21()!21)(!3!21()(5432232xxxxxxxxxxxAe 其中其中x4的系数为的系数为!4714x 因此因此 a4=71.