浅析用生成函数计算卷积和

蒋金

（淮南师范学院 电气信息工程学院，安徽 淮南 232038）

浅析用生成函数计算卷积和

蒋金

（淮南师范学院 电气信息工程学院，安徽 淮南 232038）

本文主要研究利用生成函数来计算卷积和，把求解卷积和的问题转化为代数问题，可以大大简化卷积和的求解过程.该方法简便、快捷、灵活，为求解一些卷积领域的问题提供借鉴.

生成函数；卷积；卷积和

1 引言

生成函数是解决计数问题的一个重要工具.它可用于研究未知数列规律，用递推式求出数列的通项，也可用于编程与算法设计，它对程序效率与速度有很大改进.

给定一个数列{an}，n=0,1,2,…，则其对应的生成函数是幂级数 f(x)=a0+a1x+a2x2+….有时生成函数不一定都用一长串多项式来表示.例如：组合数序列的生成函数为

由二项式定理知：fn(x)=(1+x)n.当 n→∞ 时，(1)式是一个无穷级数，实质上它只是引进一个表示序列的记号而已，没有必要去讨论它的收敛性.此时变量 x只是一种形式变元.

2 正文

在求卷积和的应用中，生成函数构成这么一个多项式函数 g(x)，使得 x的 n次方系 数为 f(n)，n=0,1,2,….如 序列{0,1,2,…,n,…}对应的生成函数为 g(x)=0+x+2x2+…+nxn+…，可以看出一个序列和它的生成函数是一一对应的.给定一个序列就可以得到这个序列的生成函数.反之，如果给定了生成函数，则生成函数所对应的序列也随之而定.例如：两个卷积序列 f1(k)、f2(k)

对应的生成函数 F1(x)=1+xF2(x)=1+2x由时域上的卷积和对应于生成函数相应的乘积得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；

……

（ⅱ）用生成函数求解得：

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

对 F1(x)F2(x)=(1+2x+3x2)(1+x+x2+x3)计算如下

由此可见，利用生成函数求卷积和可以大大简化解题过程.

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

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

利用生成函数求解卷积和的过程如下：

若出现分母有平方项或多次方项，可由二项式定理：设α是任意实数，则对于满足的所有 a和 b，有(a+b)α=

即

若分式分母中出现1形式，即转化为生成函数为(1-ax)n1-ax)n的形式.

例如上例中 u(k)*u(k)，对应生成函数乘积为

则对应的 u(k)*u(k)=(k+1)u(k).

3 结论

由以上的推论及各事例的运算可表明，生成函数在做卷积和求解方面的简化性.生成函数把卷积和的和运算转化为代数中的乘积运算，即是我们熟悉及日常所用的，可以更加方便、快捷地为我们所掌握.在我们平时做卷积运算时候，比利用教材上的方法更加简便，为解决其他类似问题提供借鉴.

——————————

〔1〕蒋金.用生成函数求解离散系统的时域分析[J].齐齐哈尔大学学报（自然科学版），2013（3）：28-32.

〔2〕孙世新.组合数学[M].成都：电子科技大学出版社，2003.

〔3〕许胤龙，孙淑玲.组合数学引论[M].合肥：中国科学技术大学出版社，2011.

O242

A

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

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