资源描述：
《递推关系和生成函数.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第七章递推关系和生成函数7.1某些数列许多组合学计数问题都涉及到一个参数，例如hn表示{1,2,….n}的排列数，hn=n!;那么hn就是n的函数形式，n就是参数；在本章里，我们将讨论涉及一个整数参数的某些计数问题的代数求解方法。我们或者能得到一个显式公式，或者能得到一个函数，即生成函数。1在《高等数学》“无穷级数”章节中，我们知道函数f(x)有n+1阶导数时可以转化成幂级数，例如：f(x)在x0=0处展开成麦克劳林级数：2或者在x0处展开成泰勒级数：我们在二项式系数讨论中也有：3上述由函数展开成级数的问题，反过来就是由级数（数列）生成函数的问题。
2、幂级数（有限或无限）是我们经常要用到的级数，也把它称为数列ak（k=1,2,…）的生成函数或母函数。实际上决定幂级数性质的因素完全是xn的系数ak。47.1某些数列本次课首先讨论由数列生成递归关系令h0,h1,h2,…,hn,…是一个数列。其中hn称作该数列的通项或生成项。对于上述数列，定义其部分和如下：s0=h0s1=h0+h1……5则由部分和s0,s1,s2,…,sn,…亦然构成数列。我们熟悉的数列有：算术数列：其中每个后项比前项大一个常数q。几何数列：其中每个后项是前项的q倍。一旦我们指定了初始项h0和常数q，上述两个数列的序列就唯一确定了：
3、算术数列：h0,h0+q,h0+hq,……h0+nq…..6通项为：hn=h0+nq(n≥1)相邻两项有关系：hn=hn-1+q(n≥1)前n项和公式：几何数列：h0,qh0,q2h0,q3h0,……qnh0…...通项为：hn=qnh0(n≥1)相邻两项有关系：hn=qhn-1(n≥1)前n项和公式：7例：算术序列：正偶数序列可以表示为：2,4,6,…..2n..(n≥1)即：h0=2，q=2正奇数序列可以表示为：1,3,…..2n-1..(n≥1)即：h0=1，q=2常数序列可以表示为：5,5,5,…..5..即：h0=5，q=08例：几何序列
4、：幂指数序列可以表示为：1,2,4,…..2n..(n≥0)即：h0=1，q=2通项hn=2n(n≥0)一般计数序列：5,3×5,32×5,………..3n×5,………..(n≥0)h0=5，q=3通项hn=3n×59例：确定平面一般位置上的n个互相交叠的圆所形成的区域数？分析：设hn是由n个互相交叠的圆所形成的区域数。所谓相交是指两个圆的交点必须是2个并且仅仅2个，相切和相离都不成立。我们有h0=1；一个平面10区域；h1=2，一个圆围成的圆内和圆外平面区域；h2=4；如果是h3，在h2的基础上增加一个圆，围成的区域将增加4个，如图中红色的区域。h
5、3=h2+x=h3+2(3-1)；再加一个兰色的圆将多6个区域h4=h3+y=h3+2(4-1)14233217654811我们得到递推关系如下：设n≥2，对于n–1个一般位置上互相交替的圆已经在平面是画出，它们形成hn–1个区域。再加上第n个圆使得在一般位置上放置n个互相交替的圆。前n–1个圆的每一个与第n个都交于两点，得到2(n–1)个不同的点：p1,p2,…,p2(n-1)。他们把第n个圆分成2(n–1)条弧：12p1p2,p2p3,p3p4,……..这2(n–1)条弧的每一条能将前(n–1)个圆形成的区域一分为二，得到2(n–1)个区域，就
6、是说，增加第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+[2×1+2×2+…..+2×(n-1)]14Fibonacci序列(斐波那契序列)意大利数学家Fibonacci在13世纪初提出过如下一个有趣问题：年前养了一对小兔（雌雄各一），这对兔子中的母兔从2月份开始每月都产下一对雌雄各一的小兔
7、。每对新生小兔间隔一月后也开始每个月都产下一对新的小兔（雌雄各一）。如是而下去，15假定兔子都不死亡，兔子都不多生小兔，生的小兔性别比例保持不变，不考虑近亲繁殖的问题，问一年后共有多少对兔子？假定年初为1月份,年后为13月，若设fn为第n个月所有的兔子对数，不难推算各月兔子对数与月份数的关系为:16著名的Fibonacci数列由此而得名。这一数列的增长速度是很快的。其中，第二年年底兔子有50000对，第三年年底兔子有15000000对，第55项就超过了1万亿对。第一列下来单独定义。我们已经算出f1=1,f2=1,f3=2,f4=3。月份012345
8、678兔子对01123581321fnf0f1f2f3f4f5f6f7f817则由各月兔子数不难证得如下递推式成立:fn=
