专栏文章

生成函数的数学基础

MMoYuFang
算法·理论参与者 46已保存评论 58

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
58 条
当前快照
1 份
快照标识符
@mhz5tfae
此快照首次捕获于
2025/11/15 01:56
3 个月前
此快照最后确认于
2025/11/29 05:25
3 个月前
查看原文
第一次接触生成函数在 OI\text{OI} 中的组合计数题，然后在网上找了许多讲解生成函数的 blog 学习，从胡小兔大佬的【趣谈生成函数】入门，再到从 cmd 大佬【多项式计数杂谈】里一览生成函数的全貌，非常感谢这些大佬们让我这个无名之辈窥见这一美丽的数学结构，也了解到许多有趣的组合计数。
网上介绍生成函数的 blog 里，一般直接给出关于生成函数的运算法则以及基本公式，将它们默认为正确，在此基础上探讨生成函数在组合计数、求和式计算中的各种技巧与应用，却并未给出这些运算法则和基本公式的正确性证明。
自然的，在学习过程中遇到的各种天花乱坠技巧使我好奇它们的正确性证明是什么。
rqy 大佬在 【浅谈 OI 中常用的一些生成函数运算的合法与正确性】 一文中介绍了一些有关生成函数运算的定义与合法性证明，从这篇 blog 里能了解到关于生成函数的定义以及生成函数极限的定义。
于是我也写了一篇更详细 blog 作为学习笔记，但是这篇 blog 纯粹是从数学的角度上写的，对学习生成函数各种应用没有什么帮助，纯粹只是理性愉悦。
况且讲生成函数应用的好 blog 太多太多了，我再去写应用介绍不过是重复造轮子，写的也不如其它 blog 好。
网上介绍生成函数正确性证明的 blog 几乎见不到（因为大家都不关注它吧），也许这篇 blog 能有点意义。
生成函数的水深不见底，这篇 blog 不可能一次性写完，只能慢慢完善它吧。
目前谈及的内容有
  • 生成函数的定义、为什么生成函数是无穷求和
  • 生成函数的加法运算、乘法运算、除法运算
  • 生成函数的取模运算（多项式取模）
  • 生成函数的极限
  • 无穷求和交换次序
  • 生成函数的复合运算、复合逆
  • 生成函数求导
  • 生成函数泰勒展开
上面这些内容都给了完整的证明，但还有很多生成函数里的内容没有涉及到，将来可能会填下面的坑。
  • 生成函数积分
  • exp⁡\exp 函数、ln⁡\ln 函数
  • 生成函数开根
  • 生成函数的分式域、拉格朗日反演
  • 多元生成函数
事实上生成函数在组合计数之外的领域也有很多应用，它是一种化简计算的利器，在数学分析里也有各种应用，了解它的数学基础也是一件挺有趣的事情。
因为本人只学过数学分析，没学过抽象代数，写的东西都很初级，遇到啰嗦的地方也可以跳过不看。
语文太差了，这篇 blog 肯定写得很枯燥，请见谅。
如果有什么公式错误或者证明错误之类的可以私信或评论区，我尽量改正。

术语约定

  • 自然数集 N={0,1,2,3,...}\mathbb{N}=\{0,1,2,3,...\}，N+={1,2,3,...}\mathbb{N}^+=\{1,2,3,...\}。
  • 设 P\mathbb{P} 是某一数域，如整数域、有理数域、实数域，P∗=P−{0}\mathbb{P}_*=\mathbb{P}-\{0\} 代表去掉 00 元后的数域。
  • 用 {ai:i∈N}\{a_i:i\in\mathbb{N}\} 来表示如下序列
a0,a1,a2,a3,...,ak,...a_0,a_1,a_2,a_3,...,a_k,...
其中 aia_i 可以是 P\mathbb{P} 里的数字，也可以是生成函数，或者其它的东西，总之用序列来表示一组有序对象。
  • 本文中的序列均指无穷序列。
  • 对于一个数字序列 {ai∈P}\{a_i\in\mathbb{P}\}，若 ∃k∈N\exists k\in \mathbb{N}，使得 ∀n>k\forall n>k 有 an=0a_n=0，则称该序列为有限序列，意思这个无穷序列在某一项后均为 00。

正文

在这篇文章中，首先会抛弃掉生成函数作为 “函数” 的意义，认为它只序列的另一种表示方式，然后再逐步证明这个 “ 序列” 具有的种种 “函数” 性质。
生成函数，也称形式幂级数，多项式（评论区有人认为这有问题，我不太确定，但这应该不影响阅读）。
设有序列 {ai:ai∈P}\{a_i:a_i\in\mathbb{P}\}。
根据序列 {ai}\{a_i\}，生成函数 f(x)f(x) 被定义为
f(x)=a0+a1x+a2x2+a3x3+...+anxn+...f(x)=a_0+a_1x+a_2x^2+a_3x^3+...+a_nx^n+...
也可以简记为
f(x)=∑i=0∞aixif(x)=\sum_{i=0}^{\infty}a_ix^i
在生成函数 f(x)f(x) 中，xx 不是未知数，它只是一个占位符，xix^i 用来标记它是第几个占位符。
对于 f(x)f(x) 第 ii 位上的 aia_i，我们记作 f[i]f[i]，f[i]f[i] 也被称作 f(x)f(x) 的第 ii 次项系数，简称 ii 次项。
特别的有 f(x)f(x) 的 00 次项称作常数项。
于是
f(x)=∑i=0∞f[i]xif(x)=\sum_{i=0}^{\infty}f[i]x^i f(x)=f[0]+f[1]x+f[2]x2+f[3]x3+...+f[n]xn+...f(x)=f[0]+f[1]x+f[2]x^2+f[3]x^3+...+f[n]x^n+...
∑∞\displaystyle \sum^\infty 在这里的意义并不是无穷项求和，上述定义看似是无穷项的求和，实质上只是一个记号，只是对序列的另一种表达方式，因为目前已经抛弃掉生成函数作为函数的意义，这一点尤为值得注意。
在下文，会逐步证明 ∑∞\displaystyle \sum^{\infty} 代表序列的意义与生成函数无穷项求和的意义是等价的。
为了提取序列中的某一项系数方便，也记
[xi]f(x)=f[i][x^i]f(x)=f[i]
这并不是多此一举，比如提取 1+x−2x2+3x31+x-2x^2+3x^3 的二次项系数可以简记为 [x2](1+x−2x2+3x3)[x^2](1+x-2x^2+3x^3) 。
对于两个生成函数 f(x)f(x) 与 g(x)g(x)，f(x)=g(x)f(x)=g(x) 当且仅当 ∀i∈N\forall i\in\mathbb{N} 均满足  f[i]=g[i]\ f[i]=g[i]，这阐明了生成函数相等的概念。
若产生生成函数 f(x)f(x) 的序列 {f[i]}\{f[i]\} 是有限序列，则称 f(x)f(x) 是有限多项式、有限幂级数，否则称 f(x)f(x) 是无穷多项式、无穷幂级数。
若 f(x)f(x) 是有限多项式，它的最高次项为 nn，也可以将 f(x)f(x) 记为
f(x)=∑i=0nf[i]xif(x)=\sum_{i=0}^{n}f[i]x^i
或者
f(x)=f[0]+f[1]x+f[2]x2+...+f[n]xnf(x)=f[0]+f[1]x+f[2]x^2+...+f[n]x^n
注意，这仍然不意味着上述两种记法中，符号 ∑i=0n\displaystyle \sum_{i=0}^n 或 ++ 意味着有限项求和，它们仍然只是对有限序列的另一种表达方式，因为我们还未定义关于生成函数的加法运算。
例如：
1.1. 除第 00 项为 a∈Pa\in\mathbb{P} 外的项皆为 00 的序列 {a,0,0,0,...}\{a,0,0,0,...\}，它产生的生成函数为
f(x)=∑i=00f[i]xi=af(x)=\sum_{i=0}^{0}f[i]x^i=a
2.2. 序列 {1,−2,1,−3,0,0,0,...}\{1,-2,1,-3,0,0,0,...\} 产生的生成函数为
f(x)=∑i=03f[i]xi=1−2x+x2−3x3f(x)=\sum_{i=0}^{3}f[i]x^i=1-2x+x^2-3x^3

生成函数的运算

加法运算

