母函數方法在解競賽題中的運用

●

(杭州第十一中學 浙江杭州 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個冪級數，然后由同次冪的系數相等得到要證明的組合恒等式．