2-1 母函数与指数型母函数

第二章母函数与递推关系2.1母函数与指数型母函数2.2递推关系与Fibonacci数列2.3线性常系数递推关系2.4非线性递推关系举例2.5应用举例2.1母函数与指数型母函数1.母函数2.母函数的性质3.整数的拆分4.Ferrers图像5.指数型母函数1.母函数母函数方法是一套非常有用的方法，应用极广。这套方法的系统叙述，最早见于Laplace在1812年的名著—概率解析理论。我们来看如下的例子：两个骰子掷出6点，有多少种选法？注意到，出现1，5有两种选法，出现2，4也有两种选法，而出现3，3只有一种选法，按加法法则，共有2+2+1=5种不同选法。或者，第一个骰子除了6以外都可选，有5种选法，一旦第一个选定，第二个骰子就只有一种可能的选法，按乘法法则有5×1=5种。但碰到用三个或四个骰子掷出n点，上述两方法就不胜其烦了。设想把骰子出现的点数1,2,…,6和t,t2,…,t6对应起来，则每个骰子可能出现的点数与(t+t2+…+t6)中t的各次幂一一对应。若有两个骰子，则(...)(...)....2626234562345ttttttttttt其中t6的系数为5，显然来自于,,,,.156246336426516ttttttttttttttt这表明，掷出6点的方法一一对应于得到t6的方法。262()(...)ftttt故使两个骰子掷出n点的方法数等价于求中tn的系数。这个函数f(t)称为母函数。母函数方法的基本思想：把离散数列和幂级数一一对应起来，把离散数列间的相互结合关系对应成为幂级数间的运算关系，最后由幂级数形式来确定离散数列的构造。再来看下面的例子：121221213112(1)(1)(1)1()(),nnnnnnaxaxaxaaaxaaaaaaxaaax若令a1=a2=…=an=1，则有()(,)(,)(,).21112nnxCnxCnxCnnx这就是二项式展开定理。()()()111mnmnxxx[(,)(,)(,)][(,)(,)(,)](,)(,)(,)010101nmmnCnCnxCnnxCmCmxCmmxCmnCmnxCmnmnx比较等号两端项对应系数，可以得到恒等式：(,)(,)(,)(,)(,)(,)(,).0110CmnrCmCnrCmCnrCmrCn()(/)()1111nmmmnxxxx[(,)(,)(,)][(,)(,)(,)][(,)(,)(,)(,)120101012nmmmnCnCnxCnnxCmCmxCmmxxCmnCmnxCmnxCmnmnx(,)(,)(,)(,)(,)(,)(,).0011CmnmCnCmCnCmCnmCmm比较等式两端的常数项，可以得到恒等式：(1)(,0)(,1)(,)nnxCnCnxCnnx中令x=1可得又如在等式(,0)(,1)(,2)(,)2.nCnCnCnCnn两端对x求导可得：()(,)(,)(,),111122nnnxCnCnxnCnnx再令x=1可得1(,1)2(,2)3(,3)(,)2.nCnCnCnnCnnn类似还可以得到222(,1)2(,2)(,)(1)2.nCnCnnCnnnn还可以类似地推出一些等式，但通过上面一些例子已可见函数(1+x)n在研究序列C(n,0),C(n,1),…,C(n,n)的关系时所起的作用。定义：对于序列a0,a1,a2,…，函数2012()Gxaaxax称为序列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,…显然，,,,12201100uuvuuvuv。,0233uuuv一般的有.3,31nuuuvnnnn若信号输入的序列u0,u1,…的母函数为U(x)，输出的信号序列v0,v1,…的母函数为V(x)，则3()(1)()()(),VxxxUxPxUx其中()Pxxx31被装置的特性所确定，称为该装置的传递函数。设r，w，y分别代表红球，白球，黄球。2(1)(1)(1)rrwy例2有红球两个，白球、黄球各一个，试求有多少种不同的组合方案。22221()()().rywrryrwywryrwrywryw(1)取一个球的组合数为3，即分别取红，白，黄。(2)取两个球的组合数为4，即两个红的，一红一黄，一红一白，一白一黄。(3)取三个球的组合数为3，即两红一黄，两红一白，一红一黄一白。(4)取四个球的组合数为1，即两红一黄一白。22()(1)(1)Gxxxx共有1+3+4+3+1=12种组合方式。43210,,,,cccccrc令取r的组合数为,则序列的母函数为2341343.xxxx令an为从8位男同志中抽取出n个的允许组合数。由于要男同志的数目必须是偶数。故例3某单位有8个男同志，5个女同志，现要组织一个由数目为偶数的男同志和数目不少于2的女同志组成的小组，试求有多少种组成方式？2468()1287028.Axxxxx因此序列a1,a2,…,a8对应的母函数为：1357020,1,(8,2)28,aaaaaaC468(8,4)70,(8,6)28,1.aCaCa类似可得女同志的允许组合数对应的母函数为2345()10105.Bxxxxx()()()()()CxAxBxxxxxxxxx24682345128702810105xxxxxxxxxxxx23456789101112131010285281840728630350150385其中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)。0,,,,kklklbakl()().11101000lllllllBxbxbxaxaxxAx证:则()().!!!1211123mmmmxxxxBxxe例4已知,!!!231123xxxxAxe性质2：若bk=ak+l，则()[()]/.lklkkBxAxaxx10则().!!!xxxxBxexx2221234例5已知,!!!231123xxxxAxe性质3：若bk=a0+…+ak，则()().AxBxx1ba00baa101baaa2012kkbaaaa0121:x:x2:xk:____________________________()/()/()/()Bxaxaxxaxx2012111[]/()()/().aaxaxxAxx201211+)则()Bxxxx231234例6已知(),nAxxxxx2111(),()Axxx2111()Cxxxx2313610().()Bxxx3111性质4：若bk=ak+ak+1+…，则()()().AxAxBxx11baaa0012()baaaAa112301()baaaAaa22340111:x:x2:____________________________()()()()()BxAxxaxxxaxxx2202211111()()()().aaxxAAxAxxxx0111111+)()A1性质5：若bk=kak，则()'().BxxAx性质6：若bk=ak/(1+k)，则()().xBxAxdxx01则()Bxxxx2323例7已知(),nAxxxxx2111'.()xxxx2111性质7：若ck=a0bk+a1bk-1+…+ak-1b1+akb0，则()Cxccxcx2012()().AxBxcab000cabab10110cababab20211201:x:x2:____________________________Cxabbxbxaxbbxbxaxbbxbx2200121012222012()().aaxaxbbxbxAxBx22012012+)令,xBxxxxx232231例8已知(),nAxxxxx2111(),kknknnkkcabk01122()()().()xCxAxBxx31则3.整数的拆分所谓正整数拆分即把正整数分解成若干正整数的和。相当于把n个无区别的球放到n个无标志的盒子，盒子允许空着，也允许放多于一个球。整数拆分成若干整数的和，办法不一，不同拆分法的总数叫做拆分数。拆分可以分为无序拆分和有序拆分；不允许重复的拆分和允许重复的拆分。例9若有1克、2克、3克、4克的砝码各一枚，问能称出那几种重量？有几种可能方案？()()()()xxxx2341111.xxxxxxxxxx2345678910122222从右端的母函数知可称出从1克到10克，系数便是方案数。例如右端有2x5项，即称出5克的方案有2种：5=2+3=1+4。类似的，称出6克的方案也有2种：6=2+4=1+2+3。例10求用1分、2分、3分的邮票贴出不同数值的方案数。()()()xxxxxx22436111以x4为例，其系数为4，即4拆分成1，2，3之和的允许重复的拆分数为4：4=1+1+1+1=1+1+2=1+3=2+2。注意邮票允许重复，因此母函数为：例11若有1克砝码3枚、2克砝码4枚、4克砝码2枚，问能称出那几种质量？各有几种方案？Gxxxxxxxxxx23246848()(1)(1)(1)即可称出1至19克的质量，不同的方案数即为对应项前面的系数。母函数为：xxxxxxxxxxxxxxxxxxx234567891011121314151617181912233445555443322.例12把整数N无序拆分成整数a1,a2,…,an的和，且不允许重复，求不同的拆分数。的不同解的个数。这个问题对应于求不定方程...,,,,,...,nniaxaxaxNxin11220112令bN表示不同的拆分数，则其对应的母函数为：()()()...().naaaGxxxx12111特殊的，当ai=i时，对应的母函数为：()()()...().nGxxxx2111例13把整数N无序拆分成整数a1,a2,…,an的和，允许重复，求不同的拆分数。的不同解的个数。这个问题对应于求不定方程...,,,,,...,nniaxaxaxNxin11220112令bN表示不同的拆分数，则其对应的母函数为：()(....)(...)...(