母函数与指数型母函数PPT学习教案

《母函数与指数型母函数PPT学习教案》由会员分享，可在线阅读，更多相关《母函数与指数型母函数PPT学习教案（58页珍藏版）》请在装配图网上搜索。

1、会计学1母函数与指数型母函数母函数与指数型母函数2.1 母函数与指数型母函数1. 母函数2. 母函数的性质3. 整数的拆分4. Ferrers 图像5. 指数型母函数第1页/共58页1. 母函数母函数方法是一套非常有用的方法，应用极广。这套方法的系统叙述，最早见于Laplace在1812年的名著概率解析理论。我们来看如下的例子：两个骰子掷出6点，有多少种选法？注意到，出现1，5有两种选法，出现2，4也有两种选法，而出现3，3只有一种选法，按加法法则，共有2+2+1=5种不同选法。或者，第一个骰子除了6以外都可选，有5种选法，一旦第一个选定，第二个骰子就只有一种可能的选法，按乘法法则有51=5种

2、。第2页/共58页但碰到用三个或四个骰子掷出n点，上述两方法就不胜其烦了。设想把骰子出现的点数1,2,6和t,t2,t6对应起来，则每个骰子可能出现的点数与(t+t2+t6)中t的各次幂一一对应。若有两个骰子，则(.)(.).2626234562345ttttttttttt其中t6的系数为5，显然来自于, ,.156246336426516ttttttttttttttt 这表明，掷出6点的方法一一对应于得到t6的方法。第3页/共58页262( )(.)f tttt故使两个骰子掷出n点的方法数等价于求中tn的系数。这个函数f(t)称为母函数。母函数方法的基本思想：把离散数列和幂级数一一对应起来，

3、把离散数列间的相互结合关系对应成为幂级数间的运算关系，最后由幂级数形式来确定离散数列的构造。第4页/共58页再来看下面的例子：121221213112(1)(1)(1)1()(),nnnnnna xa xa xaaaxa aa aaaxa aa x 若令a1=a2= =an=1，则有()( , )( , )( , ).21112nnxC nxC nxC n n x这就是二项式展开定理。第5页/共58页 () ()()111mnm nxxx ( , )( , )( , ) (, )(, )(,)(, )(, )(,)010101nmmnC nC nxC n n xC mC mxC m m xC

4、mnC mnxC mn mn x 比较等号两端项对应系数，可以得到恒等式：(, )(, ) ( , ) (, ) ( ,) (, ) ( , ).0110C mn rC mC n rC mC n rC m r C n第6页/共58页() (/)()1111nmmm nxxxx ( , )( , )( , ) (, )(, )(,) (, )(, )(, ) (,)120101012nmmm nC nC nxC n n xC mC mxC m m xxC mnC mnxC mnxC mn mn x (,)( , ) (, )( , ) (, ) ( ,) (,). 0011C mn mC nC

5、mC nC mC n m C m m比较等式两端的常数项，可以得到恒等式：第7页/共58页(1)( ,0)( ,1)( , )nnxC nC nxC n n x中令x=1 可得又如在等式( ,0)( ,1)( ,2)( , )2 .nC nC nC nC n n两端对x求导可得：()( , )( , )( , ),111122nnnxC nC nxnC n n x再令x=1 可得1( ,1)2 ( ,2)3 ( ,3)( , )2.nC nC nC nnC n nn类似还可以得到222( ,1)2( ,2)( , )(1)2.nC nC nn C n nn n第8页/共58页还可以类似地推出一

6、些等式，但通过上面一些例子已可见函数(1+x)n在研究序列C(n,0),C(n,1),C(n,n)的关系时所起的作用。定义：对于序列a0,a1,a2,，函数2012( )G xaa xa x 称为序列a0,a1,a2,的母函数。例如函数(1+x)n就是序列C(n,0),C(n,1),C(n,n)的母函数。如若已知序列，则对应的母函数可根据定义给出。反之，如果已经求出序列的母函数G(x)，则该序列也随之确定。第9页/共58页DDD输入u输出v例1 下图是一逻辑回路，符号D是一延迟装置，即在时间t输入一个信号给延迟装置D，在t+1时刻D将输出同样的信号，符号表示加法装置。若在t=0,1,2,时刻的

