生成函数与形式幂级数

前言

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

前置知识

代数系统,群论

环是一个具有两个二元运算的代数系统。环\(\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 \]