下载文档原格式
递推关系与母函数法1.2 递推关系Hanoi塔问题：这是组合数学中的著名问题。
n个圆盘依其半径大小，从下而上套在柱A上，如图1.1所示。
每次只允许取一个转移到柱B或柱C上，而且不允许大盘放在小盘上方。
若要求把柱A上的n个盘转移到柱C上，请设计一种方法，并估计要移动几个盘次，现在只有A，B，C三根柱子可供使用。
设a,b,c是3个塔座。
开始时，在塔座a上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一起。
各圆盘从小到大编号为1,2,…,n,现要求将塔座a 上的这一叠圆盘移到塔座b上，并仍按同样顺序叠置。
在移动圆盘时应遵守以下移动规则：规则1：每次只能移动1个圆盘；规则2：任何时刻都不允许将较大的圆盘压在较小的圆盘之上；规则3：在满足移动规则1和2的前提下，可将圆盘移至a,b,c中任一塔座上。
图1.1Hanoi塔是个典型的问题，第一步要设计算法，进而估计它的复杂性，即估计工作量。
这一问题有典型的意义，第一步先解决算法问题，即如何完成n个盘的搬动，进一步还要对算法作出复杂性分析，即对要作多少盘次的搬动进行估计。
算法设计：n=时，第一步先把最上面一个圆盘套在柱B上；第二步把第二个圆盘转2移到柱C上；最后再把柱B上的一个圆盘转移到柱C上，到此转移完毕。
假定1n-个盘子的转移算法已经确定。
对于一般n个圆盘的问题，先把上面的1n-个圆盘转称到柱B上，再把最后一上圆盘转移到柱C上，然后把柱B上的1n-个圆盘转移到柱C上，转移完毕。
上述的算法是递归的连用。
2n=时，第一步便利用n=时已给出了算法；3算法把上面两个圆盘移到柱B上，第二步再把第三个圆盘转移到柱C上；最后把柱B上的两个圆盘转移到柱C上，4,5,,n= 以此类推。
图1.1形象地给出4n=的转移过程。
void hanoi (int n, int a, int b, int c) {if (n > 0) {hanoi (n-1, a, c, b); move (a,b);hanoi (n-1, c, b, a); } }算法分析：令n h 表示n 个圆盘所需要的转移盘次。
ACM 暑期集训 组合数学（4） 递推 递归 母函数1 递推关系序列{a n }=a 0，a 1，…，a n ，…，把 a n 与某些a i (i <n )联系起来的等式叫做关于序列{a n }的递推方程。
当给定递推方程和适当的初值就唯一确定了序列。
递推关系分类： （1）按常量部分：齐次递推关系：指常量＝0，如F(n)=F(n-1)+F(n-2) 非齐次递推关系：指常量≠0，如F(n)=2*F(n-1)+1 （2）按运算关系：线性关系，如上面的两个；非线性关系，如F(n)=F(n-1)*F(n-2)。
（3）按系数：常系数递推关系，如（1）中的两个；变系数递推关系，如D(n)=(n-1)(D(n-1)+D(n-2)。
（4）按数列的多少一元递推关系，只涉及一个数列，上面的均为一元； 多元递推关系，涉及多个数列，如⎩⎨⎧+=+=----111177n n nn n n a b b b a a Fibonacci 数列为1,1,2,3,5,8,13,.....long long data[100]; data[1]=1; data[2]=1;for(int i=3;i<=50;i++) data[i]=data[i-1]+data[i-2]; while(cin>>n) cout<<data[n]<<endl;例1：直线割平面问题。
在一个无限的平面上有N 条直线，试问这些直线最多能将平面分割成多少区域？F(1) = 2; F(2) = 4; F(3) = 7; F(n)=F(n-1)+n; (n>1)int recurrence(int n) //递推 {f[1]=2;for(i=2;i<=n;i++) f[n]=f[n-1]+n; return f[n]; }int recursion(int n) 递归： {if(n==1) return 2;//递归终止条件 else return recursion(n-1)+n; }更快的方法是求出通项：F(n)=n^(n+1)/2+1例2：HDOJ2050 折线割平面问题在一个无限的平面上有N 条折线，试问这些折线最多能将平面分割成多少区域？F(n)=F(n-1)+4n-3; F(n)=2*n^2-n+1;例3：椭圆割平面问题。
习题11、 基本题：1～9，14，16，19，22～23，29，312、 加强题：11～12，17，18，21，283、 关联题：10，27，4、 提高题：13，15，20，24～26，30，321-1 在1到9999之间，有多少个每位上数字全不相同而且由奇数构成的整数？（解）问题相当于求在相异元素{}9,7,5,3,1中不重复地取1个、2个、…、4个元素的所有排列数，答案为45352515P P P P +++＝5+20+60+120＝2051-2 比5400小并具有下列性质的正整数有多少个？(1) 每位的数字全不同；(2) 每位数字不同且不出现数字2与7。
（解）（1）分类统计：①一位正整数有919=P 个；②两位正整数有1919P P ⨯＝81个；③三位正整数有2919P P ⨯＝9×9×8＝648个；④千位数小于5的四位数有3914P P ⨯＝4×9×8×7＝2016个；⑤千位数等于5，百位数小于4的数有28141P P ⨯⨯＝4×8×7＝224个。
由乘法法则，满足条件的数的总个数为9＋81＋648＋2016＋224＝2978（2）仿（1），总个数为17P ＋1717P P ⨯＋2717P P ⨯＋3713P P ⨯＋26131P P ⨯⨯＝7＋49＋294＋630＋150＝11301-3 一教室有两排，每排8个坐位，今有14名学生，问按下列不同的方式入座，各有多少种坐法？(1) 规定某5人总坐在前排，某4人总在后排，但每人具体坐位不指定；(2) 要求前排至少坐5人，后排至少坐4人。
（解）（1）5人在前排就座，其坐法数为 ()58,P ，4人在后排就座，其坐法数为 ()48,P ，还空7个坐位，让剩下的54514=--个人入坐，就座方式为 ()57,P 种，由乘法法则，就座方式总数为()58,P ()48,P ()57,P ＝28 449 792 000 （2）因前排至少需坐6人，最多坐8人，后排也如此。
数学公园游记第十八回递推数列与母函数递推数列变化多，探求通项细琢磨.转化归纳是根本，特征方程来撮合.上回书我们说到了兔子数列(斐波拉契数列)的通项与黄金数之间的亲密关系.但我们对其通项a n=，n=0，1，2，，到底是怎样得来的，还是不明就里，满头雾水.这回书我们就专门谈谈几类递推数列通项的求法及母函数与特征方程等问题.其中就有兔子数列通项公式的推算过程.§1 几类递推数列通项公式的求法由递推关系式，求数列通项公式的问题，一直都是数列问题中，既基本又重要的问题.它是贯穿于数列——这一神奇乐章的主旋律之一.下面就若干基本且重要的类型逐一进行解析，以供各位看官朋友参考、借鉴.1.a n+1=a n+f(n)型通项公式的求法——累加法.在高中教材中，推导等差数列的通项公式用的是不完全归纳法，其实我们也可以用累加法，请看：a2-a1=d,a3-a2=d,………a n-a n-1=d.(竖式)将上述n-1个等式相加即可得a n=a1+(n-1)d.用这种方式来求形如a n+1=a n+f(n)型递推数列的通项公式，也十分方便、有效.一般地，a n=(a n-a n-1)+(a n-1-a n-2)+ …＋(a2-a1)+a1=f(n-1)+f(n-2)+…+f(1)+a1(横式).例1.已知{a n}满足a n+1=a n+2×3n-1(n∈N+)，a1=2，求a n.解：∵a n+1=a n+2×3n-1(n∈N+)，∴a2-a1=2×30，a3-a2=2×31,………a n-a n-1=2×3n-2.将上述n-1个等式相加即可得a n= a1+2(30+31+…+3n-2)=3n-1+1.用累加法求出形如a n+1=a n+f(n)型递推数列的通项的前提是，其中f(n)的求和我们可以顺利地进行.2.a n+1=a n f(n)型通项公式的求法——累积法.在高中教材中，推导等比数列的通项公式用的也是不完全归纳法，其实我们也同样可以用累积法，请看：，，………(竖式)将上述n -1个等式相乘即可得a n =a 1q n -1.用这种方式求形如a n+1=a n f(n)型递推数列的通项公式，也很方便. 一般地，112211.....a a a a a a a a n n n n n ---==f(n -1)f(n -2)…f(2)f(1)a 1.例2.已知数列{a n }满足：a 1=2，且a n =3n a n -1(n ∈N +,n ≥2). 求a n . 解： ∵ 3n (n ∈N +, n ≥2)， ∴32， 33，…………3n .将上述n -1个等式相乘即可得a n =a 1。
2.1题（陈兴）求序列{ 0，1，8，27，3n }的母函数。
解：由序列可得到32333()23n G x x x x n x =+++++因为23111n x x x x x =++++++- 2311()'12341n x x x nx x-=++++++-设 2311()()'23(1)1n np x x x x x n x nx x-==++++-+-2222221[()]'123(1)n n p x x x x n x n x --=+++++-+设 2223212()[()]'23(1)n nq x x p x x x x n x n x -==++++-+3323231[()]'123(1)n n q x x x n x n x --=++++-+ 3233313[()]'23(1)n n x q x x x x n x n x -=+++-+ 由以上推理可知[()]'x q x =,[7*94*(6)],n n +-所以可通过求得[()]'x q x 得到序列的母函数：32()4G x x x x =++2321()()[34(3)]6n H x F x dx x x n x +==++++⎰2.2题（陈兴）已知序列343,,,,333n ⎧+⎛⎫⎛⎫⎛⎫⎫⎨⎬ ⎪ ⎪ ⎪⎝⎭⎝⎭⎝⎭⎭⎩，求母函数 解： 3*2*14*3*2(3)*(2)*(1)()3*2*13*2*13*2*1nn n n G x x +++=+++=1[3.2.1 4.3.2(3)(2)(1)]6n x n n n x ++++++211()()[3.2 4.3(3)(2)]6n F x G x dx x x n n x +==+++++⎰ 2321()()[34(3)]6n H x F x dx x x n x +==++++⎰3431()()[]6n I x H x dx x X x ++==++⎰因为23111n x x x x+=+++++-所以211()(1)61I x x x x=----所以31()[]'''61x G x x=-就是所求序列的母函数。
运用母函数求解递推数列通项公式作者：陈朝斌石建梅来源：《数学教学通讯(教师阅读)》2009年第03期四川内江师范学院数学与信息科学学院641112摘要：在教学中，教师应充分认识递推数列在初等数学与高等数学中的本质联系，从高等数学的高度进行教学，这有利于培养学生创造性的思维和探究问题的能力．本文利用母函数求解相关的一阶递推数列、二阶递推数列的通项问题.关键词：母函数；递推数列；应用在日常教学中，教师一般从初等数学的角度进行教学，采用“化归”的思想，引入辅助数列把问题转化为等差数列或等比数列来解决，但求解过程较烦琐，技巧性也不强．有些教师认识到递推数列问题在高等数学中的背景，从高等数学的高度进行教学，如采用“特征根法”“不动点法”等．本文主要利用母函数知识来研究递推数列问题．定义对数列｛an｝中的各项a0，a1，a2，…，构造函数G（x）=a0+a1x+a2x2+…，称G （x）为数列｛an｝的母函数．规定G（x）可以像多项式那样进行四则运算，不用考虑敛、散性．用母函数求解递推数列通项问题时一般有4步.（1）构造数列｛an｝的母函数G（x）=anxn=a0+a1x+a2x2+a3x3+…；（2）将关于an的递推关系式转化为关于数列｛an｝的母函数G（x）的方程式；（3）解出G（x）=++…，并根据=xn=1+x+x2+x3+…及=（px）n=1+px+（px）2+（px）3+…，=Cxn，将母函数的函数表达式展开成G（x）=a0+a1x+a2x2+a3x3+…的形式；（4）根据母函数G（x）=a0+a1x+a2x2+…中xn的系数an，求出数列｛an｝的通项.[⇩]一阶线性递推数列an+1=p（n）an+q（n），a1=a（a为常数，p（n）≠0），其中p（n），q（n）是关于n的函数.例1 （2008四川）设数列｛an｝的前n项和为Sn，已知ban－2n=（b-1）Sn .（1）证明：当b=2时，数列｛an-n·2n-1｝是等比数列；（2）求数列｛an｝的通项公式．解析由题意知a1=2，且an+1=ban+2n．（1）略.（2）当b≠2时，an+1=ban+2n，且有a0=．设数列｛an｝的母函数为G（x）=a0+a1x+a2x2+a3x3+…，所以x∶a1=ba0+20，x2∶a2=ba1+21，x3∶a3=ba2+22，…以上等式相加得G（x）=［（b-2）x·（1-2x）（1-bx）］.令G（x）=+，则an=·（A·2n+B·bn）.所以A+B=1，（2A+bB）=2 .解得A=，B=．因此an=［2n+（2-2b）bn-1］．综上所述，当b=2时，an=（n+1）2n-1；当b≠2时，an=2，n=1，［2n+（2-2b）bn-1］，n≥2 .评注经研究，如果数列｛an｝满足an+1=pan+qn（p≠0，1，q≠0，p≠q），且a1=a，则an=apn-1+－．[⇩]二阶线性递推数列an+2=pan+1+qan，a1=a，a2=b（a，b为常数，pq≠0）．例2（2008广东）设p，q为实数，α，β是方程x2－px+q=0的两个实根，数列｛xn｝满足x1=p，x2=p2－q，xn=pxn-1－qxn-2（n=3，4，…）．（1）证明：α+β=p，αβ=q；（2）求数列｛xn｝的通项公式；（3）若p=1，q=，求数列｛xn｝的前n项和Sn．解析 xn=pxn-1－qxn-2对n=2，3，4…也成立，则x0=1．（1）略.（2）设数列｛an｝的母函数为G（y）=a0+a1y+a2y2+a3y3+…，所以y2∶x2=px1－qx0，y3∶x3=px2－qx1，y4∶x4=px3－qx2，…以上等式相加得G（y）=，且α+β=p，αβ=q．当α≠β时，令G（y）=+，所以A+B=1，βA+αB=0，即A=，B=－.因此xn=.当α=β时，G（y）==C（ay）n，因此xn=Cαn=（n+1）αn.综上所述，xn=［αn+1－βn+1］，α≠β，xn=（n+1）αn，α=β.（3）略．评注经研究，如果数列｛an｝满足an+2=pan+1+qan，且a1=a，a2=b（pq≠0，a，b均为常数），其中α+β=p，αβ=－q．当α≠β时，an=；当α=β时，an=aαn-1+（n-1）（b-x）αn-2．在2008年的高考数学试卷中出现了一阶递推数列、一阶分式数列和二阶递推数列问题，而且数列的形式相当复杂，因此，在教学中加强递推数列在初、高等数学中的本质联系，从高等数学的角度进行教学，才能保证学生在高考中占有一定的优势．。
母函数与递推关系习题
1、 有n 阶台阶，一人从下往上走，每次走一或两级，求他走这n 级台阶的方法数。
2、 {1,2,3,}n S n = 的一个子集为交替的：如果按递增次序列出该子集的元素时，它们的
奇偶性为：奇、偶、奇、偶、 。
空集也算作交替的。
求n S 的交替自己的树木。
3、 某人有n 元钱，他一天买一样东西，或一元钱的甲、或二元钱的乙、或二元钱的丙，问他用完这n 元钱有多少种方法？
4、 求{,,}S a b c =∞⋅的n 排列数，要求在排列中a 与a 不相邻。
5、 设40n n i a i ==
∑，0n ≥，求n a 。
6、 求1003102-⎛⎫ ⎪⎝⎭。
7、 平面上有n 条直线，其中任意两条都相交于一点，但没有三条相交于同一点，求这n 条直线将平面分成的区域数。
8、 空间中有n 个平面，其中任意两个都有唯一交线，任意三个都有唯一一个交点，但没有四个相交于同一点。
求这n 个平面将空间分成的区域数。
9、 在平面上画一个圆，然后再依次画n 条与圆都相交的直线，其中当k 是大于1的奇数时，第k 条直线只与前面(1)k -条直线中的一条在圆内相交，当k 是偶数时，第k 条直线与前面(1)k -条直线都在圆内相交，又没有三条直线在圆内相交于同一点。
求这n 直线将圆分成的区域数。
10、
求{1,2,3}S =∞⋅的k 排列的个数，要求在排列中同一元素至多连续出现两次。
11、 将一个凸(1)n +边形用它的对角线划分成三角形，要求所用的对角现在多边形内部无交点，求划分的方法数。
12、 设一克、三克、七克重的砝码分别有1枚、3枚、2枚。
问用这些砝码能称出哪些重量？称每一重量又各有几种方案？
13、 有两种拆分：（1）1{1,12,3,14,}S =∞⋅⋅∞⋅⋅ ；（2）23{1,2,3,}S =⋅ 。
证明对
同一正整数n ，这两种拆分的拆分数相等。
14、 证明：周长为2n ，边长为整数的三角形的个数等于将n 拆分成恰好三项的拆分数。
15、
证明：将n 拆分成k 项，并且要求考虑各项次序的个数为11k n C --。
16、 设n a 为多重集{1,2,,}S m =∞⋅ 的n -组合数，要求在组合当中，每一元素出现
偶数次。
求n a 的母函数，进而求n a 。
17、
求多重集{53S =⋅⋅黑，红,⋅2白}的5-组合数和5-排列数。
18、 求下列两个方程的整数解的个数：
123123123123()5;05,03,02;
()8;16,03,2 4.a x x x x x x b x x x x x x ++=≤≤≤≤≤≤++=≤≤≤≤≤≤ 19、
求n 位四进制数的个数，要求在其中2和3都出现偶数次。
20、 把1到n 按顺序排成一圈，然后从中取出k 个数，要求两两之间另有至少两个数。
求方法数。