7、输入为u0,u1,u2,求在这些时刻的输出v0,v1,v2,第10页/共58页显然，,12201100uuvuuvuv。,0233uuuv一般的有. 3 ,31nuuuvnnnn若信号输入的序列u0,u1,的母函数为U(x)，输出的信号序列v0,v1,的母函数为V(x)，则3( )(1) ( )( ) ( ),V xxx U xP x U x其中( )P xxx31被装置的特性所确定，称为该装置的传递函数。第11页/共58页设r，w，y 分别代表红球，白球，黄球。2(1)(1)(1)rrwy例2 有红球两个，白球、黄球各一个，试求有多少种不同的组合方案。22221()() ().rywrryr

8、wywr yr wrywr yw(1) 取一个球的组合数为3，即分别取红，白，黄。(2) 取两个球的组合数为4，即两个红的，一红一黄，一红一白，一白一黄。(3) 取三个球的组合数为3，即两红一黄，两红一白，一红一黄一白。(4) 取四个球的组合数为1，即两红一黄一白。第12页/共58页22( )(1)(1)G xxxx共有1+3+4+3+1=12种组合方式。43210,cccccrc令取r的组合数为 ,则序列的母函数为2341343.xxxx 第13页/共58页令an为从8位男同志中抽取出n个的允许组合数。由于要男同志的数目必须是偶数。故例3 某单位有8个男同志，5个女同志，现要组织一个由数目为

9、偶数的男同志和数目不少于2的女同志组成的小组，试求有多少种组成方式？2468( )1287028.A xxxxx因此序列a1,a2,a8对应的母函数为：1357020,1,(8,2)28,aaaaaaC468(8,4)70,(8,6)28,1.aCaCa第14页/共58页类似可得女同志的允许组合数对应的母函数为2345( )10105.B xxxxx( )( ) ( ) () ()C xA x B xxxxxxxxx 24682345128702810105 xxxxxxxxxxxx23456789101112131010285281840728630350150385其中xk的系数就是组成符

10、合要求的k人小组的数目。第15页/共58页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)。0,kk lklbakl ( ) ( ).11101000lllllllB xb xbxa xa xx A x 证:第16页/共58页则( )().!1211123mmmmxxxxB xxe 例4 已知 ,!231123xxxxA xe性质2：若bk=ak+l，则( ) ( )/.lk

11、lkkB xA xa xx 10则( ).!xxxxB xexx 2221234例5 已知 ,!231123xxxxA xe 第17页/共58页性质3：若bk=a0+ak，则( )( ).A xB xx 1ba 00baa101baaa2012kkbaaaa0121:x:x2:xk:_ ( )/()/()/()B xaxa xxa xx2012111/()( )/().aa xa xxA xx201211+)第18页/共58页则( )B xxxx231234例6 已知( ),nA xxxxx 2111( ),()A xxx2111( )C xxxx2313610( ).()B xxx3111第

12、19页/共58页性质4：若bk=ak+ak+1+，则( )( )( ).AxA xB xx 11baaa0012( )baaaAa112301( )baaaAaa22340111:x:x2:_ ( )( )()() ()B xAxxa xxxa xxx2202211 111()( )( )( ).aa xxAAxA xxxx 0111111+)( )A 1第20页/共58页性质5：若bk=kak，则( )( ).B xxA x 性质6：若bk=ak/(1+k)，则( )( ).xB xA x dxx 01则( )B xxxx2323例7 已知( ),nA xxxxx 2111 .()xxxx

13、21 11第21页/共58页性质7：若ck=a0bk+a1bk-1+ak-1b1+akb0，则( )C xcc xc x2012( ) ( ).A x B x ca b 000ca ba b10 110ca ba ba b2021 1201:x:x2:_ C xabb xb xa x bb xb xa xbb xb x2200121012222012 ( ) ( ).aa xa xbb xb xA x B x 22012012+)第22页/共58页令 ,xB xxxxx 232231例8 已知( ),nA xxxxx 2111(),kknk nnk kca bk 01122( )( ) ( )

