生成函数与形式幂级数
前言
关于生成函数有很多概念模糊的地方，比如生成函数的乘法是怎么定义的，比如乘法可以换序吗？比如为什么可以把多项式变成对数函数？为什么又可以使用泰勒展开？
前置知识
代数系统，群论
环
环是一个具有两个二元运算的代数系统。环\(\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 \]