生成函数与形式幂级数

发表于 2021-05-08 分类于 ACM ，学习笔记，数学阅读次数： 22 本文字数： 2.2k 阅读时长 ≈ 2 分钟

next hexonext butterfly volantis yearn yilia shoka indigo apollo landscape cactus matery icarus fluid material

前言

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

前置知识

代数系统，群论

环

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

$< R, + >$ 构成交换群，即 $+$ 满足封闭性、结合律、单位元、逆元、交换律
$< R, \circ >$ 构成半群，即 $\cdot$ 满足封闭性、结合律、单位元
$\circ$ 对 $+$ 有分配率，即 $a \circ (b + c) = a \circ b + a \circ c$

交换环

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

幂级数

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

形式幂级数

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

概念搭建

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

数论幂函数

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

数论多项式

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

无穷数论多项式定义

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

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

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

无穷多项式的 $+$ 运算

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

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

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

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

所以 $< R, + >$ 构成交换群。

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

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

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

所以 $< R, + >$ 构成半群。

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

无穷多项式环

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

泰勒表示法（核武器）

根据无穷多项式的定义，只要确定了函数 $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}$

前言