14、.()xC xA x B xx 31则第23页/共58页3. 整数的拆分所谓正整数拆分即把正整数分解成若干正整数的和。相当于把n个无区别的球放到n个无标志的盒子，盒子允许空着，也允许放多于一个球。整数拆分成若干整数的和，办法不一，不同拆分法的总数叫做拆分数。拆分可以分为无序拆分和有序拆分；不允许重复的拆分和允许重复的拆分。第24页/共58页例9 若有1克、2克、3克、4克的砝码各一枚，问能称出那几种重量？有几种可能方案？()()()()xxxx2341111.xxxxxxxxxx2345678910122222从右端的母函数知可称出从1克到10克，系数便是方案数。例如右端有2x5项，即称出5克

15、的方案有2种：5=2+3=1+4。类似的，称出6克的方案也有2种：6=2+4=1+2+3。第25页/共58页例10 求用1分、2分、3分的邮票贴出不同数值的方案数。()()()xxxxxx22436111以x4为例，其系数为4，即4拆分成1，2，3之和的允许重复的拆分数为4：4 = 1+1+1+1 = 1+1+2 = 1+3 = 2+2。注意邮票允许重复，因此母函数为：第26页/共58页例11 若有1克砝码3枚、2克砝码4枚、4克砝码2枚，问能称出那几种质量？各有几种方案？G xxxxxxxxxx23246848( )(1)(1)(1)即可称出1至19克的质量，不同的方案数即为对应项前面的系数

16、。母函数为：xxxxxxxxxxxxxxxxxxx2345678910111213141516171819 1223344 555544 3322.第27页/共58页例12 把整数N无序拆分成整数a1,a2,an的和，且不允许重复，求不同的拆分数。的不同解的个数。这个问题对应于求不定方程 ., , , ,. ,nnia xa xa xNxin11220 11 2令bN表示不同的拆分数，则其对应的母函数为：( )()().().naaaG xxxx12111特殊的，当ai=i时，对应的母函数为：( )()().().nG xxxx2111第28页/共58页例13 把整数N无序拆分成整数a1,a2

17、,an的和，允许重复，求不同的拆分数。的不同解的个数。这个问题对应于求不定方程 ., , , ,. ,nnia xa xa xNxin11220 11 2令bN表示不同的拆分数，则其对应的母函数为：( )(.)(.) . (.)nnaaaaaaG xxxxxxx1122222111第29页/共58页.( -)() . ()naaaxxx 121111特殊的，当ai=i时，对应的母函数为：( ).()().()nG xxxx 21111( )(.)(.) . (.)nnaaaaaaG xxxxxxx1122222111第30页/共58页例14 把整数N无序拆分成奇整数的和，允许重复，求不同的拆分

18、数。这相当于在上例中把ai取成奇数，因此拆分数对应的母函数为：( ) .()()()nGxxxx 03211111例15 把整数N无序拆分成2的幂次的和，求不同的拆分数。这相当于把N拆分成1,2,4,8,的和，但不允许重复。因此拆分数对应的母函数为：( )()()()()ntG xxxxx2421111第31页/共58页例16 把整数N无序拆分1,2,m的和，允许重复，求不同的拆分数。若要求m至少出现一次呢？若无要求，由例13可知其母函数为：( ).()()()mmGxxxx 21111若要求m至少出现一次，则拆分数对应的母函数为： mmmGxxxxxxx2242( )(1)(1)()mmxx

19、xx2.(1)(1)(1)第32页/共58页这个等式的组合意义很明显：整数n拆分成1到m的和的拆分数减去拆分成1到m-1的和的拆分数，即为至少出现一个m的拆分数。显然有 mmmGxxxxxxx2211( )(1)(1)(1)1(1)(1)(1) mmGxGx 1( )( ).第33页/共58页( )()()()nG xxxx2111设bN表示N剖分成不同正整数和的剖分数，则其对应的母函数为：定理1 整数剖分成不同整数的和的剖分数(不允许重复)等于剖分成奇数的剖分数(允许重复)。xxxxxxxx246823411111111 .()()nxxx 3211111第34页/共58页( )()()()

