应用举例.ppt

例1 9个数字(1到9)和4个四则运算符(+,-,)组成的13个元素，求由其中的n个元素的排列构成一算术表达式的个数。,这里所说的算术表达式指的是普通意义下的四则运算表达式，不允许运算符连续出现，最后一位必定是数字。,假设n个元素的算术表达式个数为an。由于最后一位必定是数字，接下来看第n-1位，即倒数第二位。,2.5 应用举例,若第n-1位是数字，则前n-1位构成算术表达式，个数为an-1，加上最后一位有9种取法，因此这样的n位算术表达式个数为9an-1。,若第n-1位是运算符，则第n-2位必定是数字(不允许两个运算符连续出现)，即前n-2位构成算术表达式，个数为an-2，加上最后一位有9种取法，倒数第二位有4种取法，这样的n位算术表达式个数为36an-2。,因此可以得到递推关系式：,初始条件为a1=9，a2=90。,这里a2=90指的是81个两位数和-1到-9。,为了后面的计算方便，我们把a1，a2代入原递推关系反解出a0=1/4。,从特征方程x2-9x-36=0解出特征根为12，-3。,因此可以设,代入初始条件有,因此有：,由此解出,例2 n条直线把平面分成多少个区域？假定直线两两相交且无三线共点。,设n条直线把平面分成Dn个区域。,这是一个非齐次递推关系。由于1是1重特征根，因此特解应设为2次多项式，加上齐次方程的通解为常数，因此可以设,代入初始条件：D1=2，D2=4，D3=7，解得A=B=1/2,C=1。因此有,第n条直线被其它n-1条直线分成n段，这n段刚好对应增加了n个新的区域。因此有,例3 设有n条封闭的曲线，两两相交于两点，任意三条封闭曲线不相交于一点。求这样的 n条曲线把平面分割成几个部分？,设n条曲线把平面分割成an个部分。,这2n-2个交点把第n条曲线分成2n-2段。,这是一个线性常系数非齐次递推关系。,第n条曲线与其他n-1条曲线共有2(n-1)个交点。,这2n-2段刚好是增加的区域的边界，即增加了2n-2个区域。因此有,右端项为一次多项式，但因为1是1重特征根，因此特解应该设为二次多项式。加上齐次递推关系的通解为常数，因此有,对于初始条件，显然有a1=2，a2=4。,在递推关系an-an-1=2n-2中令n=1还可以得到a0=2。,把这三个初始条件代入有,因此有：,例4 空间有n个平面，任意三个平面交于一点，且无四平面共点。这样的n个平面把空间分成多少个不重叠的区域？,设这样的n个平面把空间分成an个区域。,因此关键在于第n个平面被其它n-1个平面分成多少个区域？,题目的条件保证了第n个平面与其它n-1个平面各有一条交线，而且这些直线两两相交，且无三线共点。,第n个平面被其它n-1个平面分成一些区域，这些区域刚好对应到新增加了的空间区域个数。,因此根据例2的结论，这n-1条直线把第n个平面分成的区域个数为：Dn-1=n(n-1)/2+1。,这表明,与前面的讨论类似，这个递推关系的解应该是三次多项式，即可设,初始条件有a1=2，a2=4，a3=8，a0=1。代入有,因此有,例5 平面上有一点P，它是n个区域D1,D2,Dn的共同交界点。现取k种颜色对这n个区域进行着色，要求相邻两个区域着的颜色不同。求着色的方案数。,设不同的着色方案数为an。,(1)D1和Dn-1着色相同；,满足条件的着色方案分为两类：,(2)D1和Dn-1着色不同；,(1)从D1到Dn-2的着色方案数为an-2(D1和Dn-2看作相邻，着色不同)。,然后Dn-1和D1同色，Dn有k-1种颜色可选。,这种情形的总方案数为(k-1)an-2。,特征方程为：x2-(k-2)x-(k-1)=0。,由初始条件a2=k(k-1)，a3=k(k-1)(k-2)，有,(2)从D1到Dn-1的着色方案数为an-1(D1和Dn-1看作相邻，着色不同)。,然后Dn有k-2种颜色可选。这种方案数为(k-2)an-1。,因此可以得到递推关系式：,特征根为：k-1，-1。因此有,有,由此解得：,把a0=k，a1=0代入,因此满足条件的不同着色方案数为：,例6 求n位二进制数中最后三位出现010图象的数的个数。,这里所说的010图象是指：对于n位2进制数从左向右进行扫描，一旦出现010图象，便从这图象后面一位继续开始扫描。,例如对11位2进制数00101001010从左向右的扫描结果应该是2-4，7-9位出现010图象，即,而不是4-6，9-11位出现的010图象，即不是,注意最后三位是010和最后三位出现010图象的区别。,最后三位是010的n位二进制数显然有2n-3个。,设最后三位出现010图象的数的个数为an。,这些数可以分为两类：最后三位出现010图象以及第n-4位至第n-2位出现010图象。,这是一个二阶线性常系数非齐次递推关系。初始条件为a3=1，a4=2。,最后三位出现010图象的数有an个，第n-4位至第n-2位出现010图象的数的个数为an-2。因此有,代入递推关系解得：a2=2-a4=0，a1=1-a3=0，a0=1/2-a2=1/2。,先求对应的齐次递推关系的通解。,特征方程为x2+1=0，特征根为i和-i。,由于右端项是2n-3，因此可以设一个特解为C2n。,所以递推关系的解可以表示为：,因此齐次递推关系的通解为：,代入初始条件有：,由此解得：,因此最后三位出现010图象的数的个数为：,例7 求n位二进制数中最后三位第一次出现010图象的数的个数。,设最后三位第一次出现010图象的数的个数为an。,同上例，最后三位是010的数有2n-3个。,这些数包括：,(1)最后三位第一次出现010图象的，个数为an：,(2)第n-4至n-2位第一次出现010图象的，个数为an-2：,(3)第n-5至n-3位第一次出现010图象的，个数为an-3：,(4)第n-6至n-4位第一次出现010图象的：,注意到第n-3位可以取1或0，因此这种数有2an-4个。,一般的，对于k3，第n-k-2至第n-k位第一次出现010图象的数的个数为2k-3an-k，因为从第n-k+1至第n-3的这k-3位每位都可取1或0。,因此有：,初始条件为a3=1，a4=2，a5=3。,注意a5=3是因为最后3位是010的5位数有4个：,00010，01010，10010，11010.,但其中01010不满足条件。,这不是一个常系数递推关系，左边的递推关系中的项数和系数都是在不断变化的。,例如，令n=6，则a6+a4+a3=8，由此得到a6=5。,例如，令n=7，则a7+a5+a4+2a3=16，由此得到a7=9。,得到一般通项表达式的方法比较特别。,设序列an对应的母函数为：,则有：,x3:,x4:,x5:,+),整理得：,因此有：,例8 计算如下电路中各点的电压vj(j=1,2,n)：,取如右图所示部分电路：,根据欧姆定律有,此外还有：ij+1=ij+vj+1/2。,消去ij即得到关于vj的递推关系式：,或,特别的，由(v1-v0)/4=v0/2，可得v1=3v0。,这是一个线性常系数齐次递推关系。,特征方程为：x2-4x+1=0，特征根为：因此设,代入初始条件：,解得：,则有,若电源电压v已知，则可以由,解出v0，从而得到所有的vj。,例9 计算如下电路的等效电阻(总电阻)：,Rn可以看成是Rn-1和其他三个电阻串并联所得，即：,因此有：,这是一个非线性递推关系。初始条件为R1=R。,令Rn=an/bn，a1=R，b1=1。,则有,因此可以令,消去an有,这是一个线性常系数齐次递推关系。,特征方程为x2-4Rx+R2=0，特征根为,因此可以设,代入初始条件有,因此有,然后有,因此有,