蔣金

（淮南師范學(xué)院 電氣信息工程學(xué)院，安徽 淮南 232038）

淺析用生成函數(shù)計(jì)算卷積和

蔣金

（淮南師范學(xué)院 電氣信息工程學(xué)院，安徽 淮南 232038）

本文主要研究利用生成函數(shù)來(lái)計(jì)算卷積和，把求解卷積和的問(wèn)題轉(zhuǎn)化為代數(shù)問(wèn)題，可以大大簡(jiǎn)化卷積和的求解過(guò)程.該方法簡(jiǎn)便、快捷、靈活，為求解一些卷積領(lǐng)域的問(wèn)題提供借鑒.

生成函數(shù)；卷積；卷積和

1 引言

生成函數(shù)是解決計(jì)數(shù)問(wèn)題的一個(gè)重要工具.它可用于研究未知數(shù)列規(guī)律，用遞推式求出數(shù)列的通項(xiàng)，也可用于編程與算法設(shè)計(jì)，它對(duì)程序效率與速度有很大改進(jìn).

給定一個(gè)數(shù)列{an}，n=0,1,2,…，則其對(duì)應(yīng)的生成函數(shù)是冪級(jí)數(shù) f(x)=a0+a1x+a2x2+….有時(shí)生成函數(shù)不一定都用一長(zhǎng)串多項(xiàng)式來(lái)表示.例如：組合數(shù)序列的生成函數(shù)為

由二項(xiàng)式定理知：fn(x)=(1+x)n.當(dāng) n→∞ 時(shí)，(1)式是一個(gè)無(wú)窮級(jí)數(shù)，實(shí)質(zhì)上它只是引進(jìn)一個(gè)表示序列的記號(hào)而已，沒(méi)有必要去討論它的收斂性.此時(shí)變量 x只是一種形式變?cè)?

2 正文

在求卷積和的應(yīng)用中，生成函數(shù)構(gòu)成這么一個(gè)多項(xiàng)式函數(shù) g(x)，使得 x的 n次方系 數(shù)為 f(n)，n=0,1,2,….如 序列{0,1,2,…,n,…}對(duì)應(yīng)的生成函數(shù)為 g(x)=0+x+2x2+…+nxn+…，可以看出一個(gè)序列和它的生成函數(shù)是一一對(duì)應(yīng)的.給定一個(gè)序列就可以得到這個(gè)序列的生成函數(shù).反之，如果給定了生成函數(shù)，則生成函數(shù)所對(duì)應(yīng)的序列也隨之而定.例如：兩個(gè)卷積序列 f1(k)、f2(k)

對(duì)應(yīng)的生成函數(shù) F1(x)=1+xF2(x)=1+2x由時(shí)域上的卷積和對(duì)應(yīng)于生成函數(shù)相應(yīng)的乘積得f1(k)*f2(k)=F1(x)F2(x)=(1+x)(1+2x)=1+3x+2x2，

例1有兩個(gè)序列

試求兩序列的卷積和 f(k).

(ⅰ)用卷積和公式算法如下：

將序列 f1(k)、f2(k)的自變量為 i，序列 f1(i),f2(i)如圖 1、2所示；將 f2(i)反轉(zhuǎn)后得 f2(-i)，如圖 3所示.

當(dāng) k＜0時(shí)，f(k)=f1(k)*f2(k)=0；

如此，依次可得

f(2)=f1(0)f2(2)+f1(1)f2(1)+f1(2)f2(0)=6；

f(3)=f1(0)f2(3)+f1(1)f2(2)+f1(2)f2(1)+f1(3)f2(0)=6；

……

（ⅱ）用生成函數(shù)求解得：

F1(x)=1+2x+3x2,F2(x)=1+x+x2+x3.

對(duì) F1(x)F2(x)=(1+2x+3x2)(1+x+x2+x3)計(jì)算如下

由此可見(jiàn)，利用生成函數(shù)求卷積和可以大大簡(jiǎn)化解題過(guò)程.

例 2 求 u(k)*u(k)的卷積和.

U(x)=1+x+x2+x3+…….

利用生成函數(shù)求解卷積和的過(guò)程如下：

若出現(xiàn)分母有平方項(xiàng)或多次方項(xiàng)，可由二項(xiàng)式定理：設(shè)α是任意實(shí)數(shù)，則對(duì)于滿(mǎn)足的所有 a和 b，有(a+b)α=

即

若分式分母中出現(xiàn)1形式，即轉(zhuǎn)化為生成函數(shù)為(1-ax)n1-ax)n的形式.

例如上例中 u(k)*u(k)，對(duì)應(yīng)生成函數(shù)乘積為

則對(duì)應(yīng)的 u(k)*u(k)=(k+1)u(k).

3 結(jié)論

由以上的推論及各事例的運(yùn)算可表明，生成函數(shù)在做卷積和求解方面的簡(jiǎn)化性.生成函數(shù)把卷積和的和運(yùn)算轉(zhuǎn)化為代數(shù)中的乘積運(yùn)算，即是我們熟悉及日常所用的，可以更加方便、快捷地為我們所掌握.在我們平時(shí)做卷積運(yùn)算時(shí)候，比利用教材上的方法更加簡(jiǎn)便，為解決其他類(lèi)似問(wèn)題提供借鑒.

——————————

〔1〕蔣金.用生成函數(shù)求解離散系統(tǒng)的時(shí)域分析[J].齊齊哈爾大學(xué)學(xué)報(bào)（自然科學(xué)版），2013（3）：28-32.

〔2〕孫世新.組合數(shù)學(xué)[M].成都：電子科技大學(xué)出版社，2003.

〔3〕許胤龍，孫淑玲.組合數(shù)學(xué)引論[M].合肥：中國(guó)科學(xué)技術(shù)大學(xué)出版社，2011.

O242

A

1673-260X（2013）04-0001-02

安徽省高校自然科學(xué)基金（No.KJ2013B260）