母函的应用

2003年6月湖北大学成人教育学院学报Jun.,2003第21卷第3期 Journal of Adult Education College of Hubei University Vol.21No.3母函的应用戴想元(湖北大学数学与计算机科学学院,武汉,430062)【摘要】母函数是组合数学中用来研究有关问题的重要工具。本文主要介绍怎样利用母函数来计数,解递推关系以及求和。【关键词】母函数;计数;解递推关系;求和【中图分类号】Q157【文献标识码】A【文章编号】109-0444(2003)03-0073-06母函数的基本概念为了引入母函数的概念,初步认识母函数与我们所讨论的计数问题是如何联系在一起的,先来看个例子引例:求从n个元素a1a2中取r个元素的组合方式和组合数(简称n元集的r-组合数)解:考虑n个二项式1+a1x,1+a2x,…,1+anx乘积的展开式中x(i=1,2,…,n)的系数:(1+a1x)(1+a2x)…(1+ax)…(1+anx)1+(a1+a2+…+an)x+(a(2+…+aa+aa1+1…a;+r-1+2…an)x上式展式的特点1)x的系数是从n个元素中取r个元素的所有组合方式,取a1=a2an=1时,x的系数就是n元素的的r一组合数(")2)上述结论不是偶然的,因每一个二项式1+a1x表明了元素a在从n个元素中取r个元素时的两种状态:不取a,或者取a,当用1去与其他二项式相乘时,表示不取a;当用ax去与其他二项式相乘时,表示取了a;所以最后x的系数就是n元素的r-组合方式。当a=1(i=1,2,…,n)时,x的系数就是n元素的r—组合数3)当只考虑计数时,令a1=a2an=1,则有(1+x)于是组合数列{()}≥。就与母函数(1+x)相对应定义设数列{ak}k≥0=(a,a1,…,ak,…)是一个无穷数列,则称形式幂级数为数列(ak)k≥0的普通型母函数,简称为普母函数或母五称形式幂级数中国煤化工(x)=a0+a1x+a2CNMHG为数列(ak)k≥的指数型母函数,简称指母函数收稿日期]2003-04-02作者简介]戴想元(1944—),男,湖北应城人,湖北大学数学与计算机科学学院副教授定义中“形式幂级数”一语,指的是撇开了级数的收敛性问题。而当我们须对幂级数进行微分或积分时,则认为该级数具有分析学中函数应满足的性质。形式幂级数的代数运算,即加、减和乘法都按多项式运算法则进行,而微分、积分则按数学分析中的算法则进行二、母函数与排列组合基本公式Ⅰ,从n元集S={a1,a2,…,an}中取k个元的组合,其中限定元素a出现的次数之集为M(i=1,2,…,n)时的组合数记为c,则数列(ck)≥0的母函数是f(x)基本公式Ⅰ包含了许多特殊情况,如1°当M1=MMn{0,1}时,f(x)=(1+x)2°当M1=M{0,1,2,…},f(x)=(1+x+x2+…)3°当M1=M2=…=Mn={0,2,4,…},f(x)=(1+x2+x4+…)基本公式Ⅰ的一个等价命题是:把k个相同的球放入n个互不相同的盒子a1,a2,…,an中,要求盒子a,中放入m个球,其放法数的母函数是m(>x")对于我们要求的组合数c,如果能找到其对立的母函数f(x)=m(∑x),将这母函数展开成f(x)=∑cx,则x的系数c就是我们要求的组合数例1求证n元集的k-可重组合数是(+k-1)k证明所谓n元集的k可重组合指的是从n元集s=(a1,a2,…,an}中选取的无序k元组(x1x2,…,x),这里x1,x2,…,xk∈S,它们可彼此相同,每个元素a,出现的次数集M1={0,1,2,…k)(依n元集的k一可重组合的的定义,这组合数的母函数是f(x)=(1+x+x2+…)将其展开(1+x+x2+…)"=(n(-n-1)(-n-2)…(-n-t+1)(-1)2n(n+1)(n+2)…(+=1)所求n元集的k一可重组合数就是上面展开式中x的系数(+k-1应该强调的是,在求可以重复的组合数时,常用函数=(1-x)”,今后可以把它的展开式中国煤化工)x作为公式来用CNMHG例2求n元集S={a1,a2,…,an}的k一可重组合数c,要求a1,a2出现偶数次,其余元素出现奇数次解该问题的母函数是f(x)=(1+)2(x+x3+x5+…)”-2+r-1k上式中x的系数就是ck2基本公式I,从n元集S={a1,a2,…,an}中取k个元的排列,其中限定元b出现的次数之集是M(i1,2,…,n),把这种排列的个数记为p,则数列()≥0的母函数是f(x)=∑x5k!=m(∑,)注:1°若M1=M2=…Mn={0,1,2,…},则f(x)=(1+2若M1=M2=Mn={0,2,4,…},则f(x)={1+2,+M1=M2=…=Mn={1,3,5,…},则f(x)=(x+,++…)=(对于我们要求的排列数p,如果能找到其对应的母函数∫(x)=Ⅱ(、x),将这母函数展开成f(x)=∑Pk1,则的系数内就是我们要求的排列数例3求字母集{a,b,c,d}上含偶数个a的k元字的个数f解()≥。的母函数是(1+x++…)(1+x++(elr+ezr)的系数是=D(4+2)。例4用1,2,3,4这四个数字组成7位数,要求1出现2次或3次,2出现偶数次,4出现奇数次,求这样7位数的个数解此排列数的母函数是+;+2)(1+(2.(e-e-)·e(-1)”-)取的系数1(3×6×7+6×7+3×5×6中国煤化工CNMHG,这就是所求的7位数的个数。必须应注意的是,要弄清楚我们所讨论的问题是组合问题还是排列问题,如果是组合问题就用基本公式I,如果是排列问题则用基本公式Ⅱ,切莫用错公式、母函数与数列求和设数(ak)k≥0=(a0,a1,a2,…,ak,…)的母函数是+用函数,1=1+x+x2+…去乘f(x)f(x)=(1+x+x2+…)(a+a1x+1+(a0+a1)x+(a0+a1+a2)x2+…+(a0+a1+…+a)x+…上式右边x的系数a。+aak刚好是数列(a)=0中前(k+1)项:ao,a1,…,a4的和,正因为如此,我们称函数为求和函数上述事实表明,要求某数列(ak)0前(m+1)项的和,事先求出数列的母函数f(x),然后用去乘f(x),再将函数,f(x)展开,则展开式中xm的系数就是要求的和an+a1+…+an例5求和12+22+…+n2。解先求数列(n2)。0的母函数,由1+x+x2+…+x+…两边微分:(1-x)2=1+2x+3x2+…+rx两边同乘以x并微分得(1-x)=1+2x+32x2+…+r2x-1+(1+x)两边同乘x:(1-x)=x+2x2+32x3+…+r2x+由此得到了数列(n2)≥0的母函数进一步知:12+22+…+n2的母函数是1x(1+x)=(x+x2)3+x"的系数是)+(3)=(n+2)(n+1)n⊥(n+1)n(m-1)(n+1)(2n+1)即12+22+…+n(n+1)(2n+1)例6设数列(a4)=:a=k(k+1)(k+2),求数列的和S=∑k(k+1)(k+2)解由x微分得两边乘以x:a工=>r,再微分得HHa中国煤化工两边乘以xx3=>k(k+1)x4+2,…,仿上继CNMH@+1)(k+2)的母函数是6. x5+k-1上式xm的系数是6(4+m即S=k(k+1)(k+2)=6(3+m、例7证明数列a=(2)的母函数是(1-4x)+,由此证明∑(2)(2m2)=4证明(1-4x)-=S(-1)由此知,数列an的母函数是(1—4x)-。应该提出的是,按推广的二项式系数的计算,有恒等式(-1)因a=(2)的母函数是(1-4x),所以n=(2m-2)的母函数也是(1-4x)+,从而n-12n)(2m-2n)的母函数是(1-4x)-(1-4x),即(1-4x)-1因(1-4x)-14x2,其中xm的系数是4m所以2n、2m-2n四、母函数与递推关系根据给岀的已知条件,我们往往不能直接找到所讨论问题的结论,而能找到所讨论问题的一个递推关系,然后再想办法解这个递推关系。借用母函数解递推关系,这是一个很重要的方法。例如,把一对兔子(雌、雄各一只)在某年的开始放到围栏中,每个月这对兔子都生出一对新兔,其中雌雄各一只,由第二个月开始,每对新兔每个月也生出一对新兔,也是雌雄各一只,问一年后围栏中有多少对兔子令∫表示第n个月开始时围栏中兔子的对数,这数∫可分为两类,一类是那些第n-1个月初就存在的兔子,仍然存在,这就是f。1;另一类是每对在第n-2个月初就存在的兔子将在第n-1月生出对新兔来,这数是fn2,由加法原则有递推关系fn=f-1+fn-2(n≥2)fn=1,f1=1例8解递推关系n=fn-1+fn2(n≥2),这里f0=f1=1解令数列(f)。的母函数为f(x)=∑fx由递推关系f=f-1+f2有,r"=>f-II"+>fm-2I'H≥2=xXfm-Ix"-1+x2fa-2x-2中国煤化工r>fnr"+x2>f,x'CNMHG即f(x)-f0-f1x=x(f(x)-/0)+x2f(x)将f=f1=1代入上式并整理得,数列(fn)。。的母函数是将f(x)展开:f(x)=1-x-x2(1-a1x)(1-a2x(>af+lr这里a1=1+√52.上式中x的系数就是所求的数fn5)5例9解递推关系fn=f1fn-1+f2fn-2+…+fn-1f1(n≥2)这里f1=1解令f(x)=∑x由递推关系fn=f11-1+ff-2+…+ff1有f灬(f1fn-1+f2fn-2+…+fn-1f1)xf1f1x2+(f1f2+f2f1)x3+(f1f3+f2f2+f3f1)x4+…+(f1fn-1+f2f(n2)++fn-1f1)x+由于f(x)=f1x+f2x2+…+fnx”+…所以f(x)=∑(/1fn-1+f2f2-2+…+fn-1f)x又∑fx”=f(x)-fx,故由(*)式有f(x)-f1x=f(x),即f2(x)-f(x)+x=0(这里f1=1)解得f(x),由于f(0)=0,所以f(x)f(x)=1-2=2-2>(-1)2x(2k-2)(k-1)!k上式右边x”的系数就是fnfn!(n-1)!nn-1由以上两个例子可以看出,许多较为复杂的递推关系均可用母函数求解,而且解的过程近乎程序化,这是其他方法所不及的。参考文献1]魏万迪.组合论[M].北京:科学出版社[2]李乔.组合数学[M].北京:高等教育出版社3]屈婉玲.组合数学[M].北京大学出版社中国煤化工〔责仼编辑:慎思CNMHG