设 f(x)f(x) 与 g(x)g(x) 是两个生成函数，它们之间进行加法运算的结果也是一个生成函数，记作 f(x)+g(x)f(x)+g(x)，满足
[xi](f(x)+g(x))=f[i]+g[i](i∈N)[x^i](f(x)+g(x))=f[i]+g[i]\quad(i\in\mathbb{N})
于是
f(x)+g(x)=∑i=0∞(f[i]+g[i])xif(x)+g(x)=\sum_{i=0}^\infty (f[i]+g[i])x^i
P\mathbb{P} 内的数字对加法满足交换律和结合律，因此可以直接推出生成函数对加法运算满足交换律和结合律，也就是说
f(x)+g(x)=g(x)+f(x)f(x)+g(x)=g(x)+f(x) (f(x)+g(x))+h(x)=f(x)+(g(x)+h(x))(f(x)+g(x))+h(x)=f(x)+(g(x)+h(x))
根据生成函数的加法运算，我们可以定义对生成函数的求和式。
设 fi(x) (i=1,2,...,n)f_i(x)\ (i=1,2,...,n) 是一组生成函数，定义它们的有限项求和
∑i=1nfi(x)=f1(x)+f2(x)+f3(x)+...+fn(x)=∑j=0∞(∑i=1nfi[j])xj\begin{aligned} \sum_{i=1}^{n}f_i(x)&=f_1(x)+f_2(x)+f_3(x)+...+f_n(x)\\ &=\sum_{j=0}^\infty\left(\sum_{i=1}^nf_i[j]\right)x^j \end{aligned}
这里仍然强调一下，这并不是说 ∑∞\displaystyle \sum^\infty 与 ∑n\displaystyle \sum^{n} 这两个求和可交换次序，前者是对序列的一种表达方式，后者是对生成函数或普通数字的有限项求和，也就是说对生成函数求和后体现的是下面的一个新序列
{(∑i=1nfi[j]):j∈N}\left\{\left(\sum_{i=1}^nf_i[j]\right):j\in\mathbb{N}\right\}

乘法运算\卷积运算

对于两个生成函数 f(x)f(x) 与 g(x)g(x)，对它们做乘法运算的结果也是一个生成函数，记作 f(x)⋅g(x)f(x)\cdot g(x) 或简写成 f(x)g(x)f(x)g(x)，满足
[xi]f(x)g(x)=∑j=0if[j]g[i−j][x^i]f(x)g(x)=\sum_{j=0}^{i}f[j]g[i-j]
相当于
f(x)g(x)=∑i=0∞(∑j=0if[j]g[i−j])xif(x)g(x)=\sum_{i=0}^\infty\left(\sum_{j=0}^if[j]g[i-j]\right)x^i
这也就是卷积运算。
与生成函数的加法运算类似，乘法运算也满足交换律和结合律，同时乘法运算对加法运算还满足分配律，也就是说
f(x)g(x)=g(x)f(x)f(x)g(x)=g(x)f(x) (f(x)g(x))⋅h(x)=f(x)⋅(g(x)h(x))(f(x)g(x))\cdot h(x)=f(x)\cdot (g(x)h(x)) (f(x)+g(x))⋅h(x)=f(x)h(x)+g(x)h(x)(f(x)+g(x))\cdot h(x)=f(x)h(x)+g(x)h(x)
（证明待补）
ps : 太懒了不想写啊qwq
定义了乘法运算后顺便可以定义幂次运算。
∀n∈N+\forall n\in\mathbb{N}^+，f(x)f(x) 的 nn 次幂记作 fn(x)f^n(x) 或 f(x)nf(x)^n，定义为
fn(x)=∏i=1nf(x)f^n(x)=\prod_{i=1}^{n}f(x)
也即 f(x)f(x) 自乘 nn 次的结果。
特别的，定义 f(x)f(x) 的 00 次幂为 11，f0(x)=1f^0(x)=1，这说明无论 f(x)f(x) 是什么生成函数， f0(x)f^0(x) 都为 11。
若对 f(x)f(x) 的 nn 次幂提取 mm 次项系数，可以记为
[xm]fn(x)=fn[m][x^m]f^n(x)=f^n[m]
注意要把 fn[m]f^n[m] 与 f[m]nf[m]^n 加以区分，前者是 fn(x)f^n(x) 的第 mm 次项系数，后这是 f[m]f[m] 的 nn 次幂。
∀a∈P\forall a\in\mathbb{P}，我们证明
af(x)=∑i=0∞af[i]xiaf(x)=\sum_{i=0}^{\infty}af[i]x^i
解释一下，等式左边的 aa 是一个生成函数 g(x)g(x)，满足 g[0]=a, g[i]=0 (i≥1)g[0]=a,\ g[i]=0\ (i\ge 1)，等式右边的 aa 是一个数字。
根据生成函数乘法的定义，∀i∈N\forall i\in\mathbb{N}，有
[xi]g(x)f(x)=∑j=0ig[j]f[i−j]=g[0]f[i−0]=af[i][x^i]g(x)f(x)=\sum_{j=0}^{i}g[j]f[i-j]=g[0]f[i-0]=af[i]
于是结论成立。
对于两个有限生成函数 f(x),g(x)f(x),g(x)，设它们的最高次分别是 n,mn,m，可以证明
f(x)g(x)=∑i=0n∑j=0mf[i]g[j]xijf(x)g(x)=\sum_{i=0}^{n}\sum_{j=0}^{m}f[i]g[j]x^{ij}
即等式左边的生成函数等于右边一堆生成函数的求和。
这分配律的直接推论。
证明
设有一组生成函数 fi(x)=f[i]xi(i=0,...,n)f_i(x)=f[i]x^i\quad(i=0,...,n) 和一组生成函数 gi(x)=g[i]xi(i=0,...,m)g_i(x)=g[i]x^i\quad(i=0,...,m)
易知
f(x)=∑i=0nfi(x)g(x)=∑i=0mgi(x)f(x)=\sum_{i=0}^n f_i(x)\quad g(x)=\sum_{i=0}^m g_i(x)
且 ∀i∈{0,...,n},j∈{0,...,m}\forall i\in\{0,...,n\},j\in\{0,...,m\} 均有
fi(x)gj(x)=f[i]g[j]xijf_i(x) g_j(x)=f[i]g[j]x^{ij}
于是
f(x)g(x)=(∑i=0nfi(x))(∑j=0mgj(x))=(∑i=0nfi(x)(∑j=0mgj(x)))=∑i=0n∑j=0mfi(x)gj(x)=∑i=0n∑j=0mf[i]g[j]xij\begin{aligned} f(x)g(x)&=\left(\sum_{i=0}^n f_i(x)\right)\left(\sum_{j=0}^m g_j(x)\right)\\ &=\left(\sum_{i=0}^n f_i(x)\left(\sum_{j=0}^m g_j(x)\right)\right)\\ &=\sum_{i=0}^n\sum_{j=0}^m f_i(x) g_j(x)\\ &=\sum_{i=0}^n\sum_{j=0}^m f[i]g[j]x^{ij} \end{aligned}

除法运算\乘法逆元

