资源描述:
《母函数与指数型母函数PPT课件.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、2.1母函数与指数型母函数母函数母函数的性质整数的拆分Ferrers图像指数型母函数1.母函数母函数方法是一套非常有用的方法,应用极广。这套方法的系统叙述,最早见于Laplace在1812年的名著—概率解析理论。我们来看如下的例子:两个骰子掷出6点,有多少种选法?注意到,出现1,5有两种选法,出现2,4也有两种选法,而出现3,3只有一种选法,按加法法则,共有2+2+1=5种不同选法。或者,第一个骰子除了6以外都可选,有5种选法,一旦第一个选定,第二个骰子就只有一种可能的选法,按乘法法则有5×1=5种。但碰到用三
2、个或四个骰子掷出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)的关系时所起的作用。定义:对于序列a0,a1,a2,…,函数称为序列a0,a1,a2,…的母函数。例如函数(1+x)n就是序列C(n,0),C(n,1),…,C(n,n)的母函数。如若已知序列
4、,则对应的母函数可根据定义给出。反之,如果已经求出序列的母函数G(x),则该序列也随之确定。DDD输入u输出v例1下图是一逻辑回路,符号D是一延迟装置,即在时间t输入一个信号给延迟装置D,在t+1时刻D将输出同样的信号,符号表示加法装置。若在t=0,1,2,…时刻的输入为u0,u1,u2,…求在这些时刻的输出v0,v1,v2,…显然,一般的有若信号输入的序列u0,u1,…的母函数为U(x),输出的信号序列v0,v1,…的母函数为V(x),则其中被装置的特性所确定,称为该装置的传递函数。设r,w,y分别代表红球
5、,白球,黄球。例2有红球两个,白球、黄球各一个,试求有多少种不同的组合方案。(1)取一个球的组合数为3,即分别取红,白,黄。(2)取两个球的组合数为4,即两个红的,一红一黄,一红一白,一白一黄。(3)取三个球的组合数为3,即两红一黄,两红一白,一红一黄一白。(4)取四个球的组合数为1,即两红一黄一白。共有1+3+4+3+1=12种组合方式。令取r的组合数为,则序列的母函数为令an为从8位男同志中抽取出n个的允许组合数。由于要男同志的数目必须是偶数。故例3某单位有8个男同志,5个女同志,现要组织一个由数目为偶数的
6、男同志和数目不少于2的女同志组成的小组,试求有多少种组成方式?因此序列a1,a2,…,a8对应的母函数为:类似可得女同志的允许组合数对应的母函数为其中xk的系数就是组成符合要求的k人小组的数目。2.母函数的性质设序列ak,bk对应的母函数分别为A(x),B(x)。则下面的两个性质显然成立:(1)A(x)=B(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=a
7、0+…+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.整数的拆分所谓正整数拆分即把正整数分解成若干正整数的和。相当于把n个无区别的球放到n个无标志的盒子,盒子允许空着,也允许放多于一个球。整数拆分成若干整数的和,办法不一,不同拆分法的总数叫做拆分数。拆分可以分为无序拆分和有序拆分;不允许
8、重复的拆分和允许重复的拆分。例9若有1克、2克、3克、4克的砝码各一枚,问能称出那几种重量?有几种可能方案?从右端的母函数知可称出从1克到10克,系数便是方案数。例如右端有2x5项,即称出5克的方案有2种:5=2+3=1+4。类似的,称出6克的方案也有2种:6=2+4=1+2+3。例10求用1分、2分、3分的邮票贴出不同数值的方案数。以x4为例,其系数为4,即4拆分成1,2,3之和的允