组合数学(第7章7.1)

《组合数学(第7章7.1)》由会员分享，可在线阅读，更多相关《组合数学(第7章7.1)（21页珍藏版）》请在装配图网上搜索。

1、*,,,,,,,,,,单击此处编辑母版标题样式,,单击此处编辑母版文本样式,,第二级,,第三级,,第四级,,第五级,,,第七章 递推关系和生成函数,,,讲授内容,,7.1,某些数列,,,,本章主要讨论涉及一个整数参数的计数问题的代数求解方法。,,错位排列计数公式的递推关系,,D,n,=,n,!,,递推关系,,(1),D,n,=(,n,,1)(,D,n,,2,+,D,n,,1,), (,n,=3,4,…),,(2),D,n,=,nD,n,,1,+(,,1),n,(,n,=2,3,…),,7.1,某些数列,（,1,）,算术数列,（等差数列）,,h,0,,,h,0,+,q,,,h,

2、0,+2,q,, …,,h,0,+,nq,,…,,递推关系：,h,n,=,h,n,-1,+,q,,,一般项：,,h,n,=,h,0,+,nq,,,前,n+1,项和：,s,n,= (,n,+1),h,0,+,q,(,n,)(,n,+1)/2,,（,2,）,几何数列,（等比数列）,,,h,0,,,qh,0,,,q,2,h,0,, …,,q,n,h,0,,…,,递推关系：,h,n,=,qh,n,-1,,,一般项：,,h,n,=,q,n,h,0,,前,n+1,项和：,s,n,=,h,0,(1-,q,n,+1,)/(1-,q,),,,一些例子,,,例,.,确定平面一般位置上的,n,个互相交叠的圆所形成的

3、区域数。（互相交叠是指每两个圆相交在不同的两个点上；一般位置是指没有同心圆）。,,用,h,n,表示,n,个交,叠的圆形成的区域数,,h,0,=1,，,h,1,=2,h,2,=4,，,h,3,=8,一般递推关,系,(,n,2,),：,,第,n,个圆与前,n,-1,个圆相交于,2(n-1),不同交点，,P,1,,,P,2,,…,,P,2(,n,,1),。,P,1,P,4,P,2,P,5,P,3,P,6,共形成,2(,n,,1),条弧,P,1,P,2,,,弧,P,2,P,3,…,,P,2(,n,,1),,1,,P,2(,n,,1),和,P,2(,n,,1),P,1,，每条弧把穿过的区域

4、一分为二，因此增加了,2(,n,,1),个区域。因此得到递推关系：,h,n,=,h,n,-1,+2(,n,,1),h,4,=14,,迭代递推关系：,h,n,=,h,n,-1,+2(,n,,1),=,h,n,-2,+2(,n,,2)+2(,n,,1),=,h,n,-3,+2(,n,,3)+2(,n,,2)+2(,n,,1),…,h,n,=,h,1,+2,,1+2,,2+…+2(,n,,2)+2(,n,,1),,,=,h,1,+2,[1+2+…+(,n,,2,)+,(,n,,1),],得到,：,,,h,n,=2+2[,n,(,n,,1)/2]=,n,2,,n,+2

5、,,斐波那契（,Fibonacci,）序列,,年初把性别相反的一对新生兔子放进围栏，从第二个月开始每月生出一对性别相反的兔子，每对新兔也从第二个月开始每月生出一对性别相反的兔子，问一年后围栏内共有多少对兔子。,,,表示幼兔,表示成兔,实线表示成长,虚线表示生殖,1:,1,2:,1,3:,2,4:,3,5:,5,6:,8,7:,13,,令,f,n,表,示,第,n,个月开始时兔子的对数。,,显然,f,1,=1,,f,2,=1,,f,3,=2,,而,f,4,=3,。,,递推关系,在第,n,个月开始，笼内的兔子可分为两个部分：第,n,,1,个月期间出生未成熟的兔子和第,n,,1,个月已经成熟的兔子

6、，第,n,,1,个月期间出的兔子数等于第,n,,2,月开始的兔子数，即：,,f,n,=,f,n,,,1,+,f,n,,2,迭代计算得到：,,f,13,=233,,定义,1,：设,f,0,=0,,f,1,=1,,那么满足递推关系,f,n,=,f,n,-1,+,f,n,-2,的序列叫斐波那契（,Fibonacci,）序列，项称为斐波那契数。,,,由归纳法原理可得：,Fibonacci,序列的部分和为,,s,n,=,f,0,+,f,1,+…+,f,n,=,f,n,+2,,1,,证明,：,f,0,+,f,1,+…+,f,n,+,f,n+,1,= (,f,n,+2,,1)+,f,n+,1,,

7、,= (,f,n,+2,+,f,n+,1,),,1,,=,f,n,+3,,1,,,斐波那契数是偶数当且仅当,n,被,3,整除。,,定理,7.1.1,斐波那契数满足公式,,n,0,观察递推关系：,,f,n,,f,n,,1,,f,n,,2,=0,,(1),,设,q,0,，,,f,n,=,q,n,满足,斐波那契递推关系,,q,2,,q,1=0,,,设,f,n,=,q,n,,,因为,f,n,,f,n,,1,,f,n,,2,=,q,n,,q,n,1,,q,n,2,=,q,n,2,(,q,2,,q,1)=0,,注意,q,0,， 因此,f,n,,f,n,,1

8、,,f,n,,2,=0,当且仅当,q,2,,q,1=0.,,(2),q,是方程,x,2,,x,1=0,的根。因此,,,那么，,和,都满足斐波那契,递推关系。对如何常数,c,1,,,c,2,，下面线性组合,可验证也满足递推关系。,,(3),根据初始值，确定常系数。,,将,f,0,=0,,f,1,=1,代入上式得到线性方程组：,c,1,+,c,2,=0,该方程组的系数矩阵可逆。,因此，方程组存在唯一解：,和,,得到斐波那契数的公式：,关于,n,的函数满足某个递推关系，称这个函数是该,,递推关系的一个解。,问题,：上述求斐波那契递推关系的解时，猜测求解函数具有特定形式,f,n,=,q,n

9、,，对于其他递推关系，怎么知道具有什么形式呢？,,奇妙的斐波那契序列,斐波那契螺旋,,应用,例,：确定,2×,n,棋盘用多米诺牌完美覆盖的方法数,h,n,。,,规定,h,0,=1.,容易看到,h,1,=1,，,h,2,=2,，,h,3,=3,。,,,h,n,=,h,n,,1,满足斐波那契递推关系。,h,n,是斐波那契数。,,,,,,,,,,,,,,+,h,n,,2,,应用,定理,7.1.2,沿,Pascal,三角形左边向上对角线上的二项式系数和是,Fibonacci,数,,,即,,其中,，,k,=,,(,n,+1)/2,,。,,证明,：定义,,或者,,需要,证明,g,n,满足,Fibonacci,递推关系并有相同初始值。,g,n,,1,+,g,n,,2,=,=…,=,,小结,一些与自然数,n,相关的计数问题，有时求递推关系更容易，可以通过给出递推关系来解决相关的计数问题。,,本章的重点是递推关系的求解。,,作业,,习题,7.8 (P.162),,1.,设,f,0,,,f,1,,…,,f,n,,…,表示斐波那契序列。,…,,,i), iii),,3.,证明下列关于斐波那契数的结论。,,i), ii) , v),,