设有一个生成函数 f(x)f(x)，定义 f(x)f(x) 的乘法逆元是另一个生成函数 g(x)g(x)，满足
f(x)g(x)=1f(x)g(x)=1
解释一下，f(x)f(x) 与 g(x)g(x) 的乘积是一个新的生成函数，记这个生成函数为 h(x)h(x)，则 h(x)h(x) 满足 h[0]=1h[0]=1 且 h[i]=0 (i≥1)h[i]=0\ (i\ge 1)。
f(x)f(x) 的乘法逆元简称乘逆，记作 1f(x)\displaystyle \frac{1}{f(x)} 或 f(x)−1f(x)^{-1}、f−1(x)f^{-1}(x)。
光定义了乘法逆元还不行，还要探讨一下它是否存在，注意到
1=h[0]=f[0]g[0]1=h[0]=f[0]g[0]
于是 g(x)g(x) 存在的一个必要条件是 f[0]≠0f[0]\neq 0，反之当 f[0]≠0f[0]\neq 0 时必有 g[0]=1f[0]\displaystyle g[0]={1\over f[0]}。
我们还可以证明，f[0]≠0f[0]\neq 0 还是 g(x)g(x) 存在的充分条件，方法是利用递推公式构造出一个 g(x)g(x) 来。
注意到 ∀i∈N+\forall i\in\mathbb{N}^+ 有
h[i]=0∑j=0ig[j]f[i−j]=0g[i]=−1f[0]∑j=0i−1g[j]f[i−j]\begin{aligned} &h[i]=0\\ &\sum_{j=0}^{i}g[j]f[i-j]=0\\ &g[i]=-\frac{1}{f[0]}\sum_{j=0}^{i-1}g[j]f[i-j] \end{aligned}
于是我们找到了一个关于 g[i]g[i] 的递推公式，也就构造出了 g(x)g(x)，且这个构造方法产生的 g(x)g(x) 唯一。
所以对于某生成函数 f(x)f(x)，1f(x)\displaystyle {1\over f(x)} 存在的充要条件是 f[0]≠0f[0]\neq 0，若 f(x)f(x) 的乘逆存在，则 1f(x)\displaystyle {1\over f(x)} 唯一。
例1
设有生成函数 f(x)=1−xf(x)=1-x，请求出它的乘法逆元。
解
f[0]=1≠0f[0]=1\neq 0，于是 f(x)f(x) 有乘法逆元，记作 g(x)g(x)，于是 g[0]=1f[0]=1\displaystyle g[0]={1\over f[0]}=1。
∀i∈N+\forall i\in\mathbb{N}^+，有
g[i]=−1f[0]∑j=0i−1g[j]f[i−j]=−∑j=i−1i−1g[j]f[i−j]=−g[i−1]f[1]=g[i−1]\begin{aligned} g[i]&=-\frac{1}{f[0]}\sum_{j=0}^{i-1}g[j]f[i-j]\\ &=-\sum_{j=i-1}^{i-1}g[j]f[i-j]\\ &=-g[i-1]f[1]\\ &=g[i-1] \end{aligned}
其中利用了 f(x)f(x) 的 22 次以上的项系数均为 00，且 f[0]=1, f[1]=−1f[0]=1,\ f[1]=-1 的性质。
由上面的递推式可以看出 g(x)g(x) 的每一项系数都相同，等于 g[0]=1g[0]=1，于是
1f(x)=g(x)=∑i=0∞xi\frac{1}{f(x)}=g(x)=\sum_{i=0}^{\infty}x^i
也就是
11−x=∑i=0∞xi\frac{1}{1-x}=\sum_{i=0}^{\infty}x^i
这也是 oiers 喜闻乐见的式子。
设 f(x)f(x) 与 g(x)g(x) 两个存在乘法逆元的多项式，求证
1f(x)g(x)=1f(x)⋅1g(x)\frac{1}{f(x)g(x)}=\frac{1}{f(x)}\cdot \frac{1}{g(x)}
证明
根据生成函数乘法的交换律与结合律有
1f(x)⋅1g(x)⋅f(x)g(x)=(1f(x)⋅f(x))⋅(1g(x)⋅g(x))=1⋅1=1\frac{1}{f(x)}\cdot \frac{1}{g(x)}\cdot f(x)g(x)=\left(\frac{1}{f(x)}\cdot f(x)\right)\cdot \left(\frac{1}{g(x)}\cdot g(x)\right)=1\cdot 1=1
由生成函数乘法逆元的定义知
1f(x)⋅1g(x)=1f(x)g(x)\frac{1}{f(x)}\cdot \frac{1}{g(x)}=\frac{1}{f(x)g(x)}
这个性质说明了乘逆运算与乘法运算可交换次序。
例2
∀n∈N\forall n\in\mathbb{N}，求证
1(1−x)n+1=∑k=0∞(n+kn)xk\frac{1}{(1-x)^{n+1}}=\sum_{k=0}^\infty{n +k\choose n}x^k
证明
我们使用数学归纳法，当 n=0n=0 的情况已经证明过了。
现在通过 nn 证明 n+1n+1 时的结论也成立。
1(1−x)n+2=11−x⋅1(1−x)n+1=(∑i=0∞xi)⋅(∑j=0∞(n+jn)xj)=∑k=0∞(∑i=0k(n+in))xk=∑k=0∞(n+1+kn+1)xk\begin{aligned} \frac{1}{(1-x)^{n+2}}&=\frac{1}{1-x}\cdot\frac{1}{(1-x)^{n+1}}\\ &=\left(\sum_{i=0}^\infty x^i\right)\cdot\left(\sum_{j=0}^\infty{n+j\choose n}x^j\right)\\ &=\sum_{k=0}^\infty\left(\sum_{i=0}^{k}{n+i\choose n}\right)x^k\\&=\sum_{k=0}^\infty{n+1+k\choose n+1}x^k \end{aligned}
其中用到了关于组合数的一个公式
∑i=0k(n+in)=(n+1+kn+1)\sum_{i=0}^{k}{n+i\choose n}={n+1+k\choose n+1}
证明仍然用数学归纳法。
当 k=0k=0 时结论显然成立。
现在假设对于 k−1 (k≥1)k-1\ (k\ge 1) 结论是成立的，于是有
(n+1+kn+1)=(n+kn)+(n+kn+1)=(n+kn)+(n+1+(k−1)n+1)=(n+kn)+∑i=0k−1(n+in)=∑i=0k(n+in)\begin{aligned} {n+1+k\choose n+1}&={n+k\choose n}+{n+k\choose n+1}\\ &={n+k\choose n}+{n+1+(k-1)\choose n+1}\\ &={n+k\choose n}+\sum_{i=0}^{k-1}{n+i\choose n}\\ &=\sum_{i=0}^{k}{n+i\choose n} \end{aligned}
证毕。
例3
设有生成函数 f(x)=1+xf(x)=1+x，∀n∈N\forall n\in\mathbb{N} 有
fn(x)=∑k=0n(nk)xkf^n(x)=\sum_{k=0}^{n}{n\choose k}x^k
这是二项式定理的直接推论。
若 g(x)g(x) 有乘法逆元，则 f(x)f(x) 除 g(x)g(x) 的结果记作 f(x)g(x)\displaystyle\frac{f(x)}{g(x)}，定义为
f(x)g(x)=f(x)⋅1g(x)\frac{f(x)}{g(x)}=f(x)\cdot\frac{1}{g(x)}
令 h(x)=f(x)g(x)\displaystyle h(x)=\frac{f(x)}{g(x)}，则除法的含义是 h(x)h(x) 与 g(x)g(x) 的乘积结果为 f(x)f(x)。

生成函数取模运算

对于生成函数 f(x)f(x)，设它的前 n (n≥1)n\ (n\ge 1) 项（次数 ≤n−1\le n-1 的项）构成的有限生成函数是 f∗(x)f_*(x)，定义 f(x)f(x) 对 xnx^n 取模的结果为 f∗(x)f_*(x)，记作
f∗(x)=f(x)%xnf_*(x)=f(x)\% x^n
简而言之，生成函数对 xnx^n 取模就是只保留前 nn 项，忽略掉 nn 次以上的项。
比如当 f(x)=11−x\displaystyle f(x)=\frac{1}{1-x} 时，f(x)%x5=1+x+x2+x3+x4f(x)\%x^5=1+x+x^2+x^3+x^4。
一般而言，若关于生成函数的等式是在取 xnx^n 模的意义下，即等式两边的前 nn 项对应相等，则记作
leftside=rightside(modxn)leftside=rightside\pmod{x^n}
容易验证生成函数取模运算满足以下几种性质。
(1)(1) 与加法运算可交换次序。
(f(x)+g(x))%xn=f(x)%xn+g(x)%xn(f(x)+g(x)) \%x^n=f(x)\%x^n+g(x)\%x^n
(2)(2) 与乘法运算可交换次序。
(f(x)⋅g(x))%xn=((f(x)%xn)⋅(g(x)%xn))%xn(f(x)\cdot g(x))\%x^n=((f(x)\%x^n)\cdot(g(x)\%x^n))\%x^n
(3)(3) 与除法运算可交换次序。
1f(x)%xn=1f(x)%xn%xn\frac{1}{f(x)}\%x^n=\frac{1}{f(x)\% x^n}\% x^n
证明
只证 (3)(3)。
记 f(x)f(x) 的乘逆为 g(x)g(x)，注意到构造乘法逆元的递推公式中，得到 g(x)g(x) 的前 nn 项只需要 f(x)f(x) 的前 nn 项。
于是 1f(x)%xn\displaystyle \frac{1}{f(x)\%x^n} 的前 nn 项就是 g(x)g(x) 的前 nn 项。
若记 f∗(x),g∗(x)f_*(x),g_*(x) 分别为 f(x)f(x) 和 g(x)g(x) 的前 nn 项，则一定有
f∗(x)⋅g∗(x)=1(modxn)f_*(x)\cdot g_*(x)=1\pmod{x^n}

