2003年6月湖北大學(xué)成人教育學(xué)院學(xué)報Jun.,2003第21卷第3期 Journal of Adult Education College of Hubei University Vol.21No.3母函的應(yīng)用戴想元(湖北大學(xué)數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院,武漢,430062)【摘要】母函數(shù)是組合數(shù)學(xué)中用來研究有關(guān)問題的重要工具。本文主要介紹怎樣利用母函數(shù)來計數(shù),解遞推關(guān)系以及求和?！娟P(guān)鍵詞】母函數(shù);計數(shù);解遞推關(guān)系;求和【中圖分類號】Q157【文獻(xiàn)標(biāo)識碼】A【文章編號】109-0444(2003)03-0073-06母函數(shù)的基本概念為了引入母函數(shù)的概念,初步認(rèn)識母函數(shù)與我們所討論的計數(shù)問題是如何聯(lián)系在一起的,先來看個例子引例:求從n個元素a1a2中取r個元素的組合方式和組合數(shù)(簡稱n元集的r-組合數(shù))解:考慮n個二項式1+a1x,1+a2x,…,1+anx乘積的展開式中x(i=1,2,…,n)的系數(shù):(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的系數(shù)是從n個元素中取r個元素的所有組合方式,取a1=a2an=1時,x的系數(shù)就是n元素的的r一組合數(shù)(")2)上述結(jié)論不是偶然的,因每一個二項式1+a1x表明了元素a在從n個元素中取r個元素時的兩種狀態(tài):不取a,或者取a,當(dāng)用1去與其他二項式相乘時,表示不取a;當(dāng)用ax去與其他二項式相乘時,表示取了a;所以最后x的系數(shù)就是n元素的r-組合方式。當(dāng)a=1(i=1,2,…,n)時,x的系數(shù)就是n元素的r—組合數(shù)3)當(dāng)只考慮計數(shù)時,令a1=a2an=1,則有(1+x)于是組合數(shù)列{()}≥。就與母函數(shù)(1+x)相對應(yīng)定義設(shè)數(shù)列{ak}k≥0=(a,a1,…,ak,…)是一個無窮數(shù)列,則稱形式冪級數(shù)為數(shù)列(ak)k≥0的普通型母函數(shù),簡稱為普母函數(shù)或母五稱形式冪級數(shù)中國煤化工(x)=a0+a1x+a2CNMHG為數(shù)列(ak)k≥的指數(shù)型母函數(shù),簡稱指母函數(shù)收稿日期]2003-04-02作者簡介]戴想元(1944—),男,湖北應(yīng)城人,湖北大學(xué)數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院副教授定義中“形式冪級數(shù)”一語,指的是撇開了級數(shù)的收斂性問題。而當(dāng)我們須對冪級數(shù)進(jìn)行微分或積分時,則認(rèn)為該級數(shù)具有分析學(xué)中函數(shù)應(yīng)滿足的性質(zhì)。形式冪級數(shù)的代數(shù)運(yùn)算,即加、減和乘法都按多項式運(yùn)算法則進(jìn)行,而微分、積分則按數(shù)學(xué)分析中的算法則進(jìn)行二、母函數(shù)與排列組合基本公式Ⅰ,從n元集S={a1,a2,…,an}中取k個元的組合,其中限定元素a出現(xiàn)的次數(shù)之集為M(i=1,2,…,n)時的組合數(shù)記為c,則數(shù)列(ck)≥0的母函數(shù)是f(x)基本公式Ⅰ包含了許多特殊情況,如1°當(dāng)M1=MMn{0,1}時,f(x)=(1+x)2°當(dāng)M1=M{0,1,2,…},f(x)=(1+x+x2+…)3°當(dāng)M1=M2=…=Mn={0,2,4,…},f(x)=(1+x2+x4+…)基本公式Ⅰ的一個等價命題是:把k個相同的球放入n個互不相同的盒子a1,a2,…,an中,要求盒子a,中放入m個球,其放法數(shù)的母函數(shù)是m(>x")對于我們要求的組合數(shù)c,如果能找到其對立的母函數(shù)f(x)=m(∑x),將這母函數(shù)展開成f(x)=∑cx,則x的系數(shù)c就是我們要求的組合數(shù)例1求證n元集的k-可重組合數(shù)是(+k-1)k證明所謂n元集的k可重組合指的是從n元集s=(a1,a2,…,an}中選取的無序k元組(x1x2,…,x),這里x1,x2,…,xk∈S,它們可彼此相同,每個元素a,出現(xiàn)的次數(shù)集M1={0,1,2,…k)(依n元集的k一可重組合的的定義,這組合數(shù)的母函數(shù)是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一可重組合數(shù)就是上面展開式中x的系數(shù)(+k-1應(yīng)該強(qiáng)調(diào)的是,在求可以重復(fù)的組合數(shù)時,常用函數(shù)=(1-x)”,今后可以把它的展開式中國煤化工)x作為公式來用CNMHG例2求n元集S={a1,a2,…,an}的k一可重組合數(shù)c,要求a1,a2出現(xiàn)偶數(shù)次,其余元素出現(xiàn)奇數(shù)次解該問題的母函數(shù)是f(x)=(1+)2(x+x3+x5+…)”-2+r-1k上式中x的系數(shù)就是ck2基本公式I,從n元集S={a1,a2,…,an}中取k個元的排列,其中限定元b出現(xiàn)的次數(shù)之集是M(i1,2,…,n),把這種排列的個數(shù)記為p,則數(shù)列()≥0的母函數(shù)是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+,++…)=(對于我們要求的排列數(shù)p,如果能找到其對應(yīng)的母函數(shù)∫(x)=Ⅱ(、x),將這母函數(shù)展開成f(x)=∑Pk1,則的系數(shù)內(nèi)就是我們要求的排列數(shù)例3求字母集{a,b,c,d}上含偶數(shù)個a的k元字的個數(shù)f解()≥。的母函數(shù)是(1+x++…)(1+x++(elr+ezr)的系數(shù)是=D(4+2)。例4用1,2,3,4這四個數(shù)字組成7位數(shù),要求1出現(xiàn)2次或3次,2出現(xiàn)偶數(shù)次,4出現(xiàn)奇數(shù)次,求這樣7位數(shù)的個數(shù)解此排列數(shù)的母函數(shù)是+;+2)(1+(2.(e-e-)·e(-1)”-)取的系數(shù)1(3×6×7+6×7+3×5×6中國煤化工CNMHG,這就是所求的7位數(shù)的個數(shù)。必須應(yīng)注意的是,要弄清楚我們所討論的問題是組合問題還是排列問題,如果是組合問題就用基本公式I,如果是排列問題則用基本公式Ⅱ,切莫用錯公式、母函數(shù)與數(shù)列求和設(shè)數(shù)(ak)k≥0=(a0,a1,a2,…,ak,…)的母函數(shù)是+用函數(shù),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的系數(shù)a。+aak剛好是數(shù)列(a)=0中前(k+1)項:ao,a1,…,a4的和,正因為如此,我們稱函數(shù)為求和函數(shù)上述事實表明,要求某數(shù)列(ak)0前(m+1)項的和,事先求出數(shù)列的母函數(shù)f(x),然后用去乘f(x),再將函數(shù),f(x)展開,則展開式中xm的系數(shù)就是要求的和an+a1+…+an例5求和12+22+…+n2。解先求數(shù)列(n2)。0的母函數(shù),由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+由此得到了數(shù)列(n2)≥0的母函數(shù)進(jìn)一步知:12+22+…+n2的母函數(shù)是1x(1+x)=(x+x2)3+x"的系數(shù)是)+(3)=(n+2)(n+1)n⊥(n+1)n(m-1)(n+1)(2n+1)即12+22+…+n(n+1)(2n+1)例6設(shè)數(shù)列(a4)=:a=k(k+1)(k+2),求數(shù)列的和S=∑k(k+1)(k+2)解由x微分得兩邊乘以x:a工=>r,再微分得HHa中國煤化工兩邊乘以xx3=>k(k+1)x4+2,…,仿上繼CNMH@+1)(k+2)的母函數(shù)是6. x5+k-1上式xm的系數(shù)是6(4+m即S=k(k+1)(k+2)=6(3+m、例7證明數(shù)列a=(2)的母函數(shù)是(1-4x)+,由此證明∑(2)(2m2)=4證明(1-4x)-=S(-1)由此知,數(shù)列an的母函數(shù)是(1—4x)-。應(yīng)該提出的是,按推廣的二項式系數(shù)的計算,有恒等式(-1)因a=(2)的母函數(shù)是(1-4x),所以n=(2m-2)的母函數(shù)也是(1-4x)+,從而n-12n)(2m-2n)的母函數(shù)是(1-4x)-(1-4x),即(1-4x)-1因(1-4x)-14x2,其中xm的系數(shù)是4m所以2n、2m-2n四、母函數(shù)與遞推關(guān)系根據(jù)給岀的已知條件,我們往往不能直接找到所討論問題的結(jié)論,而能找到所討論問題的一個遞推關(guān)系,然后再想辦法解這個遞推關(guān)系。借用母函數(shù)解遞推關(guān)系,這是一個很重要的方法。例如,把一對兔子(雌、雄各一只)在某年的開始放到圍欄中,每個月這對兔子都生出一對新兔,其中雌雄各一只,由第二個月開始,每對新兔每個月也生出一對新兔,也是雌雄各一只,問一年后圍欄中有多少對兔子令∫表示第n個月開始時圍欄中兔子的對數(shù),這數(shù)∫可分為兩類,一類是那些第n-1個月初就存在的兔子,仍然存在,這就是f。1;另一類是每對在第n-2個月初就存在的兔子將在第n-1月生出對新兔來,這數(shù)是fn2,由加法原則有遞推關(guān)系fn=f-1+fn-2(n≥2)fn=1,f1=1例8解遞推關(guān)系n=fn-1+fn2(n≥2),這里f0=f1=1解令數(shù)列(f)。的母函數(shù)為f(x)=∑fx由遞推關(guān)系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代入上式并整理得,數(shù)列(fn)。。的母函數(shù)是將f(x)展開:f(x)=1-x-x2(1-a1x)(1-a2x(>af+lr這里a1=1+√52.上式中x的系數(shù)就是所求的數(shù)fn5)5例9解遞推關(guān)系fn=f1fn-1+f2fn-2+…+fn-1f1(n≥2)這里f1=1解令f(x)=∑x由遞推關(guān)系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”的系數(shù)就是fnfn!(n-1)!nn-1由以上兩個例子可以看出,許多較為復(fù)雜的遞推關(guān)系均可用母函數(shù)求解,而且解的過程近乎程序化,這是其他方法所不及的。參考文獻(xiàn)1]魏萬迪.組合論[M].北京:科學(xué)出版社[2]李喬.組合數(shù)學(xué)[M].北京:高等教育出版社3]屈婉玲.組合數(shù)學(xué)[M].北京大學(xué)出版社中國煤化工〔責(zé)仼編輯:慎思CNMHG