20、G xxxxxxx22436111设bN表示N剖分成重复数不超过2的正整数之和的剖分数，则其对应的母函数为：定理2 N剖分成其他数之和但重复数不超过2，其剖分数等于它剖分成不被3整除的数的和的剖分数。xxxxxxxx3691223411111111.kkxxxxx24531111111111不不整整除除第35页/共58页( )()()()()ntG xxxxx2421111定理3 N被剖分成一些重复次数不超过k次的整数的和，其剖分数等于被剖分成不被k+1除尽的数的和的剖分数。xxxxxx24824111111xxxx 23111定理4 对任意整数N，它被无序剖分成2的幂次的和的剖分方式一定唯一

21、。第36页/共58页例17 若有1、2、4、8、16克的砝码各一枚，问能称出那几种质量？有几种可能方案？( ) ()()()()()G xxxxxx2481611111这说明用这些砝码可以称出从1克到31克的质量，而且方案都是唯一的。xxxxxxxxxx 2481632248161111111111xxxxx 3223111.1实际上这说明整数的二进制表示是唯一的。第37页/共58页4. Ferrers图像一个从上而下的n层格子组成的图像，mi为第i层的格子数。当mimi+1，即上层的格子数不少于下层的格子数时，称之为Ferrers图像，如下图：每一层至少有一个格子。绕虚线轴旋转所得的图仍然是

22、Ferrers图像。这样的两个Ferrers图像称为一对共轭的Ferrers图像。第38页/共58页(1) 整数n拆分成k个数的和的拆分数，与数n拆分成最大数为k的拆分数相等。因为整数n拆分成k个数的和的拆分可以用一个k行的图像表示。所得的Ferrers图像的共轭图像最上面一行有k个格子。例如： 利用Ferrers图像可以得到一些关于整数拆分的结果： 24=6+6+5+4+3 5个数，最大数为6 24=5+5+5+4+3+2 6个数，最大数为5第39页/共58页理由和(1)相类似。因此，拆分成最多不超过m个数的和的拆分数的母函数是：(2) 整数n拆分成最多不超过m个数的和的拆分数，与n拆分成最

23、大不超过m的拆分数相等。.()()()mxxx21111正好拆分成m个数的和的拆分数的母函数为()()()()()()mmxxxxxx 22111111111.()()()mmxxxx 2111第40页/共58页(3) 整数n拆分成互不相同的若干奇数的和的的拆分数，与n拆分成自共轭的Ferrers图像的拆分数相等。设整数n拆分为n=(2n1+1)+(2n2+1)+(2nk+1)，其中n1n2nk。构造一个Ferrers图像，第一行第一列都是n1+1格，对应于2n1+1，第二行第二列都是n2+1格，对应于 2n2+1，依此类推。这样得到的Ferrers图像一定是自共轭的。反过来，自共轭的Ferr

24、ers图像也可以对应到一些不同奇数的和。第41页/共58页例如17=9+5+3对应的Ferrers图像为：(4) 正整数n剖分成不超过k个数的和的剖分数，等于将n+k剖分成恰好k个数的剖分数。不超过k层的Ferrers图像的每一层加上一个格子，一一对应到一个刚好k层的Ferrers图像。第42页/共58页5. 指数型母函数考虑n个元素组成的多重集，其中a1重复了n1次，a2 重复了n2次，ak重复了nk次，n=n1+n2+nk。从中取r个排列，求不同的排列数。若r=n，即考虑n个元素的全排列，则不同的排列数为：!21knnnn但是对于一般的r，情况就比较复杂了。第43页/共58页8765432