极限运算

设 {fn(x)} (n∈N)\{f_n(x)\}\ (n\in\mathbb{N}) 是一个生成函数序列，定义生成函数序列的极限是一个生成函数 f(x)f(x)，记作
f(x)=lim⁡n→∞fn(x)f(x)=\lim_{n\to\infty}f_n(x)
满足 ∀m∈N, ∃N∈N\forall m\in\mathbb{N},\ \exists N\in\mathbb{N}，使得任取 k∈[0,m]∧Nk\in[0,m]\wedge\mathbb{N}，∀n>N \forall n>N 都有 fn(x)f_n(x) 的第 kk 次项系数相等。
也即当 nn 充分大的时候 f(x)f(x) 的前 m+1m+1 项系数都固定了下来。
生成函数序列极限存在还有另一种等价的定义。
f(x)f(x) 是 {fn(x)}\{f_n(x)\} 的极限等价于 ∀m∈N, ∃N∈N+\forall m\in\mathbb{N},\ \exists N\in\mathbb{N}^+，使得 ∀n>N\forall n>N 都有
fn(x)%xm=f(x)%xmf_n(x)\%x^m=f(x)\%x^m
这个对生成函数极限的定义与数学分析中对极限的定义不同，不沿用数学分析中对极限的定义是因为这个极限定义在生成函数这个代数结构中更优良。
生成函数序列的极限不一定存在，若它的极限存在，也称该生成函数序列极限收敛或称它是收敛的生成函数序列。
首先需要阐明一些关于生成函数序列极限的性质。
(1)(1) 极限运算与加法运算可交换次序。
设 {fn(x)}, {gn(x)}\{f_n(x)\},\ \{g_n(x)\} 是两个收敛的生成函数序列，它们的极限分别为 f(x),g(x)f(x),g(x)，则有 {fn(x)+gn(x)}\{f_n(x)+g_n(x)\} 的极限收敛，并且满足
f(x)+g(x)=lim⁡n→∞(fn(x)+gn(x))f(x)+g(x)=\lim_{n\to\infty}(f_n(x)+g_n(x))
证明
由极限的定义知 ∀m∈N\forall m\in\mathbb{N}。
∃N1∈N\exists N_1\in\mathbb{N}，使得 ∀n>N1\forall n>N_1 都有 fn(x)%xm=f(x)%xmf_n(x)\%x^m=f(x)\%x^m。
同时 ∃N2∈N\exist N_2\in\mathbb{N}，使得 ∀n>N2\forall n>N_2 都有 gn(x)%xm=g(x)%xmg_n(x)\%x^m=g(x)\%x^m。
取 N=max⁡{N1,N2}N=\max\{N_1,N_2\}，则 ∀n>N\forall n>N 有 fn(x)%xm=f(x)%xm, gn(x)%xm=g(x)%xmf_n(x)\%x^m=f(x)\%x^m,\ g_n(x)\%x^m=g(x)\%x^m。
由生成函数取模运算与加法运算交换可次序得
(f(x)+g(x))%xm=f(x)%xm+g(x)%xm=fn(x)%xm+gn%xm=(fn(x)+gn(x))%xm(f(x)+g(x))\%x^m=f(x)\%x^m+g(x)\%x^m=f_n(x)\%x^m+g_n\%x^m=(f_n(x)+g_n(x))\%x^m
根据生成函数序列极限的定义可知
lim⁡n→∞(fn(x)+gn(x))=f(x)+g(x)\lim_{n\to\infty}(f_n(x)+g_n(x))=f(x)+g(x)
(2)(2) 极限运算与乘法运算可交换次序。
设 {fn(x)}, {gn(x)}\{f_n(x)\},\ \{g_n(x)\} 是两个收敛的生成函数序列，它们的极限分别为 f(x),g(x)f(x),g(x)，则有 {fn(x)⋅gn(x)}\{f_n(x)\cdot g_n(x)\} 的极限收敛，并且满足
f(x)⋅g(x)=lim⁡n→∞fn(x)⋅gn(x)f(x)\cdot g(x)=\lim_{n\to\infty}f_n(x)\cdot g_n(x)
证明
由极限的定义知
∀m∈N, ∃N∈N\forall m\in\mathbb{N},\ \exists N\in\mathbb{N}，使得 ∀n>N\forall n>N 都有 fn(x)%xm=f(x)%xm, gn(x)%xm=g(x)%xmf_n(x)\%x^m=f(x)\%x^m,\ g_n(x)\%x^m=g(x)\%x^m。
由生成函数取模运算可与乘法运算交换次序得
(f(x)⋅g(x))%xm=(f(x)%xm⋅g(x)%xm)%xm=(fn(x)%xm⋅gn(x)%xm)%xm=(fn(x)⋅gn(x))%xm\begin{aligned} (f(x)\cdot g(x))\%x^m&=(f(x)\%x^m\cdot g(x)\%x^m)\%x^m\\ &=(f_n(x)\%x^m\cdot g_n(x)\%x^m)\%x^m\\ &=(f_n(x)\cdot g_n(x))\%x^m \end{aligned}
于是
lim⁡n→∞fn(x)⋅gn(x)=f(x)⋅g(x)\lim_{n\to\infty}f_n(x)\cdot g_n(x)=f(x)\cdot g(x)
(3)(3) 极限运算与除法运算可交换次序。
设 {fn(x)},{gn(x)}\{f_n(x)\},\{g_n(x)\} 是两个收敛的生成函数序列，它们的极限分别为 f(x),g(x)f(x),g(x)，其中 gn(x)g_n(x) 有乘逆，则有
f(x)g(x)=lim⁡n→∞fn(x)gn(x)\frac{f(x)}{g(x)}=\lim_{n\to\infty}\frac{f_n(x)}{g_n(x)}
证明
首先 ∀n∈N\forall n\in\mathbb{N} 均有 gn[0]≠0g_n[0]\neq 0，gn(x)g_n(x) 的极限 g(x)g(x) 也一定满足 g[0]≠0g[0]\neq 0，所以 g(x)g(x) 有乘逆，等式的左边有意义。
∀m∈N, ∃N∈N\forall m\in\mathbb{N},\ \exists N\in\mathbb{N}，使得 ∀n>N\forall n>N 都有 fn(x)%xm=f(x)%xm, gn(x)%xm=g(x)%xmf_n(x)\%x^m=f(x)\%x^m,\ g_n(x)\%x^m=g(x)\%x^m。
由生成函数取模运算可与除法运算交换次序得
f(x)g(x)%xm=f(x)%xmg(x)%xm%xm=fn(x)%xmgn(x)%xm%xm=fn(x)gn(x)%xm\frac{f(x)}{g(x)}\%x^m=\frac{f(x)\%x^m}{g(x)\%x^m}\%x^m=\frac{f_n(x)\%x^m}{g_n(x)\%x^m}\%x^m=\frac{f_n(x)}{g_n(x)}\%x^m
于是
lim⁡n→∞fn(x)gn(x)=f(x)g(x)\lim_{n\to\infty}\frac{f_n(x)}{g_n(x)}=\frac{f(x)}{g(x)}
(4)(4) 极限运算可与取模运算交换次序。
（证明待补，较容易）
生成函数的本质是序列，∑∞\displaystyle \sum^\infty 只是对序列的一种表达方式，但在定义好了关于极限运算后，终于可以解释为什么要用无穷求和的符号 ∑∞\displaystyle \sum^\infty 来表示生成函数。
在此之前先定义什么是对生成函数的无穷项求和。
与在数学分析中分析数字序列的无穷项求和一样，我们同样用部分和序列的极限来定义无穷项求和。
对于一个生成函数序列 F={fn(x)}F=\{f_n(x)\}，定义它的部分和序列也是个生成函数序列 S={sn(x)}S=\{s_n(x)\}，满足
sn(x)=∑i=0nfi(x)s_n(x)=\sum_{i=0}^{n}f_i(x)
即 sn(x)s_n(x) 是序列 FF 的前 n+1n+1 项和（从 00 开始计数）。
若 lim⁡n→∞sn(x)\displaystyle\lim_{n\to\infty}s_n(x) 存在，记为 s(x)s(x)，则称 s(x)s(x) 为生成函数序列 FF 的无穷项求和（或称无穷级数），记为
s(x)=∑i=0∞fi(x)s(x)=\sum_{i=0}^\infty f_i(x)
注意这里的 ∑∞\displaystyle \sum^\infty 记号不再指对序列的表达方式，而是货真价实的无穷项求和。
根据生成函数极限的定义，lim⁡n→∞sn(x)\displaystyle \lim_{n\to\infty} s_n(x) 存在的充要条件是 ∀m∈N+, ∃N∈N\forall m\in\mathbb{N}^+,\ \exists N\in\mathbb{N} 使得当 n>Nn>N 时就有
sn(x)%xm=s(x)%xms_n(x)\%x^m=s(x)\%x^m
就是说 s(x)s(x) 的前 mm 项就固定下来了。
所以 ∀n>N\forall n>N 有 fn(x)%xm=0f_n(x)\% x^m=0，也就是说在 fN(x)f_N(x) 之后的 fn(x)f_n(x)，不再对 s(x)s(x) 的前 mm 项有影响，所以 fN(x)f_N(x) 之后的 fn(x)f_n(x) 的前 mm 项为 00。
所以 ∑i=0∞fi(x)\displaystyle \sum_{i=0}^\infty f_i(x) 存在等价于，∀m∈N+, ∃N∈N\forall m\in\mathbb{N}^+,\ \exists N\in\mathbb{N}，使得 ∀n>N\forall n>N 均有 fn(x)%xm=0f_n(x)\%x^m=0。
回到一开始的问题：为什么用 ∑∞\displaystyle \sum^\infty 来表示生成函数？
设有某序列 {ai}\{a_i\}，以及生成函数序列 F={fi(x)}F=\{f_i(x)\} 满足 fi(x)=aixif_i(x)=a_ix^i。
令 FF 的部分和序列为 S={si(x)}S=\{s_i(x)\}，于是
sn(x)=∑i=0nfi(x)=∑i=0naixi\begin{aligned} s_n(x)&=\sum_{i=0}^{n}f_i(x)\\ &=\sum_{i=0}^na_ix^i \end{aligned}
作生成函数 f(x)f(x)，满足 f[i]=aif[i]=a_i。
∀m∈N+\forall m\in\mathbb{N}^+，取 N=m−1N=m-1，则 ∀n>N\forall n>N 均有 fn(x)%xm=0f_n(x)\%x^m=0。
根据极限定义可知 SS 的极限存在，且 ∀i∈N\forall i\in\mathbb{N} 均有
[xi]s(x)=lim⁡n→∞[xi]sn(x)=ai=f[i][x^i]s(x)=\lim_{n\to\infty} [x^i]s_n(x)=a_i=f[i]
所以 SS 的极限是 f(x)f(x)。
故 FF 的无穷求和就是
∑i=0∞fi(x)=lim⁡n→∞sn(x)=f(x)\sum_{i=0}^\infty f_i(x)=\lim_{n\to\infty}s_n(x)=f(x)
于是有
∑i=0∞fi(x)=∑i=0∞f[i]xi\sum_{i=0}^\infty f_i(x)=\sum_{i=0}^\infty f[i]x^i
至此，我们可以发现等式左边的无穷项求和与等式右边的对序列的表达方式其实是等价的。
f(x)=∑i=0∞f[i]xif(x)=\sum_{i=0}^\infty f[i]x^i
从现在开始，上面这个式子既可以解读为序列 {f[i]}\{f[i]\} 的一种表达方式，又可以解读为对生成函数序列 {fi(x)=f[i]xi}\{f_i(x)=f[i]x^i\} 的无穷项求和。
生成函数的无穷求和求和也满足线性性质（称为无穷级数的线性性质）。
设有一组生成函数的序列 Fj={fi,j(x)}F_j=\{f_{i,j}(x)\}，满足 FjF_j 的无穷级数存在，即 ∀j\forall j 有
∑i∞fi,j(x)\sum_i^\infty f_{i,j}(x)
存在。
再设 aj(x)a_j(x) 是一组有限生成函数，则有
∑jnaj(x)∑i∞fi,j(x)=∑i∞∑jnaj(x)fi,j(x)\sum_j^na_j(x)\sum^\infty_{i} f_{i,j}(x)=\sum_i^\infty \sum_j^na_j(x)f_{i,j}(x)
证明
∑jnaj(x)∑i∞fi,j(x)=lim⁡m→∞∑jnaj(x)∑imfi,j(x)=lim⁡m→∞∑im∑jnaj(x)fi,j(x)\begin{aligned} \sum_j^na_j(x)\sum^\infty_{i} f_{i,j}(x)&=\lim_{m\to\infty}\sum_j^na_j(x)\sum^m_{i} f_{i,j}(x)\\ &=\lim_{m\to\infty}\sum^m_{i}\sum_j^na_j(x) f_{i,j}(x)\\ \end{aligned}
然后
∀m∈N+\forall m\in\mathbb{N}^+
∀j\forall j，因为 FjF_j 有极限，所以 ∃Nj\exists N_j 使得 ∀i>Nj\forall i>N_j，有 fi,j(x)%xm=0f_{i,j}(x)\%x^m=0。
取 N=max⁡j{Nj}\displaystyle N=\max_j\{N_j\}，则 ∀i>N\forall i>N，∀j\forall j 均有 fi,j(x)%xm=0f_{i,j}(x)\%x^m=0。
于是
(∑jnaj(x)fi,j(x))%xm=(∑jnaj(x)(fi,j(x)%xm))%xm=(∑jnaj(x)⋅0)%xm=0\begin{aligned} \left(\sum_j^na_j(x)f_{i,j}(x)\right)\%x^m&=\left(\sum_j^na_j(x)(f_{i,j}(x)\% x^m)\right)\% x^m\\ &=\left(\sum_j^na_j(x)\cdot 0\right)\% x^m=0 \end{aligned}
于是 lim⁡m→∞∑im∑jnaj(x)fi,j(x)\displaystyle \lim_{m\to\infty}\sum_i^m \sum_j^na_j(x)f_{i,j}(x) 存在，为 ∑i∞∑jnaj(x)fi,j(x)\displaystyle \sum_i^\infty \sum_j^na_j(x)f_{i,j}(x)。
同样的我们可以定义关于生成函数的无穷乘积。
（待补充）

