母函數(shù)方法在解競賽題中的運用

●

(杭州第十一中學(xué) 浙江杭州 310053)

母函數(shù)方法的實質(zhì)是將離散數(shù)列和冪級數(shù)一一對應(yīng)起來，把離散數(shù)列間的相互結(jié)合關(guān)系對應(yīng)成為冪級數(shù)間的運算關(guān)系，最后由冪級數(shù)形式來確定離散數(shù)列的構(gòu)造的一種方法．具體地說，就是將一個有限或無限的數(shù)列{ak}和形如f(x)=a0+a1x+a2x2+…+akxk+…的函數(shù)聯(lián)系起來，構(gòu)成對應(yīng)關(guān)系.將其中的f(x)稱為數(shù)列{ak}的母函數(shù)或生成函數(shù)，意思是這個數(shù)列{ak}是由多項式f(x)生成的．母函數(shù)方法一般在解組合問題中應(yīng)用較多，本文將母函數(shù)方法進行推廣，通過一些競賽試題說明它在解方程(方程組)、解操作性問題、解多元求值問題、證明組合恒等式等諸多方面的應(yīng)用．

1 解方程或方程組

解構(gòu)造母函數(shù)f(x)=(x-x1)(x-x2)…(x-xn)，并設(shè)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的一個根，由對稱性，不妨設(shè)xn=1，代入方程組中可得

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

2 求數(shù)列的通項公式

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

解考慮母函數(shù)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設(shè)a1,a2,…,a100,b1,b2,…,b100為互不相同的實數(shù)，將它們依如下規(guī)則填入100×100的方格中:在第i行和第j列相交處的方格內(nèi)填入數(shù)字ai+bj．已知每一列的所有數(shù)字乘積都等于1，證明:每一行的所有數(shù)的乘積都等于-1．

證明構(gòu)造母函數(shù)f(x)=(x+a1)(x+a2)…(x+a100)-1，則多項式f(x)的次數(shù)為100，且f(x)的首項系數(shù)為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行中所有數(shù)的乘積都等于-1．

4 解多元求值問題

例4設(shè)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)是次數(shù)不超過2的多項式，上述方程是關(guān)于t的四次方程，它有4個根:4，16，36，64.由韋達定理，得

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

故

x2+y2+z2+w2=36.

5 解組合計數(shù)問題

例5在一次實戰(zhàn)軍事演習(xí)中，紅方的一條直線防線上設(shè)有20個崗位．為了試驗5種不同的新式武器，打算安排5個崗位配備這些新式武器，要求第一個和最后一個崗位不配備新式武器，且每相鄰5個崗位至少有1個崗位配備新式武器，相鄰2個崗位不同時配備新式武器，問共有多少種配備新式武器的方案？

解設(shè)20個崗位按先后排序為1，2，…，20，且設(shè)第k種新式武器設(shè)置的序號為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)變?yōu)?/p>

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

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

式(2)的解的個數(shù)等于(x+x2+x3+x4)6展開式中x15的系數(shù)，而

(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的系數(shù)．由

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

知x9的系數(shù)為

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

因為5種新式武器各不相同，互換位置得到不同的排列數(shù)，所以配備新式武器的方案數(shù)等于

580×5!=69 600.

6 證明組合恒等式

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

評注運用母函數(shù)方法證明組合恒等式時，常常是適當(dāng)選擇一個母函數(shù)，用2種不同的方法將它展開成2個冪級數(shù)，然后由同次冪的系數(shù)相等得到要證明的組合恒等式．