25、32543232232369109631 )1 ( )23321 ( )1)(1)(1 ()(xxxxxxxxxxxxxxxxxxxxxxxxxG先看一个具体的问题：假设有8个元素，其中a1重复3次，a2重复2次，a3重复3次。从中取r个组合，其组合数为cr，则其对应的母函数为：从x4的系数可知，从这8个元素中取4个组合，不同的组合数为10。这10个组合可从下面的展开式中得到：第44页/共58页()()()xxxxxxxx 2322311122333111其中4次方项表示了所有从8个元素中取4个的组合方案。例如 表示一个a1三个a3的组合， 表示两个a1两个a3的组合，依此类推。331xx23

26、21xx()( )( )( )xxxxx xxx xx xxxx xx xx xx x xx xx xx xxx xx xx xx x xx xx xx x xx x xx xx x221231122133322223311212131232223332223132331323132223223123231312312313221211第45页/共58页接下来讨论从这8个元素中取4个的不同排列总数。以两个a1两个a3组合为例，不同排列数为4!/(2!2!)。同样一个a1三个a3的不同排列数为4!/(1!3!)。依此类推可以得到不同的排列总数为：! ! ! ! ! ! ! ! ! ! ! ! !

27、 !1111111 31 32 21 1 22 23 1411112 1 11 2 13 12 2. 16183670第46页/共58页( )()()()!exxxxxxxxGx 2322311112312123为了便于计算，利用上述特点，形式地引进函数xxxxxxxx23456789143517358113231212727272! .!xxxxxxxx2345678392870112341703505605605678从右边很容易可以看出，取2个的排列数为9，取3个的排列数为28，取4个的排列数为70依此类推。第47页/共58页定义：对于序列a0,a1,a2,，函数( ) !kkeaaaa

28、Gxaxxxxk233120123称为序列a0,a1,a2,对应的指数型母函数。这样，对于一个多重集，其中a1重复n1次，a2 重复n2次，ak重复nk次，从中取r个排列的不同排列数所对应的指数型母函数为：( ) ! .!knennkxxxGxnxxxxxxnn1221222112111212第48页/共58页例18 求下列数列的指数型母函数：( )(, );( );( ).nnnnaP m naab 1213( )( )(, )(, )() .!nmnmennxGxP m nC m n xxn 0011( )( ).!nnbxenxGxben 03( )( ).!nxenxGxen 021第

29、49页/共58页例19 由1，2，3，4四个数字组成的五位数中，要求数1出现次数不超过2次，但不能不出现； 2出现次数不超过1次； 3出现次数最多3次，可以不出现；4出现次数为偶数。求满足上述条件的数的个数。( ) ()1! !exxxxxGxxxx22324112123124设满足上述条件的r位数个数为cr，则其对应的指数型母函数为：第50页/共58页 xxxxxxxxxx23456789105843433232448171114828848288! .!xxxxxxxxxx234567891051864215645123456178514076501260078910由此可见满足条件的5位

30、数共215个。第51页/共58页例20 求由1，3，5，7，9五个数字组成的n位数的个数，要求其中3，7出现的次数为偶数，其他1，5，9出现次数不加限制。( ) !exxxxGxx 232423112423设满足上述条件的n位数个数为cn，则其对应的指数型母函数为： xxxeee 232第52页/共58页( )()xxxeGxeee 223124()xxxeee53124().!nnnnxn 0152 314!nnnnnnnnxxxnnn00015324().nnna 152 314因此第53页/共58页例21 7个有区别的球放进4个有标志的盒子里，要求1，2两个盒子必须有偶数个球，第3个盒子

31、有奇数个球，求不同的方案个数。( )!exxxxxxGx 2243211241312这相当于从1234这4个数中取7个做允许重复的排列，即每个数字对应于每个球所放的盒子的序号。xxxxxeeeee 222这样的排列数所对应的指数型母函数为：第54页/共58页( )()xxxeGxeee 422118().!innnnxn 1114228(),nnnna 14228因此().a 7777142220808第55页/共58页例22 r个有标志的球放进n个不同的盒子里，要求无一空盒，问有多少种不同的分配方案？( )!nexxxGx23123这相当于从1到n这n个数字中取r个做允许重复的排列，即每个数字对应于每个球所放的盒子的序号。这样的排列数所对应的指数型母函数为：要求无一空盒即相当于要求每个数字至少出现一次。第56页/共58页 ( )nxeGxe 1()()xn kkknek 01 ()() .nkrrknankk 01因此()()!rrkkrnnkxkr 001()(),!rnkrrknxnkkr 001第57页/共58页