生成函数

英文

generating function

简介

亦称母函数、发生函数、计数函数.一类形式幂级数.它在组合数学中用以解决计数问题.生成函数方法的系统描述，最早见于拉普拉斯(Laplace，P.-S.)1812年的名著《概率解析理论》.普通生成函数和指数型生成函数是两种常用的生成函数.记数列a₀，a₁，a₂，…，a_n，…为{a_n}.数列{a_n}的普通生成函数(有时简称生成函数)定义为形式幂级数：

G{a_n}≡a₀+a₁x+a₂x²+…+a_nxⁿ+…

数列{a_n}称为G{a_n}的普通生成数列.这里，变量x一般取自实数域或复数域，x也可看做是一种形式变元，此时形式幂级数可按通常方式定义加法、乘法、形式微积分等运算，从而将形式幂级数看成元素，其全体做成一个交换环，在其中不涉及收敛性等问题.两个形式幂级数a₀+a₁x+a₂x²+…+a_nxⁿ+…和b₀+b₁x+b₂x²+…+b_nxⁿ+…相等，当且仅当a_k＝b_k，k=0，1，2，…普通生成函数有下列运算法则：

1.G{a_k}+G{b_k}=G{a_k+b_k}.

2.G{a_k}·G{b_k}=G｛c_k｝，这里

c_k≡a₀b_k+a₁b_k-1+…+a_k-1b₁+a_kb₀，

称为数列{a_k}和{b_k}的卷积.数列{a_n}的指数型生成函数定义为形式幂级数

数列{a_n}称为Ge{a_n}的指数生成数列(参见“指数型生成函数”).