22组合数学之母函数

2.1母函数的概念与性质主讲教师魏毅强教授联系电话[e-mail]@tyut.edu.cn2.1母函数递推关系是计数的一个强有力的工具，特别是在做算法分析时是必需的。递推关系的求解主要是利用母函数。当然母函数尚有其他用处，但这主要是介绍解递推关系上的应用。例如)()(1)1()1)(1(212131212121nnnnnnxaaaxaaaaaaxaaaxaxaxa1.问题的提出[e-mail]2项的系数a1a2+a1a3+…+an-1an，中所有的项包括n个元素a1，a2，…an中取两个组合的全体；同理x3项系数包含了从n个元素a1，a2，…an中取3个元素组合的全体。以此类推。2.1母函数若令a1=a2=…=an=1，x2项的系数中每一个组合有1个贡献，其他各项以此类推。故有：nnxnnCxnCxnCx),()2,()1,(1)1(2[e-mail]另一方面：nmnmxxx)1()1()1(nmmnxnmnmCxnmCnmCxmmCxmCmCxnnCxnCnC),()1,()0,(]),()1,()0,([]),()1,()0,([2.1母函数[e-mail]比较等号两端xk项对应系数，可得一等式)0,(),()1,()1,(),()0,(),(nCkmCknCmCknCmCknmC2.1母函数同样对于(1+x)n(1+1/x)m，（设n≥m），用类似的方法可得等式：)0,()0,()0,()0,()0,()0,(),(mCnCmCnCmCnCmnmC[e-mail]2.1递推关系与母函数对于序列{an}，构造一函数关系G(x)=a0+a1x+a2x2+…+anxn+……，称G(x)为序列{an}的母函数。上述母函数也称为普通型母函数。注意到：序列可能是有限的也可能是无限的，从而母函数可能是多项式也可能是无穷级数。母函数的首项是零次幂项，对应序列首项[e-mail]例如，对于序列{1,1,1，…}的母函数为2.1递推关系与母函数xxxxxxHkk-111)(032对于序列{Cnk}的母函数为nnkkknnnnnnnxxCxCxCxCCxH)1()(02210Fibonacci数列{Fn}母函数为1)(kkkxFxG21xxx[e-mail]2.1递推关系与母函数注意到：序列与母函数是一一对应的给定序列，可以写出形式母函数，进而通过求和可以得到序列的母函数。给定母函数，可以将函数展开或幂级数展开成为多项式或幂级数形式，由展开式的唯一性，比较各项系数，可以求得对应序列。[e-mail]2.1母函数]),()2,()1,()0,([]),()1,()0,([]),()1,()0,([21nmmmnxnmnmCxnmCxnmCnmCxxmmCxmCmCxnnCxnCnC比较等式两端的常数,即得所求事实上，(1+x)n(1+1/x)m=x-m(1+x)[e-mail]2.1母函数又如等式：nxnnCxnCxnCnCx),()2,()1,()0,()1(2n两端对x求导，并令x=1可得nnnCnCnCnC2),()2,()1,()0,(2),()3,(3)2,(2)1,(1nnnnnCnCnCnC[e-mail]用类似的方法还可以得到：132)1(),()3,(3)2,(2)1,(nnxnxxnnnCxnCxnCxnC2)1(),()3,(3)2,(2)1,(2222nnnnnCnnCnCnC2.1母函数[e-mail]还可以类似地推出一些等式，但通过上面一些例子已可见函数(1+x)n在研究序列的关系时所起的作用。对其他序列也有同样的结果。现引进母函数概念如下：),(,),1,(),0,(nnCnCnC2.1母函数[e-mail]定义1：对于序列a1,a2,a3,…,构造一函数称函数G(x)是序列a1,a2,a3,…,的母函数，或普母函数(普通型母函数),)(2321xaxaaxG2.1母函数例如(1+x)n是序列C(n,0),C(n,1),…,C(n,n)的母函数。1/(1-x)=1+x+x2+…+xn+…是序列1,1,1，…，1…，的母函数。2.母函数的定义[e-mail]如若已知序列则对应的母函数G(x)便可根据定义给出。反之，如若以求得序列的母函数G(x)，则该序列也随之确定。,,,,210aaa2.1母函数序列母函数一一对应[e-mail]2.1母函数012!)!12()1()sin(kkkxkx例1设序列a1,a2,a3,…,的母函数为G(x)=sin(x),求序列a1,a2,a3,…,解由于所以,2,1,00!)!12()1(212kakakkk，，[e-mail]2.1母函数定义2：对于序列a1,a2,a3,…,构造一函数称函数G(x)是序列a1,a2,a3,…,的指母函数(指数型母函数),2111)(2321xaxaaxG！！例如ex是序列1,1,1，…，1…，的指母函数。[e-mail]又例如nxxxxx32111nxnnxxx!1!!31!3!21!211!1132！所以，阶乘序列{n!}的指母函数为x112.1母函数[e-mail]一个序列和它的母函数一一对应。给了序列便得知它的母函数；反之，求得母函数序列也随之而定。这种关系颇像数学中的积分变换，特别酷似离散序列的Z变换。为了求满足某种递推关系的序列，可把它转换为求对应的母函数G(x)，而G(x)可能满足一代数方程，或代数方程组，甚至于是微分方程。3.母函数的性质2.1母函数[e-mail]不特别说明下面假设{ak}，{bk}两个序列对应的母函数分别为A(x)，B(x)2.1母函数性质1：若则kblk0lkalk{)()(xAxxBl[e-mail]性质1：若则kblk0lkalk{)()(xAxxBl证：)(000)(11011xAxxaxaxbxbxBlllllll2.1母函数[e-mail]例.已知1!3!2!132xexxxxA则)1(!3!2!1)(121xmmmmexxxxxB2.1母函数[e-mail]性质2：若，lkkab则llkkkxxaxAxB/])([)(102.1母函数[e-mail]AxxaxaxaaxAxaxaxaxxaxaaxB/])([/])([)(1)(101122102211221证：2210)(xbxbbxB2.1母函数[e-mail]例.!5!3sin)(53xxxxxA6533/]!51!31[sin!91!71)(xxxxxxxxB2.1母函数[e-mail]性质2：若，则kiikab0xxAxB1)()(证：)::::12102101210100nnaaaabxaaabxaabxab2.1母函数[e-mail])::::12102101210100nnaaaabxaaabxaabxab____________________________)1/()()1/(][)1/()1/()1/()(22102210xxAxxaxaaxxaxxaxaxB2.1母函数[e-mail]例.已知xxxxxAn111)(2232)1(14321)(xxxxxB20)1(1)1(xxkkk2.1母函数[e-mail]类似可得：03323232)1(1)2)(1(2110631)1()4321()(kkxxkkxxxxxxxxxxC2.1母函数[e-mail]性质2：若收敛，则0kkaxxxAAxB1)()1()())1(:)1(:)1(:11021202112100aaAabxaAaabxAaaab____________________________)1()1(]1)[1()(221202xxxaxxxaxxAxB2.1母函数[e-mail]1)()1()1/()(1)1()(102.1母函数[e-mail]性质5.若，则。kkkabxxAxB'例.xxxxA111223211132xxxxxxx则2.1母函数[e-mail]1xdxxAxxB01性质5和性质6的结论是显而易见的。性质6.若，则2.1母函数[e-mail]性质7.若则022110babababackkkkkkiikiba0xBxAxcxccxC22102.1母函数[e-mail]证:。22100xbxbbaxC22101xbxbbxa221022xbxbbxa22102210xbxbbxaxaaxBxA