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

蔣金

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

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

蔣金

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

本文主要研究利用生成函數(shù)來計算卷積和，把求解卷積和的問題轉化為代數(shù)問題，可以大大簡化卷積和的求解過程.該方法簡便、快捷、靈活，為求解一些卷積領域的問題提供借鑒.

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

1 引言

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

給定一個數(shù)列{an}，n=0,1,2,…，則其對應的生成函數(shù)是冪級數(shù) f(x)=a0+a1x+a2x2+….有時生成函數(shù)不一定都用一長串多項式來表示.例如：組合數(shù)序列的生成函數(shù)為

由二項式定理知：fn(x)=(1+x)n.當 n→∞ 時，(1)式是一個無窮級數(shù)，實質上它只是引進一個表示序列的記號而已，沒有必要去討論它的收斂性.此時變量 x只是一種形式變元.

2 正文

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

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

例1有兩個序列

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

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

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

當 k＜0時，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.

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

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

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

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

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

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

即

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

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

則對應的 u(k)*u(k)=(k+1)u(k).

3 結論

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

——————————

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

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

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

O242

A

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

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