2_1母函数与指数型母函数

《2_1母函数与指数型母函数》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第二章母函数与递推关系2.1母函数与指数型母函数2.2递推关系与Fibonacci数列2.3线性常系数递推关系2.4非线性递推关系举例2.5应用举例2.1母函数与指数型母函数母函数母函数的性质整数的拆分Ferrers图像指数型母函数1.母函数母函数方法是一套非常有用的方法，应用极广。这套方法的系统叙述，最早见于Laplace在1812年的名著—概率解析理论。我们来看如下的例子：两个骰子掷出6点，有多少种选法？注意到，出现1，5有两种选法，出现2，4也有两种选法，而出现3，3只有一种选法，按加法法则，共

2、有2+2+1=5种不同选法。或者，第一个骰子除了6以外都可选，有5种选法，一旦第一个选定，第二个骰子就只有一种可能的选法，按乘法法则有5×1=5种。但碰到用三个或四个骰子掷出n点，上述两方法就不胜其烦了。设想把骰子出现的点数1,2,…,6和t,t2,…,t6对应起来，则每个骰子可能出现的点数与(t+t2+…+t6)中t的各次幂一一对应。若有两个骰子，则其中t6的系数为5，显然来自于这表明，掷出6点的方法一一对应于得到t6的方法。故使两个骰子掷出n点的方法数等价于求中tn的系数。这个函数f(t)称为母函

3、数。母函数方法的基本思想：把离散数列和幂级数一一对应起来，把离散数列间的相互结合关系对应成为幂级数间的运算关系，最后由幂级数形式来确定离散数列的构造。再来看下面的例子：若令a1=a2=…=an=1，则有这就是二项式展开定理。比较等号两端项对应系数，可以得到恒等式：比较等式两端的常数项，可以得到恒等式：中令x=1可得又如在等式两端对x求导可得：再令x=1可得类似还可以得到还可以类似地推出一些等式，但通过上面一些例子已可见函数(1+x)n在研究序列C(n,0),C(n,1),…,C(n,n)的关系时所起的

4、作用。定义：对于序列a0,a1,a2,…，函数称为序列a0,a1,a2,…的母函数。例如函数(1+x)n就是序列C(n,0),C(n,1),…,C(n,n)的母函数。如若已知序列，则对应的母函数可根据定义给出。反之，如果已经求出序列的母函数G(x)，则该序列也随之确定。DDD输入u输出v例1下图是一逻辑回路，符号D是一延迟装置，即在时间t输入一个信号给延迟装置D，在t+1时刻D将输出同样的信号，符号表示加法装置。若在t=0,1,2,…时刻的输入为u0,u1,u2,…求在这些时刻的输出v0,v1,v2

5、,…显然，一般的有若信号输入的序列u0,u1,…的母函数为U(x)，输出的信号序列v0,v1,…的母函数为V(x)，则其中被装置的特性所确定，称为该装置的传递函数。设r，w，y分别代表红球，白球，黄球。例2有红球两个，白球、黄球各一个，试求有多少种不同的组合方案。(1)取一个球的组合数为3，即分别取红，白，黄。(2)取两个球的组合数为4，即两个红的，一红一黄，一红一白，一白一黄。(3)取三个球的组合数为3，即两红一黄，两红一白，一红一黄一白。(4)取四个球的组合数为1，即两红一黄一白。共有1+3+4+

6、3+1=12种组合方式。令取r的组合数为,则序列的母函数为令an为从8位男同志中抽取出n个的允许组合数。由于要男同志的数目必须是偶数。故例3某单位有8个男同志，5个女同志，现要组织一个由数目为偶数的男同志和数目不少于2的女同志组成的小组，试求有多少种组成方式？因此序列a1,a2,…,a8对应的母函数为：类似可得女同志的允许组合数对应的母函数为其中xk的系数就是组成符合要求的k人小组的数目。2.母函数的性质设序列ak,bk对应的母函数分别为A(x),B(x)。则下面的两个性质显然成立：(1)A(x)=B

7、(x)当且仅当ak=bk。(2)若A(x)+B(x)=c0+c1x+c2x2+…，则ck=ak+bk。性质1：若则B(x)=xlA(x)。证:则例4已知性质2：若bk=ak+l，则则例5已知性质3：若bk=a0+…+ak，则1:x:x2:xk:+)则例6已知性质4：若bk=ak+ak+1+…，则1:x:x2:+)性质5：若bk=kak，则性质6：若bk=ak/(1+k)，则则例7已知性质7：若ck=a0bk+a1bk-1+…+ak-1b1+akb0，则1:x:x2:+)令例8已知则3.整数的拆分所谓正

8、整数拆分即把正整数分解成若干正整数的和。相当于把n个无区别的球放到n个无标志的盒子，盒子允许空着，也允许放多于一个球。整数拆分成若干整数的和，办法不一，不同拆分法的总数叫做拆分数。拆分可以分为无序拆分和有序拆分；不允许重复的拆分和允许重复的拆分。例9若有1克、2克、3克、4克的砝码各一枚，问能称出那几种重量？有几种可能方案？从右端的母函数知可称出从1克到10克，系数便是方案数。例如右端有2x5项，即称出5克的方案有2种：5=2+3=1+4。类似的，称出6