组合数学第7章7.1

1、第七章 递推关系和生成函数,前言,数学的一种重要思想 递推思想体现了世界上许多事物现象变化所遵循的一种前因和后果的关系，具有广泛的应用。 计算机科学中，例如著名的“梵塔问题”，在算法分析中有着广泛的应用。,讲授内容,7.1 某些数列 本章主要讨论涉及一个整数参数的计数问题的代数求解方法。,错位排列计数公式的递推关系,Dn=n!,递推关系 (1) Dn=(n1)( Dn2+Dn1), (n=3,4,) (2) Dn=nDn1+(1)n (n=2,3,),7.1 某些数列,（1）算术数列（等差数列） h0, h0+q, h0+2q, , h0+nq, 递推关系：hn= hn-1+q 一般项： hn

2、= h0+nq 前n+1项和：sn= (n+1)h0+q(n)(n+1)/2 （2）几何数列（等比数列） h0, qh0, q2h0, , qnh0, 递推关系：hn= qhn-1 一般项： hn= qnh0 前n+1项和：sn= h0(1-qn+1)/(1-q),一些例子,例. 确定平面一般位置上的n个互相交叠的圆所形成的区域数。（互相交叠是指每两个圆相交在不同的两个点上；一般位置是指没有同心圆）。,用hn表示n个交叠的圆形成的区域数,h0=1， h1=2,h2=4，,h3=8,一般递推关系(n2)： 第n个圆与前n-1个圆相交于2(n-1)不同交点，P1, P2, P2(n1)。,P1,P

3、4,P2,P5,P3,P6,共形成2(n1)条弧P1P2, 弧P2P3 , P2(n1) 1 P2(n1)和P2(n1) P1，每条弧把穿过的区域一分为二，因此增加了2(n1)个区域。因此得到递推关系：,hn=hn-1+2(n1),h4=14,迭代递推关系：,hn= hn-1+2(n1),= hn-2+2(n2)+2(n1),= hn-3+2(n3)+2(n2)+2(n1),hn=h1+21+22+2(n2)+2(n1) = h1+21+2+(n2)+(n1),得到： hn=2+2n(n1)/2=n2n+2,斐波那契（Fibonacci）序列,年初把性别相反的一对新生兔子放进围栏，从第二个月开

4、始每月生出一对性别相反的兔子，每对新兔也从第二个月开始每月生出一对性别相反的兔子，问一年后围栏内共有多少对兔子。,表示幼兔,表示成兔,实线表示成长,虚线表示生殖,1: 1,2: 1,3: 2,4: 3,5: 5,6: 8,7: 13,令fn表示第n个月开始时兔子的对数。 显然 f1=1, f2=1, f3=2, 而f4=3。 递推关系 在第n个月开始，笼内的兔子可分为两个部分：第n1个月期间出生未成熟的兔子和第n1个月已经成熟的兔子，第n1个月期间出的兔子数等于第n2月开始的兔子数，即：,fn= fn 1+fn 2,迭代计算得到： f13=233,定义1：设f0=0, f1=1, 那么满足递推

5、关系fn= fn-1+fn-2的序列叫斐波那契（Fibonacci）序列，项称为斐波那契数。 由归纳法原理可得：Fibonacci序列的部分和为 sn=f0+f1+fn= fn+21 证明： f0+f1+fn+fn+1= (fn+21)+fn+1 = (fn+2+fn+1)1 = fn+31 斐波那契数是偶数当且仅当n被3整除。,定理7.1.1 斐波那契数满足公式,n0,观察递推关系： fn fn1fn2=0 (1) 设q0， fn=qn满足斐波那契递推关系 q2q1=0 设fn=qn, 因为fn fn1fn2=qnqn1qn2= qn2(q2q1)=0, 注意 q0， 因此fnfn1fn2=

6、0当且仅当q2q1=0.,(2) q是方程x2x1=0的根。因此,那么，,和,都满足斐波那契,递推关系。对如何常数c1,c2，下面线性组合,可验证也满足递推关系。,(3) 根据初始值，确定常系数。 将f0=0, f1=1 代入上式得到线性方程组：,c1+c2=0,该方程组的系数矩阵可逆。,因此，方程组存在唯一解：,和,得到斐波那契数的公式：,关于n的函数满足某个递推关系，称这个函数是该 递推关系的一个解。,问题：上述求斐波那契递推关系的解时，猜测求解函数具有特定形式fn=qn，对于其他递推关系，怎么知道具有什么形式呢？,奇妙的斐波那契序列,斐波那契螺旋,应用,例：确定2n棋盘用多米诺牌完美覆盖的方法数hn。 规定h0=1. 容易看到h1=1， h2=2， h3=3。 hn= hn1 满足斐波那契递推关系。hn是斐波那契数。,+ hn2,应用,定理7.1.2 沿Pascal三角形左边向上对角线上的二项式系数和是Fibonacci数, 即,其中，k=(n+1)/2。,证明：定义 或者 需要证明gn满足Fibonacci递推关系并有相同初始值。,gn1+ gn2=,=,=,小结,一些与自然数n相关的计数问题，有时求递推关系更容易，可以通过给出递推关系来解决相关的