复合运算

生成函数的名字里带“函数”两个字，说明它本身带有函数运算的性质，也就是生成函数的复合运算，只有建立了生成函数复合运算的相关理论，才能让生成函数发挥更大的威力。
设 f(x),g(x)f(x),g(x) 是两个生成函数，定义它们复合运算为一个对生成函数的无穷项求和，记其结果为 h(x)h(x)，则
h(x)=lim⁡n→∞∑i=0nf[i]gi(x)h(x)=\lim_{n\to\infty}\sum_{i=0}^{n}f[i]g^i(x)
或者
h(x)=∑i=0∞f[i]gi(x)h(x)=\sum_{i=0}^{\infty}f[i]g^i(x)
h(x)h(x) 也记作 f(g(x))f(g(x)) 或 h=f∘gh=f\circ g。
来看看这个关于生成函数的无穷级数在什么情况下收敛吧。
若 f(g(x))f(g(x)) 存在，则一定至少满足下面两种情况其中之一。
  1. f(x)f(x) 是有限多项式。
  2. g(x)g(x) 满足 g[0]=0g[0]=0。
第一条就不需要解释了吧，只解释第二条。
若 f(x)f(x) 是无穷多项式，且 g[0]≠0g[0]\neq 0，则 ∀n∈N\forall n\in\mathbb{N} 均 ∃i>n\exists i>n 使得 [x0]f[i]≠0[x^0]f[i]\neq 0，注意到 [x0]gi(x)≠0[x^0]g^i(x)\neq 0，则 [x0]f[i]gi(x)≠0[x^0]f[i]g^i(x)\neq 0。
于是 ∀m∈N+\forall m\in\mathbb{N}^+ 均有 f[i]gi(x)%xm≠0f[i]g^i(x)\%x^m\neq 0，所以对 f[i]gi(x)f[i]g^i(x) 的无穷求和的极限一定不存在。
反之当两者情况的其中之一满足时，f(g(x))f(g(x)) 一定存在且唯一。
与普通的函数的复合运算类似，生成函数的复合运算也可以与加法运算、乘法运算、除法运算交换，以下我们一一证明。
(1)(1) 复合运算可与加法运算交换次序，即
(f+g)(h(x))=f(h(x))+g(h(x))(f+g)(h(x))=f(h(x))+g(h(x))
证明
f(h(x))+g(h(x))=∑i=0∞f[i]hi(x)+∑i=0∞g[i]hi(x)=∑i=0∞(f[i]+g[i])hi(x)=(f+g)(h(x))\begin{aligned} f(h(x))+g(h(x))&=\sum_{i=0}^\infty f[i]h^i(x)+\sum_{i=0}^\infty g[i]h^i(x)\\ &=\sum_{i=0}^\infty(f[i]+g[i])h^i(x)\\ &=(f+g)(h(x))\\ \end{aligned}
其中利用了级数运算的线性性质。
(2)(2) 复合运算与乘法运算可交换次序。
(f⋅g)(h(x))=f(h(x))⋅g(h(x))(f\cdot g)(h(x))=f(h(x))\cdot g(h(x))
证明
若 f(x)f(x) 与 g(x)g(x) 为有限多项式，根据无穷级数的线性性质，则结论当然成立。
否则，要使等式两边有意义则必须满足 h[0]=0h[0]=0。
∀n∈N\forall n\in\mathbb{N} 我们证明 [xn](f⋅g)(h(x))=[xn]f(h(x))⋅g(h(x))[x^n](f\cdot g)(h(x))=[x^n]f(h(x))\cdot g(h(x))。
因为 h[0]=0h[0]=0 所以 f[i]hi(x)%xn+1=0, g[i]hi(x)%xn+1=0(i>n)f[i]h^i(x)\%x^{n+1}=0,\ g[i]h^i(x)\%x^{n+1}=0\quad(i>n)。
于是
[xn]f(h(x))⋅g(h(x))=[xn](∑i=0nf[i]hi(x))⋅(∑j=0ng[j]hj(x))=[xn]∑i=0n(∑j=0if[i]g[i−j])hi(x)=[xn](f⋅g)(h(x))\begin{aligned}\\ [x^n]f(h(x))\cdot g(h(x))&=[x^n]\left(\sum_{i=0}^nf[i]h^i(x)\right)\cdot\left(\sum_{j=0}^ng[j]h^j(x)\right)\\ &=[x^n]\sum_{i=0}^n\left(\sum_{j=0}^if[i]g[i-j]\right)h^i(x)\\ &=[x^n](f\cdot g)(h(x)) \end{aligned}
(3)(3) 复合运算与乘逆运算可交换次序。
设 f(x)f(x) 存在乘逆，g(x)=1f(x)\displaystyle g(x)=\frac{1}{f(x)}，于是
g(h(x))=1f(h(x))g(h(x))=\frac{1}{f(h(x))}
证明
首先有 g⋅f=1g\cdot f=1，于是 (g⋅f)(h(x))=1(g\cdot f)(h(x))=1。
然后利用复合运算与乘法运算可交换次序
1=(g⋅f)(h(x))=g(h(x))⋅f(h(x))1=(g\cdot f)(h(x))=g(h(x))\cdot f(h(x))
所以
g(h(x))=1f(h(x))g(h(x))=\frac{1}{f(h(x))}
(4)(4) 在 g[0]=0g[0]=0 的情况下，计算 f(g(x))f(g(x)) 时复合运算可与取模运算交换次序。
记 f∗(x)=f(x)%xnf_*(x)=f(x)\% x^n，g∗(x)=g(x)%xng_*(x)=g(x)\%x^n，则有
f(g(x))=f∗(g∗(x))(modxn)f(g(x))=f_*(g_*(x))\pmod{x^n}
证明
因为 g[0]=0g[0]=0，当 i≥ni\ge n 时有 gi(x)%xn=0g^i(x)\% x^n=0，于是
f(g(x))%xn=(∑i=0n−1f[i]gi(x))%xn=(∑i=0n−1f[i]g∗i(x))%xn=f∗(g∗(x))%xn\begin{aligned} f(g(x))\% x^n&=\left(\sum_{i=0}^{n-1}f[i]g^i(x)\right)\%x^n\\ &=\left(\sum_{i=0}^{n-1}f[i]g_*^i(x)\right)\%x^n\\ &=f_*(g_*(x))\%x^n \end{aligned}
(5)(5) 对于常项为 00 一次项非 00 的生成函数，复合运算满足结合律。
设 f(x),g(x),h(x)f(x),g(x),h(x) 是三个不同的生成函数，满足 f[0]=g[0]=h[0]=0, f[1]≠0, g[1]≠0, h[1]≠0f[0]=g[0]=h[0]=0,\ f[1]\neq0,\ g[1]\neq0,\ h[1]\neq0。
证明
设 p(x)=f(g(x)), q(x)=g(h(x))p(x)=f(g(x)),\ q(x)=g(h(x))。
任取 n∈N+n\in\mathbb{N}^+，在 (modxn)\pmod{x^n} 的情况下，f(x),g(x),h(x)f(x),g(x),h(x) 均是有限多项式，有限多项式对复合运算满足结合律，于是有
p(h(x))=f(q(x))(modxn)p(h(x))=f(q(x))\pmod {x^n}
且 ∀m≥n\forall m\ge n，均满足 ∀i∈[0,n−1]∧N\forall i\in[0,n-1]\wedge\mathbb{N} 有
[xi]p(h(x))=[xi]f(q(x))(modxm)[x^i]p(h(x))=[x^i]f(q(x))\pmod{x^m}
而 nn 是任意选取的，故 ∀k∈N\forall k\in\mathbb{N}，都能找到 n>kn>k，于是 p(h(x))p(h(x)) 的前 nn 项等于 f(q(x))f(q(x)) 的前 nn 项，于是 [xk]p(h(x))=[xk]f(q(x))[x^k]p(h(x))=[x^k]f(q(x))。
也就是说随着 nn 的增大，p(h(x))p(h(x)) 与 f(q(x))f(q(x)) 前面会有越来越多的项被固定，且这些被固定的项逐一对应相等。
故对于无穷幂级数 f(x),g(x),h(x)f(x),g(x),h(x) 而言，f(g(h(x)))f(g(h(x))) 也满足结合律，即
p(h(x))=f(q(x))p(h(x))=f(q(x))
证毕。
在讨论复合运算时，不得不讨论逆元，就像定义完乘法运算后就讨论的乘法逆元一样。
设 f(x)f(x) 是某生成函数，如果存在某生成函数 g(x)g(x) 使得 g(f(x))=xg(f(x))=x，则称 g(x)g(x) 为 f(x)f(x) 的复合逆元，记作 g(x)=f−(x)g(x)=f^-(x)。
注意要将复合逆元 f−(x)f^-(x) 与乘法逆元 f−1(x)f^{-1}(x) 的记号区分开来。
容易验证 f(x)f(x) 存在复合逆元的一个必要条件是 f[0]=0,f[1]≠0f[0]=0,f[1]\neq 0，也即 f(x)f(x) 必须是一个常项为 00 且 11 次项非 00 的生成函数，它的复合逆元 f−(x)f^-(x) 若存在也一定满足 f−[0]=0,f−[1]≠0f^-[0]=0,f^-[1]\neq 0。
以下我们证明 f[0]=0,f[1]≠0f[0]=0,f[1]\neq 0 也是复合逆元存在的充分条件，并且可以通过递推的方式得到 f(x)f(x) 的复合逆元 f−(x)f^-(x)。
为了方便记 g(x)=f−(x)g(x)=f^-(x)。
根据 g(f(x))=xg(f(x))=x 可知
[x1]g(f(x))=1[xn]g(f(x))=0 (n>1)\begin{aligned} &[x^1]g(f(x))=1\\ &[x^n]g(f(x))=0\ (n>1) \end{aligned}
首先有
1=[x1]g(f(x))=g[1]f[1]1=[x^1]g(f(x))=g[1]f[1]
故
g[1]=1f[1]g[1]=\frac{1}{f[1]}
∀n>1\forall n>1，因为 f[0]=0f[0]=0，所以 fi(x)%xn+1=0 (i≥n+1)f^i(x)\%x^{n+1}=0\ (i\ge n+1)，于是关于 g[i]fi(x)g[i]f^i(x) 的求和只需要求和 i≤ni\le n 的项，也就是说
0=[xn]g(f(x))=[xn]∑i=1ng[i]fi(x)=g[n]f[1]n+[xn]∑i=1n−1g[i]fi(x)\begin{aligned} 0=[x^n]g(f(x))&=[x^n]\sum_{i=1}^{n}g[i]f^i(x)\\ &=g[n]f[1]^n+[x^n]\sum_{i=1}^{n-1}g[i]f^i(x) \end{aligned}
于是
g[n]=−1f[1]n∑i=1n−1g[i]fi[n]g[n]=-\frac{1}{f[1]^n}\sum_{i=1}^{n-1}g[i]f^i[n]
注意到等式的右边只涉及到 g[1],g[2],...,g[n−1]g[1],g[2],...,g[n-1]，于是 g(x)g(x) 的递推公式就求出来了。
根据此递推公式构造出的 g(x)g(x) 是唯一的，故 f(x)f(x) 的复合逆元也是存在且唯一的。
尽管 g(f(x))=xg(f(x))=x，但我们并不知道是否也有 f(g(x))=xf(g(x))=x，但现在我们可以证明 f(g(x))=xf(g(x))=x 也是成立的。
证明
记 ε(x)=x\varepsilon(x)=x 于是 g∘f=εg\circ f=\varepsilon。
因为 g[0]=0,g[1]≠0g[0]=0,g[1]\neq 0，可知 g(x)g(x) 存在复合逆元 g−(x)g^-(x)，g−∘g=εg^-\circ g=\varepsilon。
因为生成函数的复合运算满足结合律，于是
g=gε∘g=g(g∘f)∘g=gg∘(f∘g)=gg−∘(g∘(f∘g))=g−∘g(g−∘g)∘(f∘g)=g−∘gε∘(f∘g)=εf∘g=ε\begin{aligned} g&=g\\ \varepsilon\circ g&=g\\ (g\circ f)\circ g&=g\\ g\circ(f\circ g)&=g\\ g^-\circ(g\circ(f\circ g))&=g^-\circ g\\ (g^-\circ g)\circ(f\circ g)&=g^-\circ g\\ \varepsilon\circ(f\circ g)&=\varepsilon\\ f\circ g&=\varepsilon \end{aligned}
于是 f(g(x))=xf(g(x))=x。
这说明了 f(x)f(x) 与 f−(x)f^-(x) 互为复合逆元，f−∘f=f∘f−=εf^-\circ f=f\circ f^-=\varepsilon。
例
设 f(x)=11−x\displaystyle f(x)=\frac{1}{1-x}，则 f(x−1)f(x-1) 不存在。
如果直接将 x−1x-1 带入到 11−x\displaystyle{1\over 1-x} 里会得到 12−x\displaystyle {1\over 2-x} 的结果，然而这是错的。
f(x)f(x) 是无穷多项式，但是 [x0](x−1)≠0[x^0](x-1)\neq 0，所以下面的无穷求和是不存在的。
∑i=0∞(x−1)i\sum_{i=0}^\infty (x-1)^i
如果硬是要展开则得到
∑j=0∞xj∑i=0∞(ij)(−1)i−j\sum_{j=0}^\infty x^j\sum_{i=0}^\infty{i\choose j}(-1)^{i-j}
且不说能不能交换求和次序，即使能交换，交换后的结果也不存在。

