母函数方法在解竞赛题中的运用

●

(杭州第十一中学 浙江杭州 310053)

母函数方法的实质是将离散数列和幂级数一一对应起来，把离散数列间的相互结合关系对应成为幂级数间的运算关系，最后由幂级数形式来确定离散数列的构造的一种方法．具体地说，就是将一个有限或无限的数列{ak}和形如f(x)=a0+a1x+a2x2+…+akxk+…的函数联系起来，构成对应关系.将其中的f(x)称为数列{ak}的母函数或生成函数，意思是这个数列{ak}是由多项式f(x)生成的．母函数方法一般在解组合问题中应用较多，本文将母函数方法进行推广，通过一些竞赛试题说明它在解方程(方程组)、解操作性问题、解多元求值问题、证明组合恒等式等诸多方面的应用．

1 解方程或方程组

解构造母函数f(x)=(x-x1)(x-x2)…(x-xn)，并设f(x)=xn+an-1xn-1+…+a1x+a，则

即

n+nan-1+…+na1+na0=0,

亦即

1+an-1+…+a1+a0=0，

故f(1)=0．

这说明x=1是方程f(x)=0的一个根，由对称性，不妨设xn=1，代入方程组中可得

同理可解得x1=x2=…=xn-1=xn=1．

2 求数列的通项公式

例2已知在数列{an}中，a0=-1，a1=1,an=2an-1+3an-2+3n(n≥2),求数列的通项an．

解考虑母函数f(x)=a0+a1x+a2x2+…+anxn+…，则

-2xf(x)=-2a0x-2a1x2-2a2x3-…-2an-1xn+…

-3x2f(x)=-3a0x2-3a1x3-3a2x4-…-3an-2xn+…

以上3个式子相加，又a0=-1，a1=1,an=2an-1+3an-2+3n(n≥2),化简得

3 解操作性问题

例3设a1,a2,…,a100,b1,b2,…,b100为互不相同的实数，将它们依如下规则填入100×100的方格中:在第i行和第j列相交处的方格内填入数字ai+bj．已知每一列的所有数字乘积都等于1，证明:每一行的所有数的乘积都等于-1．

证明构造母函数f(x)=(x+a1)(x+a2)…(x+a100)-1，则多项式f(x)的次数为100，且f(x)的首项系数为1．依题意知f(bi)=0(i=1,2,…,100)，从而x-bi(i=1,2,…,100)都是f(x)的因式．因为b1,b2,…,b100互不相同，所以f(x)=(x-b1)(x-b2)…(x-b100),即

(x+a1)(x+a2)…(x+a100)-1=(x-b1)(x-b2)…(x-b100).

在上式中，令x=-ai(i=1,2,…,100)，则

-1=(-1)100(a1+b1)(a2+b2)…(a100+b100),

故第i行中所有数的乘积都等于-1．

4 解多元求值问题

例4设x,y,z与w适合:

求x2+y2+z2+w2的值．

(t-1)(t-9)(t-25)(t-49)-x2(t-9)(t-25)(t-49)-y2(t-1)(t-25)(t-49)-

z2(t-1)(t-9)(t-49)-w2(t-1)(t-9)(t-25)=0,

整理得

t4-(1+9+25+49+x2+y2+z2+w2)t3+f(t)=0,

其中f(t)是次数不超过2的多项式，上述方程是关于t的四次方程，它有4个根:4，16，36，64.由韦达定理，得

1+9+25+49+x2+y2+z2+w2=4+16+36+64，

故

x2+y2+z2+w2=36.

5 解组合计数问题

例5在一次实战军事演习中，红方的一条直线防线上设有20个岗位．为了试验5种不同的新式武器，打算安排5个岗位配备这些新式武器，要求第一个和最后一个岗位不配备新式武器，且每相邻5个岗位至少有1个岗位配备新式武器，相邻2个岗位不同时配备新式武器，问共有多少种配备新式武器的方案？

解设20个岗位按先后排序为1，2，…，20，且设第k种新式武器设置的序号为ak(k=1,2,3,4,5)．令x1=a1，x2=a2-a1，x3=a3-a2，x4=a4-a3，x5=a5-a4，x6=20-a5，则

x1+x2+x3+x4+x5+x6=20,(1)

其中2≤xk≤5(k=1,2,3,4,5)，1≤x6≤4．作代换yk=xk-1(k=1,2,3,4,5)，y6=x6，从而式(1)变为

y1+y2+y3+y4+y5+y6=15,(2)

其中1≤yk≤4(k=1,2,3,4,5,6)．

式(2)的解的个数等于(x+x2+x3+x4)6展开式中x15的系数，而

(x+x2+x3+x4)6=x6(1+x+x2+x3)6=x6(1+x)6(1+x2)6，

故只需求(1+x)6(1+x2)6展开式中x9的系数．由

(1+x)6(1+x2)6=(1+6x+15x2+20x3+15x4+6x5+x6)(1+6x2+15x4+20x6+15x8+6x10+x12),

知x9的系数为

6×15+20×20+6×15=580．

因为5种新式武器各不相同，互换位置得到不同的排列数，所以配备新式武器的方案数等于

580×5!=69 600.

6 证明组合恒等式

证明(1+x)2n+1= (1+x)2n(1+x)=[2x+(1+x2)]n(1+x)=

评注运用母函数方法证明组合恒等式时，常常是适当选择一个母函数，用2种不同的方法将它展开成2个幂级数，然后由同次幂的系数相等得到要证明的组合恒等式．