组合数学(第7章7.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,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,个互相交叠的圆所形成的区域数。（互相交叠是指每两个圆相交在不同的两个点上；一般位置是指没有同心圆）。,用,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,，每条弧把穿过的区域一分为二，因此增加了,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,斐波那契（,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,个月已经成熟的兔子，第,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,= (,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,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,，对于其他递推关系，怎么知道具有什么形式呢？,奇妙的斐波那契序列,斐波那契螺旋,应用,例,：确定,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),