生成函数求导运算

设生成函数 f(x)=∑i=0∞f[i]xi\displaystyle f(x)=\sum_{i=0}^\infty f[i]x^i，则它的导数记作 f′(x)f'(x)，定义为
f′(x)=∑i=0∞(i+1)f[i+1]xif'(x)=\sum_{i=0}^\infty (i+1)f[i+1]x^i
也可以是下面这种形式
f′(x)=∑i=1∞if[i]xif'(x)=\sum_{i=1}^\infty if[i]x^i
注意求导后常数项 f[0]f[0] 被丢失了。
生成函数的导数也被记作 (f(x))′(f(x))'。
在利用生成函数求递推式时，求导是一种有力的工具，在介绍生成函数导数的应用之前需要阐明一些性质。
生成函数的求导公式与数学分析中的普通函数的求导公式类似，接下来会一一证明。
(1)(1) 设 f(x),g(x)f(x),g(x) 是某两个生成函数，a,b∈Pa,b\in\mathbb{P}，则有
(af(x)+bg(x))′=af′(x)+bg′(x)(af(x)+bg(x))'=af'(x)+bg'(x)
证明
这是显然的。
(2)(2) 设 f(x),g(x)f(x),g(x) 是某两个生成函数，则有
(f(x)⋅g(x))′=f′(x)g(x)+f(x)g′(x)(f(x)\cdot g(x))'=f'(x)g(x)+f(x)g'(x)
证明
等式的左边。
(f(x)⋅g(x))′=∑i=0∞(i+1)(∑j=0i+1f[j]g[i+1−j])xi(f(x)\cdot g(x))'=\sum_{i=0}^\infty(i+1)\left(\sum_{j=0}^{i+1}f[j]g[i+1-j]\right)x^i
等式右边的第一项。
f′(x)g(x)=(∑i=0∞(i+1)f[i+1]xi)⋅(∑j=0∞g[j]xj)=∑i=0∞(∑j=0i(j+1)f[j+1]g[i−j])xi=∑i=0∞(∑j=1i+1jf[j]g[i−(j−1)])xi=∑i=0∞(∑j=0j+1jf[j]g[i+1−j])xi\begin{aligned} f'(x)g(x)&=\left(\sum_{i=0}^\infty (i+1)f[i+1]x^i\right)\cdot\left(\sum_{j=0}^\infty g[j]x^j\right)\\ &=\sum_{i=0}^\infty\left(\sum_{j=0}^i(j+1)f[j+1]g[i-j]\right)x^i\\ &=\sum_{i=0}^\infty\left(\sum_{j=1}^{i+1}jf[j]g[i-(j-1)]\right)x^i\\ &=\sum_{i=0}^\infty\left(\sum_{j=0}^{j+1}jf[j]g[i+1-j]\right)x^i\\ \end{aligned}
等式右边的第二项。
f(x)g′(x)=(∑i=0∞f[i]xi)⋅(∑j=0∞(j+1)g[j+1]xj)=∑i=0∞(∑j=0if[j+1](i+1−j)g[i+1−j])xi=∑i=0∞(∑j=0i+1f[j+1](i+1−j)g[i+1−j])xi\begin{aligned} f(x)g'(x)&=\left(\sum_{i=0}^\infty f[i]x^i\right)\cdot\left(\sum_{j=0}^\infty(j+1) g[j+1]x^j\right)\\ &=\sum_{i=0}^\infty\left(\sum_{j=0}^{i}f[j+1](i+1-j)g[i+1-j]\right)x^i\\ &=\sum_{i=0}^\infty\left(\sum_{j=0}^{i+1}f[j+1](i+1-j)g[i+1-j]\right)x^i\\ \end{aligned}
将利用无穷级数的线性性质，等式右边的两项合并后就得到等式的左边。
(3)(3) 设 f(x)f(x) 是某生成函数，n∈N+n\in\mathbb{N}^+，则有
(fn(x))′=nfn−1(x)f′(x)(f^n(x))'=nf^{n-1}(x)f'(x)
证明
使用数学归纳法。
n=1n=1 时结论显然成立。
假设对于 n−1n-1 结论成立，即有
(fn−1(x))′=(n−1)fn−2(x)f′(x)(f^{n-1}(x))'=(n-1)f^{n-2}(x)f'(x)
于是
(fn(x))′=(fn−1(x)⋅f(x))′=(fn−1(x))′f(x)+fn−1(x)f′(x)=(n−1)fn−2(x)f′(x)f(x)+fn−1(x)f′(x)=nfn−1(x)f′(x)\begin{aligned} (f^n(x))'&=(f^{n-1}(x)\cdot f(x))'\\ &=(f^{n-1}(x))'f(x)+f^{n-1}(x)f'(x)\\ &=(n-1)f^{n-2}(x)f'(x)f(x)+f^{n-1}(x)f'(x)\\ &=nf^{n-1}(x)f'(x) \end{aligned}
(4)(4) 求导运算与生成函数取模运算的次序交换满足
f′(x)%xn=(f(x)%xn+1)′f'(x)\%x^n=(f(x)\%x^{n+1})'
证明是显然的。
(5)(5) 极限运算可与求导运算交换次序。
设有收敛的生成函数序列 {fn(x)}\{f_n(x)\}，其极限为 f(x)f(x)，则有
f′(x)=lim⁡n→∞fn′(x)f'(x)=\lim_{n\to\infty}f_n'(x)
证明
由生成函数序列极限的定义可知 ∀m∈N+, ∃N∈N\forall m\in\mathbb{N}^+,\ \exists N\in\mathbb{N}，使得 ∀n>N\forall n> N 有 fn(x)=f(x)%xm+1f_n(x)=f(x)\%x^{m+1}。
于是
f′(x)%xm=(f(x)%xm+1)′=(fn(x))′%xm=fn′(x)%xmf'(x)\%x^m=(f(x)\%x^{m+1})'=(f_n(x))'\% x^m=f_n'(x)\% x^m
于是生成函数序列 {fn′(x)}\{f_n'(x)\} 收敛于 f′(x)f'(x)。
推论
生成函数的无穷求和（若存在的话）可与求导运算交换次序，即
(∑i=0∞fi(x))′=∑i=0∞fi′(x)\left(\sum_{i=0}^{\infty}f_i(x)\right)'=\sum_{i=0}^\infty f_i'(x)
(6)(6) 设 f(x),g(x)f(x),g(x) 是某两个生成函数且 f(g(x))f(g(x)) 存在，则有
(f(g(x)))′=f′(g(x))g′(x)(f(g(x)))'=f'(g(x))g'(x)
证明
根据 (4)(4) 和 (5)(5) 的结论有
(f(g(x)))′=(∑i=0∞f[i]gi(x))′=∑i=0∞(f[i]gi(x))′=∑i=1∞if[i]gi−1(x)g′(x)=g′(x)∑i=1∞if[i]gi−1(x)=f′(g(x))g′(x)\begin{aligned} (f(g(x)))'&=\left(\sum_{i=0}^\infty f[i]g^i(x)\right)'\\ &=\sum_{i=0}^\infty (f[i]g^i(x))'\\ &=\sum_{i=1}^\infty if[i]g^{i-1}(x)g'(x)\\ &=g'(x)\sum_{i=1}^\infty if[i]g^{i-1}(x)\\ &=f'(g(x))g'(x) \end{aligned}
(7)(7) 设 f(x)f(x) 是一个有乘逆的生成函数，则有
(1f(x))′=−f′(x)f2(x)\left(\frac{1}{f(x)}\right)'=-\frac{f'(x)}{f^2(x)}
证明
首先可以证明，∀a∈P∗\forall a\in\mathbb{P}_*，有
(1a+x)′=−1(a+x)2\left(\frac{1}{a+x}\right)'=-\frac{1}{(a+x)^2}
将等式的左右两边分别展开为无穷求和即可证明。
于是
(1f(x))′=(1f[0]+(f(x)−f[0]))′=−(f[0]+(f(x)−f[0]))′(f[0]+(f(x)−f[0]))2=−f′(x)f2(x)\begin{aligned} \left(\frac{1}{f(x)}\right)'&=\left(\frac{1}{f[0]+(f(x)-f[0])}\right)'\\ &=-\frac{(f[0]+(f(x)-f[0]))'}{(f[0]+(f(x)-f[0]))^2}\\ &=-\frac{f'(x)}{f^2(x)} \end{aligned}
推论
设 f(x),g(x)f(x),g(x) 是两个生成函数，g[0]≠0g[0]\neq 0，于是有
(f(x)g(x))′=f′(x)g(x)−f(x)g′(x)g2(x)\left(\frac{f(x)}{g(x)}\right)'=\frac{f'(x)g(x)-f(x)g'(x)}{g^2(x)}
综上可以整理出以下四条求导法则。
(af(x)+bg(x))′=af′(x)+bg′(x)(f(x)g(x))′=f′(x)g(x)+f(x)g′(x)(f(x)g(x))′=f′(x)g(x)−f(x)g′(x)f2(x)f(g(x))′=f′(g(x))g′(x)\begin{aligned} (af(x)+bg(x))'&=af'(x)+bg'(x)\\ (f(x)g(x))'&=f'(x)g(x)+f(x)g'(x)\\ \left(\frac{f(x)}{g(x)}\right)'&=\frac{f'(x)g(x)-f(x)g'(x)}{f^2(x)}\\ f(g(x))'&=f'(g(x))g'(x)\\ \end{aligned}

