递推关系和生成函数课件

第七章第七章 递推关系和生成函数递推关系和生成函数7.1 某些数列某些数列 许多组合学计数问题都涉及到一个参数，例许多组合学计数问题都涉及到一个参数，例如如hn表示表示1,2,.n的排列数，的排列数，hn=n!;那么那么hn 就就是是n的函数形式，的函数形式，n就是参数；在本章里，我们就是参数；在本章里，我们将讨论涉及一个整数参数的某些计数问题的代将讨论涉及一个整数参数的某些计数问题的代数求解方法。我们或者能得到一个显式公式，数求解方法。我们或者能得到一个显式公式，或者能得到一个函数，即或者能得到一个函数，即。1 在高等数学在高等数学“无穷级数无穷级数”章节中，我们知章节中，我们知 道函数道函数 f(x)有有n+1阶导数时阶导数时可以转化成幂级数，可以转化成幂级数，例如：例如：f(x)在在x0=0 处展开成处展开成麦克劳林级数：麦克劳林级数：2 或者或者在在x0 处展开成处展开成泰勒级数：泰勒级数：我们在二项式系数讨论中也有：我们在二项式系数讨论中也有：3 上述由函数展开成级数的问题，反过来就上述由函数展开成级数的问题，反过来就是由级数（数列）生成函数的问题。是由级数（数列）生成函数的问题。幂级数（有限或无限）幂级数（有限或无限）是我们经常要用到的级数，也把它称为数列是我们经常要用到的级数，也把它称为数列ak（k=1,2,）的）的生成函数生成函数或或母函数母函数。实际上决定幂级数性质的因素完全是实际上决定幂级数性质的因素完全是xn的的系数系数ak。4 7.1 某些数列某些数列 本次课首先讨论由数列生成递归关系本次课首先讨论由数列生成递归关系 令令 h0,h1,h2,hn,是一个数列。其是一个数列。其中中 hn称作该数列的称作该数列的通项通项或或生成项生成项。对于上述数列，定义其对于上述数列，定义其部分和部分和如下：如下：s0=h0 s1=h0+h1 5 则由部分和则由部分和 s0,s1,s2,sn,亦然构成数列。亦然构成数列。我们熟悉的数列有：我们熟悉的数列有：算术数列算术数列：其中每个后项比前项大一个常数：其中每个后项比前项大一个常数q。几何数列几何数列：其中每个后项是前项的：其中每个后项是前项的q倍。倍。一旦我们指定了初始项一旦我们指定了初始项h0和常数和常数q，上述两个数，上述两个数列的序列就唯一确定了：列的序列就唯一确定了：算术数列：算术数列：h0,h0+q,h0+hq,h0+nq.6 通项为：通项为：hn=h0+nq (n1)相邻两项有关系：相邻两项有关系：hn=hn-1+q (n1)前前n项和公式：项和公式：几何数列：几何数列：h0,qh0,q2h0,q3h0,qnh0.通项为：通项为：hn=qnh0 (n1)相邻两项有关系：相邻两项有关系：hn=qhn-1 (n1)前前n项和公式：项和公式：7 例：算术序列：例：算术序列：正偶数序列可以表示为：正偶数序列可以表示为：2,4,6,.2n.(n1)即：即：h0=2，q=2 正奇数序列可以表示为：正奇数序列可以表示为：1,3,.2n-1.(n1)即：即：h0=1，q=2 常数序列可以表示为：常数序列可以表示为：5,5,5,.5.即：即：h0=5，q=08例：几何序列：例：几何序列：幂指数序列可以表示为：幂指数序列可以表示为：1,2,4,.2n.(n0)即：即：h0=1，q=2 通项通项 hn=2n (n0)一般计数序列：一般计数序列：5,35,325,.3n5,.(n0)h0=5，q=3 通项通项 hn=3n 5 9例：确定平面一般位置上的例：确定平面一般位置上的n个互相交叠的圆所个互相交叠的圆所 形成的区域数？形成的区域数？分析：设分析：设hn是由是由n个互相个互相交叠的圆所形成的区域数。交叠的圆所形成的区域数。所谓相交是指两个圆的所谓相交是指两个圆的交点必须是交点必须是2个并且仅仅个并且仅仅2个，个，相切和相离都不成立。我们有相切和相离都不成立。我们有 h0=1；一个平面；一个平面10 区域；区域；h1=2，一个圆围成的圆内和圆外平面，一个圆围成的圆内和圆外平面 区域；区域；h2=4；如果是如果是 h3，在，在h2 的基础上的基础上增加一个圆，围成的区域将增加一个圆，围成的区域将增加增加4个，如图中红色的区域。个，如图中红色的区域。h3=h2+x=h3+2(3-1)；再加；再加一个兰色的圆将多一个兰色的圆将多6个区域个区域 h4=h3+y=h3+2(4-1)14233217654811 我们得到递推关系如下：设我们得到递推关系如下：设n2，对于，对于 n 1 个一般位置上互相交替的圆已经在平面是画个一般位置上互相交替的圆已经在平面是画出，它们形成出，它们形成hn1个区域。再加上第个区域。再加上第n个圆使得个圆使得在一般位置上放置在一般位置上放置n 个个互相交替的圆。互相交替的圆。前前n 1个圆的每一个与第个圆的每一个与第n 个都交于两点，个都交于两点，得到得到2(n1)个不同的点：个不同的点：p1,p2,p2(n-1)。他们。他们把第把第n个圆分成个圆分成2(n1)条弧：条弧：12 p1p2,p2p3,p3p4,.这这2(n1)条弧的每一条能将前条弧的每一条能将前(n1)个圆形个圆形成的区域一分为二，得到成的区域一分为二，得到2(n1)个区域，就是个区域，就是说，增加第说，增加第n个圆，就增加个圆，就增加2(n-1)个区域。个区域。分析分析hn与与hn-1 的关系，我们能发现区域数的关系，我们能发现区域数量量hn与画圆的数量与画圆的数量n的关系：的关系：13hn=hn-1+2(n-1)=hn-2+2(n-2)+2(n-1)=hn-3+2(n-3)+2(n-2)+2(n-1).=h1+2(1)+2(2)+.+2(n-2)+2(n-1)=2+21+22+.+2(n-1)14FibonacciFibonacci序列序列(斐波那契序列斐波那契序列)意大利数学家意大利数学家Fibonacci在在13世纪初世纪初提出过如下一个有趣问题：提出过如下一个有趣问题：年前养了一对小兔（雌雄各一），这对兔子中年前养了一对小兔（雌雄各一），这对兔子中的母兔从的母兔从2月份开始每月都产下一对雌雄各一的月份开始每月都产下一对雌雄各一的小兔。每对新生小兔间隔一月后也开始每个月都小兔。每对新生小兔间隔一月后也开始每个月都产下一对新的小兔（雌雄各一）。如是而下去，产下一对新的小兔（雌雄各一）。如是而下去，15 假定兔子都不死亡，兔子都不多生小兔，生的假定兔子都不死亡，兔子都不多生小兔，生的 小兔性别比例保持不变，不考虑近亲繁殖的小兔性别比例保持不变，不考虑近亲繁殖的问题，问一年后共有多少对兔子？问题，问一年后共有多少对兔子？假假定定年年初初为为1月月份份,年年后后为为13月月，若若设设 fn 为为第第n个个月月所所有有的的兔兔子子对对数数，不不难难推推算算各各月月兔兔子子对对数数与月份数的关系为与月份数的关系为:16 著著名名的的Fibonacci数数列列由由此此而而得得名名。这这一一数数列列的的增增长长速速度度是是很很快快的的。其其中中，第第二二年年年年底底兔兔子子有有50 000对对，第第三三年年年年底底兔兔子子有有15 000 000对对，第第 55 项就超过了项就超过了1万亿对。万亿对。第一列下来单独定义第一列下来单独定义。我们已经算出我们已经算出 f1=1,f2=1,f3=2,f4=3。月份月份012345678兔子对兔子对01123581321 fn f0 f1 f2 f3 f4 f5 f6 f7 f8 17则由各月兔子数不难证得如下递推式成立则由各月兔子数不难证得如下递推式成立:f n=f n-1+f n-2 (n 3)在在第第n月月时时，围围栏栏内内的的兔兔子子可可以以分分为为两两个个部部分分：一一是是第第n-1月月时时围围栏栏已已经经有有的的兔兔子子数数，二二是是第第n-1月月出出生生的的新新兔兔子子数数，由由于于兔兔子子的的成成熟熟期期是是一一个个月月，每每对对兔兔子子只只生生一一对对小小兔兔，第第n-1月月出出生生的的新兔子数就是第新兔子数就是第n-2月拥有的老兔子对数。月拥有的老兔子对数。18 由此我们可以求出下列兔子数：由此我们可以求出下列兔子数：f 5=f 4+f 3=3 +2=5 f 6=f 5+f 4=5 +3=8 f 7=f 6+f 5=8 +5=13 f 8=f 7+f 6=13 +8 =21 f 9=f 8+f 7=21+13=34 f 10=f 9+f 8=34+21=55 f 11=f 10+f 9=55+34=89 19 如果定义如果定义 f 0=0，f 2=f 1+f 0=1+0=1 满足满足 关系和初始条件：关系和初始条件：f n=f n-1+f n-2 (n 2)f 0=0；f 1=1 的的数数列列叫叫做做斐斐波波那那契契序序列列。序序列列的的项项叫叫做做斐斐波波那那契数契数。公式中的递推关系叫做。公式中的递推关系叫做斐波那契递归斐波那契递归。斐波那契序列有许多的性质，通过下面的斐波那契序列有许多的性质，通过下面的20 两个例题给出两个性质：两个例题给出两个性质：例：例：斐波那契序列的项的部分和为：斐波那契序列的项的部分和为：Sn=f0+f1+f2+.+.+fn=fn+2 1解：用归纳法证明：解：用归纳法证明：当当n=0时时 左左=f0=f2 1=1 1=0 成立成立 令令n0时时对对Sn成成立立，证证明明用用n+1取取代代n后后公公式式仍仍成成立。立。21Sn+1=f0+f1+f2+.+.+fn+1=fn+2 1+fn+1 =fn+2+fn+1 1=fn+3 1 公式成立公式成立例：斐波那契数是偶数当且仅当例：斐波那契数是偶数当且仅当n能够被能够被3整数整数.解：由前三个数解：由前三个数f 0，f 1，f 2的值。的值。f 0=0，f 1=1，f 2=1；由它们三项求的；由它们三项求的f 3：f 3=f 2+f 1=1+1=2 是偶数，其项数是偶数，其项数n=3能能被被3 3整除整除.22 它们的奇偶性有下列特征：它们的奇偶性有下列特征：f3 是：偶是：偶+奇奇+奇奇=偶偶；f4=f3+f2 是：偶是：偶+奇奇=奇奇；f5=f4+f3 是：是：奇奇+偶偶=奇奇；f6=f5+f4 是：是：奇奇+奇奇=偶；偶；f 6 的项数的项数n=6也能也能被被3 3整除。整除。23斐波那契递推公式斐波那契递推公式 由斐波那契递推公式由斐波那契递推公式 f n=f n-1+f n-2 得到：得到：f n f n-1 f n-2 =0 假设假设斐波那契数具有幂函数形式：斐波那契数具有幂函数形式：f n=qn其中其中q是一个非零数。代入上式是一个非零数。代入上式:qn qn-1qn-2=0解这个方程解这个方程 qn-2(q2 q 1)=0 只能是只能是 q2 q 1 =024因此因此由由于于两两个个解解都都是是斐斐波波那那契契关关系系的的特特解解，由由斐斐波波那契递推关系是线性的和齐次的，一般的通解：那契递推关系是线性的和齐次的，一般的通解：将将n=0，1时时f n 的初值代入确定系数的初值代入确定系数C1,C225 n=0，时，时:n=1，时，时:将上述值代入公式得到下列公式：将上述值代入公式得到下列公式：26 定理定理7.1.1 Fibonacci(斐波那契斐波那契)数满足公式数满足公式 虽然虽然斐波那契数斐波那契数(兔子数兔子数)都是整数，可是在都是整数，可是在公式中却包含了无理数，而求公式中却包含了无理数，而求f n 时这些无理数时这些无理数又神奇地消失了，这个表达式也就是斐波那契又神奇地消失了，这个表达式也就是斐波那契序列的通项公式。序列的通项公式。27例：令例：令f0,f1,f2,fn,满足下面给出的满足下面给出的斐波那斐波那 契递推关系和契递推关系和改变改变的初始条件的初始条件：fn=fn-1+fn-2 (n 2)f0=2 ;f1=1 的数列，试给出的数列，试给出fn的计算公式。的计算公式。解：将解：将 f0=2 ;f1=1代入代入斐波那契公式得：斐波那契公式得：f0=2 =C1+C228 解上述方程得：解上述方程得：如果将如果将斐波那契递序列的前几项改变成斐波那契递序列的前几项改变成 f0=1，f1=1，f2=2，.；即去掉；即去掉0这第一项，这第一项，29 对无穷级数来说，减少或增加有限项不会对无穷级数来说，减少或增加有限项不会改变级数的敛散性，我们以改变级数的敛散性，我们以1作为作为斐波那契递斐波那契递序列的第一、二项，递推关系不变，并且序列的第一、二项，递推关系不变，并且设设斐斐波那契数列生成的波那契数列生成的函数为函数为f(x)：3031 此此斐波那契数列斐波那契数列的又一个的又一个生成函数生成函数。设设1-x-x2 =0 的二根为的二根为、，分解多项式，分解多项式:注意区别于前面方程注意区别于前面方程：q2 q 1=0根的关系。根的关系。3233由幂级数展开公式：当由幂级数展开公式：当 x 1时时我们可以将公式中的两个分式展开成级数形式：我们可以将公式中的两个分式展开成级数形式：3435由于由于那么那么 与原来的公式比较要少一项，这正是我们与原来的公式比较要少一项，这正是我们省掉了省掉了0这第一项后得到地斐波那契数列的近这第一项后得到地斐波那契数列的近似计算公式。似计算公式。36比较这相邻两个比较这相邻两个斐波那契数的关系有：斐波那契数的关系有：这个数字正好是建筑、美学等领域的这个数字正好是建筑、美学等领域的黄黄金分割位金分割位。f nf n-1=0.618f n37关于关于斐波那契数，我们用竖式加法证明一些关系斐波那契数，我们用竖式加法证明一些关系 1)f 1+f 2+.+f n=f n+21;证明：由证明：由 f n+2=f n+f n+1 得：得：f 1=f 3 f 2 ;f 2=f 4 f 3 ;.+)f n=f n+2 f n-1 ;f 1+f 2+.+f n=f n+2 f 2=f n+21 证毕证毕38 2)f 1+f 3+.+f 2n-1=f 2n ;证明：由证明：由 f n+2=f n+f n+1 得：得：f 1=f 2 =1;f 3=f 4 f 2 ;f 5=f 6 f 4 ;.+)f 2n-1=f 2n f 2n-2 ;f 1+f 3+.+f 2n-1=f 2n 证毕证毕393)f12+f22+f32.+fn2=f n f n+1 ;证明：由证明：由 f n+2=f n+f n+1 得：得：f12 =f 1 f 1=f 2 f 1 f22 =f 2 f 2=f 2(f 3 f 1)=f 2f 3 f 2 f 1 f32 =f 3 f 3=f 3(f 4 f 2)=f 3f 4 f 3 f 2 .+)fn2=f n f n=f n(fn+1 fn-1)=fnfn+1 f n f n-1 f12+f22+f32.+fn2 =f n f n+1 ;证毕证毕40 例：确定例：确定2n棋盘用多米诺骨牌完美覆盖的棋盘用多米诺骨牌完美覆盖的 方法数方法数hn 解：解：h1=1；h2=2 h3=3；将将hn分为两分为两 种情况：种情况：A B A是左边第一个是左边第一个骨牌必须竖直摆放，其余骨牌必须竖直摆放，其余n-1个个骨牌不限制位置的覆盖的集合。骨牌不限制位置的覆盖的集合。B是左边第一是左边第一2 n2 n2(n-1)2(n-2)41骨牌不竖直摆放，即水平摆放骨牌不竖直摆放，即水平摆放(同时还有一个同时还有一个)其余其余n-2个骨牌不限制位置的覆盖的集合。个骨牌不限制位置的覆盖的集合。所以所以A中的完美覆盖数就等于中的完美覆盖数就等于2(n-1)棋棋盘的完美覆盖数：盘的完美覆盖数：|A|=hn-1 B中的完美覆盖数就等于中的完美覆盖数就等于2(n-2)棋盘的棋盘的完美覆盖数完美覆盖数,由于由于骨牌是相同的，骨牌是相同的，B中前两个中前两个水平放置的水平放置的骨牌没有上下区分；骨牌没有上下区分；|B|=hn-242 由加法原理由加法原理 故故 hn=|A|+|B|=hn-1+hn-2 (n 2)定义定义n=1时，即空覆盖：时，即空覆盖：h0=1，也是个，也是个斐波那斐波那契序列。契序列。下面说明下面说明斐波那契数作为二项式系数的和斐波那契数作为二项式系数的和出现的。出现的。43 定理定理7.1.2沿沿Pascal三角形图左边向上对角线上三角形图左边向上对角线上的二项式系数的和是的二项式系数的和是斐波那契数，更精确地说，斐波那契数，更精确地说，第第n个个斐波那契数是：斐波那契数是：44 Pascal三角形图三角形图f1=1f2=1f3=2f4=3f5=5f6=8f7=1345证明：由组合数的定义可知：当证明：由组合数的定义可知：当 kn 时时 所以我们可以把原式改写成：所以我们可以把原式改写成：下面只需要证明下面只需要证明fn满足满足斐波那契递推关系：斐波那契递推关系：46应用应用Pascal公式，对于公式，对于n2,47我们得到结论我们得到结论:f0,f1,f2,.fn,.是是斐波那契数列斐波那契数列48总总 结结 本次课我们介绍了一个重要的序列：本次课我们介绍了一个重要的序列：斐波斐波那契序列，并且引入了序列、生成函数、序列那契序列，并且引入了序列、生成函数、序列通项等概念，后面我们还将对上述问题作进一通项等概念，后面我们还将对上述问题作进一步的研究。步的研究。49本次授课到此结束本次授课到此结束作业如下作业如下:P162 1(ii),(iii),6，81.设设f0,f1,f2,.fn,.是斐波那契序列。通过是斐波那契序列。通过用小的用小的n值为下列每一个表达式赋值，推值为下列每一个表达式赋值，推测一般公式，并证明测一般公式，并证明(ii)f0+f2+f4+.+f2n50(iii)f0 f1+f2 .+(-1)nfn6.考虑考虑1行行n列的棋盘。假设用红蓝两种颜列的棋盘。假设用红蓝两种颜色之一为棋盘的每个方阁子着色。令色之一为棋盘的每个方阁子着色。令hn 是使得没有两个被涂成红色的方阁相邻是使得没有两个被涂成红色的方阁相邻的着色方法数。求出并验证的着色方法数。求出并验证hn所满足的所满足的递推关系。然后得出递推关系。然后得出hn的公式。的公式。51写在最后写在最后成功的基成功的基础在于好的学在于好的学习习惯The foundation of success lies in good habits52 结束语当你尽了自己的最大努力时，失败也是伟大的，所以不要放弃，坚持就是正确的。When You Do Your Best,Failure Is Great,So DonT Give Up,Stick To The End演讲人：XXXXXX 时 间：XX年XX月XX日