前言

关于生成函数有很多概念模糊的地方，比如生成函数的乘法是怎么定义的，比如乘法可以换序吗？比如为什么可以把多项式变成对数函数？为什么又可以使用泰勒展开？

前置知识

代数系统，群论

环

环是一个具有两个二元运算的代数系统。环$\lt R,+,\circ\gt$满足

  • $\lt R,+\gt$构成交换群， 即$+$满足封闭性、结合律、单位元、逆元、交换律

  • $\lt R,\circ\gt$构成半群， 即$\cdot$满足封闭性、结合律、单位元

  • $\circ$对$+$有分配率，即$a\circ(b+c)=a\circ b+a\circ c$

交换环

当$\circ$运算满足交换律时，这个环构成了交换环。

幂级数

每一项中都包含未知量$x$的无穷级数，是数学分析领域的概念，往往研究他的极限。

形式幂级数

每一项中都包含未知量$x$的无穷多项式，是组合数学领域的概念，往往用它研究计数问题。

概念搭建

由于笔者并未找到合适的相关资料，于是准备自己搭建一个形式幂级数体系。首先我们需要定义什么是形式幂级数。

数论幂函数

形如$f(x)=x^a ， a\in N^0$的函数， 即指数是非负整数的幂函数。

数论多项式

定义数论多项式是多个数论幂函数的线性组合的和。

无穷数论多项式定义

定义有无穷项的数论多项式为无穷数论多项式。后面为了简称，也写作无穷多项式。

为了方便表示无穷，我们可以使用累和的形式来定义一个无穷数论多项式，即
$$
\begin{aligned}
f=\sum_{i=0}^\infty f_i\cdot x^i
\end{aligned}
$$
其中$f_i$是一个关于i的函数。

定义所有无穷多项式的集合为$R$

无穷多项式的$+$运算

$f$和$g$是一个无穷多项式，定义$\begin{aligned}h=f+g=\sum_{i=0}^\infty (f_i+g_i)\cdot x^i\end{aligned}$

很明显$<R,+\gt$满足封闭性、结合律、交换律

单位元是$\begin{aligned}e=\sum_{i=0}^\infty e_i\cdot x^i\end{aligned}$满足$\forall i, e_i=0$，

$f$的逆元是$\sum_{i=0}^\infty -f_i\cdot x^i$

所以$\lt R,+\gt$构成交换群。

无穷多项式的$\circ$运算

$f$和$g$是一个无穷多项式，定义$\begin{aligned}h=f\circ g=\sum_{i=0}^\infty \sum_{a=0}^if_a\cdot g_{i-a}\cdot x^i\end{aligned}$

很明显$\lt R,\circ\gt$满足封闭性、结合律

所以$\lt R,+\gt$构成半群。

单位元是$\begin{aligned}e=\sum_{i=0}^\infty e_i\cdot x^i\end{aligned}$满足$e_i=\begin{cases}1, & \text{if $i$ is 0} \0, & \text{if $i$ is not 0}\end{cases}$，

无穷多项式环

满足分配率(懒得证明了)，$\lt,+,\circ\gt$是环

泰勒表示法（核武器）

根据无穷多项式的定义，只要确定了函数$f_i$， 无穷多项式就唯一确定了，受到泰勒展开的启发，我们给出新的表示法，函数$F(x)$的i阶导函数$F^{(i)}(x)$的在点0处的值，可以构成一个序列，我们令$f_i=\frac{F^{(i)}(0)}{i!}$,惊讶的发现我们可以通过给定函数$F$确定一个无穷多项式$f$。

推论1

泰勒表示法$F$和$G$的和就是$f+g$, 证明过程很简单

如果$H=F+G$ ，则$H^{(i)}(0)=F^{(i)}(0)+G^{(i)}(0)$, 即$h_i=f_i+g_i$

推论2

泰勒表示法$F$和$G$的积就是$f\circ g$, 证明过程很简单

如果$H=F\cdot G$, 则$H^{(i)}(0)=\sum_{j=0}^i C_j^i\cdot F^{(j)}(0)\cdot G^{(i-j)}(0)$, 即$h_i=\sum_{j=0}^i f_j\cdot g_{i-j}$,这与$\circ$运算的定义完全一样。

总结

我们直接将所有无穷多项式替换为泰勒表示法，然后乘起来，最后使用泰勒展开进行还原，不会对最终答案产生影响。

生成函数

普通型生成函数

n个没有标号的球，你要把它们分成m个有标号的盒子里面，盒子允许空

$f=1+x+x^2+x^3+…$

然后$f^n$的n次项系数就是答案。

先转为泰勒表示法$F=\frac{1}{1-x}$， 然后做幂，$F^m=(1-x)^{-m}$, 最后泰勒展开,得到n次项系数为$C_{m+n-1}^{m-1}$

一个重要的结论

$$
C_{-a}^b = (-1)^b C_{a+b-1}^b
$$