现在来填上之前那个坑。

一些定义和约定

定义形式幂级数

为数列 \(\{a_n\}\) 的普通生成函数（\(\texttt{Ordinary Generating function-OGF}\)）。

而 \(a_n\) 称为 \(x^n\) 在 \(F(x)\) 中的系数 （\(\texttt{Coefficient}\)），写作

\(\{a_n\}\) 可以为有穷序列也可以是无穷序列。

\(\texttt{for example:}\)

数列 \(\{a_n\}=\{0,1,2,3,\cdots\}\) 的普通生成函数是 \(\sum_{n\geq0}n\times x^n\)

而数列 \(\{a_n\}=\{ 0,1,2,3 \}\) 的普通生成函数是 \(0+x+2x^2+3x^3\)

数列 \(\{a_n\}\) 的起点决定了幂的起点。以上我们约定以 \(0\) 作起点编号，下同。

基本运算

与复数或反演等其他数论知识类似，生成函数也有自己基本运算的定义。也就是生成函数与生成函数之间的直接运算。

加减

假设有数列 \(\{a_n\},\{b_n\}\) 各自的 OGF \(F(x),G(x)\)。根据定义则有：

我们在序列的定义中有序列 \(\{ a\pm b\}\) 的定义，所以我们可以认为 \(F(x)\pm G(x)\) 为 \(\{ a\pm b\}\)的 OGF。

卷积

对于函数来说乘法运算就是做卷积，所以定义数列 \(\{a_n\},\{b_n\}\) 各自的 OGF \(F(x),G(x)\) 卷积可得：

那么同理 \(F(x)\sdot G(x)\) 是数列 \(\{c_n\}=\displaystyle\{ \sum_{i=0}^n a_ib_{n-i}\}\) 的 OGF，也就是两数列卷积的 OGF。

移位

我们可以将生成函数进行移位，具体表现就是原来数列对应的生成函数编号整体变小向前移或变大向后移。

想做移位我们有

生成函数是不存在负指数的，所以前移时我们减去前 \(m\) 项。

求导与积分

如果单独对 \(a_nx^n\) 求很简单：

对上式求导得：

积分得：

所以对生成函数逐项求导/积分整理得：

数学(7)——生成函数入门

原文：https://www.cnblogs.com/reywmp/p/14783252.html