《组合数学(第7章7.1)》由会员分享，可在线阅读，更多相关《组合数学(第7章7.1)（21页珍藏版）》请在金锄头文库上搜索。
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= h0+nq 前n+1项和：sn= (n+1)h0+q(n)(n+1)/2 （2）几何数列（等比数列） h0, qh0, q2h0, , qnh0, 递推关系：hn= qhn-1 一般项： h
2、n= qnh0前n+1项和：sn= h0(1-qn+1)/(1-q) 一些例子例. 确定平面一般位置上的n个互相交叠的 圆所形成的区域数。（互相交叠是指每两 个圆相交在不同的两个点上；一般位置是 指没有同心圆）。 用hn表示n个交叠的圆形成的区域数h0=1， h1=2h2=4， h3=8一般递推关系(n2)： 第n个圆与前n-1个圆相交于 2(n-1)不同交点，P1, P2, P2(n1)。P1P4P2P5P3P6共形成2(n1)条弧P1P2, 弧P2P3 , P2(n1) 1 P2(n1)和 P2(n1) P1，每条弧把穿过的区域一分为二，因此增加 了2(n1)个区域。因此得到递推关系：hn
3、=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）序列 n年初把性别相反的一对新生兔子放进围栏 ，从第二个月开始每月生出一对性别相反 的兔子，每对新兔也从第二个月开始每月 生出一对性别相反的兔子，问一年后围栏 内共有多少对兔子。 表示幼兔表示成兔实线表示成长虚线表示生殖1: 12: 13: 24: 35: 56: 87: 13
4、令fn表示第n个月开始时兔子的对数。 显然 f1=1, f2=1, f3=2, 而f4=3。 递推关系 在第n个月开始，笼内的兔子可分 为两个部分：第n1个月期间出生未成熟的 兔子和第n1个月已经成熟的兔子，第n1 个月期间出的兔子数等于第n2月开始的兔 子数，即：fn= fn 1+fn 2迭代计算得到： f13=233n定义1：设f0=0, f1=1, 那么满足递推关系fn= fn-1+fn-2的序列叫斐波那契（Fibonacci）序列 ，项称为斐波那契数。n 由归纳法原理可得：Fibonacci序列的部分 和为 sn=f0+f1+fn= fn+21 证明： f0+f1+fn+fn+1= (
5、fn+21)+fn+1 = (fn+2+fn+1)1= fn+31n斐波那契数是偶数当且仅当n被3整除。n定理7.1.1 斐波那契数满足公式n0观察递推关系： fn fn1fn2=0(1) 设q0， fn=qn满足斐波那契递推关系 q2q1=0设fn=qn, 因为fn fn1fn2=qnqn1qn2= qn2(q2q1)=0, 注意 q0， 因此fnfn1fn2=0当且仅当q2q1=0.(2) q是方程x2x1=0的根。因此那么，和都满足斐波那契递推关系。对如何常数c1,c2，下面线性组合可验证也满足递推关系。(3) 根据初始值，确定常系数。将f0=0, f1=1 代入上式得到线性方程组：c1
6、+c2=0该方程组的系数矩阵可逆。因此，方程组存在唯一解：和得到斐波那契数的公式： 关于n的函数满足某个递推关系，称这个函数是该递推关系的一个解。问题：上述求斐波那契递推关系的解时，猜测求解 函数具有特定形式fn=qn，对于其他递推关系， 怎么知道具有什么形式呢？奇妙的斐波那契序列n斐波那契螺旋应用例：确定2n棋盘用多米诺牌完美覆盖的方法 数hn。规定h0=1. 容易看到h1=1， h2=2， h3=3。hn= hn1 满足斐波那契递推关系。hn是斐波那契数。+ hn2应用n定理7.1.2 沿Pascal三角形左边向上对角线 上的二项式系数和是Fibonacci数, 即其中，k=(n+1)/2。证明：定义或者需要证明gn满足Fibonacci递推关系并有相同初始值。gn1+ gn2=小结n一些与自然数n相关的计数问题，有时求递 推关系更容易，可以通过给出递推关系来 解决相关的计数问题。n本章的重点是递推关系的求解。作业n习题7.8 (P.162) 1. 设 f0, f1, fn,表示斐波那契序列。i), iii) 3. 证明下列关于斐波那契数的结论。i), ii) , v)