泰勒展开公式

设 g(x)g(x) 是某生成函数，a(x),b(x)a(x),b(x) 是某生成函数，且满足 g(a(x)),g(b(x))g(a(x)),g(b(x)) 均存在。
则有
g(b(x))=∑i=0∞g(i)(a(x))(b(x)−a(x))ii!g(b(x))=\sum_{i=0}^\infty g^{(i)}(a(x))\frac{(b(x)-a(x))^i}{i!}
证明
为了表示方便将 a(x),b(x)a(x),b(x) 简写成 a,ba,b。
∑i=0∞g(i)(a)(b−a)ii!=∑i=0∞∑j=0i(ij)bjai−j(−1)i−j=∑j=0∞bj∑i=j∞(ij)ai−j(−1)i−jg(i)(a)i!(*1)\begin{aligned} \sum_{i=0}^\infty& g^{(i)}(a)\frac{(b-a)^i}{i!}\\ &=\sum_{i=0}^\infty \sum_{j=0}^i{i\choose j}b^ja^{i-j}(-1)^{i-j}\\ &=\sum_{j=0}^\infty b^j\sum_{i=j}^\infty{i\choose j}a^{i-j}(-1)^{i-j}\frac{g^{(i)}(a)}{i!}\\ \end{aligned}\tag{*1}
注意到
∑i=j∞(ij)ai−j(−1)i−jg(i)(a)i!=∑i=j∞(ij)ai−j(−1)i−j1i!∑k=i∞ki‾g[k]xk−i=∑i=j∞∑k=i∞(ij)ai−j(−1)i−j(ki)g[k]xk−i=∑k=j∞g[k]ak−j∑i=jk(ki)(ij)(−1)i−j(*2)\begin{aligned} \sum_{i=j}^\infty&{i\choose j}a^{i-j}(-1)^{i-j}\frac{g^{(i)}(a)}{i!}\\ &=\sum_{i=j}^\infty{i\choose j}a^{i-j}(-1)^{i-j}\frac{1}{i!}\sum_{k=i}^\infty k^{\underline{i}}g[k]x^{k-i}\\ &=\sum_{i=j}^\infty\sum_{k=i}^\infty{i\choose j}a^{i-j}(-1)^{i-j}{k\choose i}g[k]x^{k-i}\\ &=\sum_{k=j}^\infty g[k]a^{k-j}\sum_{i=j}^k{k\choose i}{i\choose j}(-1)^{i-j}\\ \end{aligned}\tag{*2}
因为
(ki)(ij)=(kj)(k−ji−j){k\choose i}{i\choose j}={k\choose j}{k-j\choose i-j}
于是
∑i=jk(ki)(ij)(−1)i−j=(1−1)k−j=[k=j]\sum_{i=j}^k{k\choose i}{i\choose j}(-1)^{i-j}=(1-1)^{k-j}=[k=j]
代回式 (*2)(\text{*2}) 得到
∑i=j∞(ij)ai−j(−1)i−jg(i)(a)i!=∑k=j∞g[k]ak−j[k=j]=g[j]\begin{aligned} \sum_{i=j}^\infty&{i\choose j}a^{i-j}(-1)^{i-j}\frac{g^{(i)}(a)}{i!}\\ &=\sum_{k=j}^\infty g[k]a^{k-j}[k=j]\\ &=g[j] \end{aligned}
再代回式 (*1)(\text{*1}) 得到
∑i=0∞g(i)(a)(b−a)ii!=∑j=0∞g[j]bj=g(b)\sum_{i=0}^\infty g^{(i)}(a)\frac{(b-a)^i}{i!}=\sum_{j=0}^\infty g[j]b^j=g(b)
证毕。

评论

共 58 条评论，欢迎与作者交流。

正在加载评论...