Contents
形式幂级数
定义
设 $x$ 是一个符号，$a_i$ 是实数，存在 $A(x)$ 使得
$$
A(x) = a_0 + a_1 x + a_2 x^2 + \cdots + a_n x^n = \sum_{n=0}^{\infty} a_n x^n
$$
则称 $A(x) = \sum_{n=0}^{\infty} a_n x^n$ 为以 $x$ 为未定元的一个形式幂级数，形式幂级数并不关注具体的值，因此也不需要考虑收敛性
序列 $[1, 1, 1, 1, 1, \cdots]$ 的形式幂级数即为
$$
A(x) = 1 + x + x^2 + x^3 + \cdots + x^n
$$
泰勒展开
泰勒公式可以描述一个函数在一个顶点附近的取值
设 $n$ 是一个正整数，如果定义在一个包含 $a$ 的区间上的函数 $f$ 在 $a$ 点处 $n+1$ 次可导，那么对于这个区间上的任意 $x$，都有
$$
f(x) = f(a) + \frac{f'(a)}{1!} (x-a) + \frac{f^{(2)}(a)}{2!}(x-a)^2 + \cdots + \frac{f^{(n)}(a)}{n!} (x-a)^n + R_n(x)
$$
其中的多项式称为函数在 $a$ 处的泰勒展开式，剩余的 $R_n(x)$ 是泰勒公式的余项，是 $(x-a)^n$ 的高阶无穷小
麦克劳林展开
麦克劳林展开是函数在 $0$ 处的泰勒展开
$$
f(x) = f(0) + \frac{f'(0)}{1!} x + \frac{f^{(2)}(0)}{2!}x^2 + \cdots + \frac{f^{(n)}(0)}{n!} x^n + R_n(x)
$$
这和我们的形式幂级数定义是一致的，在 $lim_{n \rightarrow \infty}$ 时，我们认为 $R_n(x) \rightarrow 0$
因此，序列 $[1, 1, 1, 1, 1, \cdots]$ 的形式幂级数又可以被写作
$$
A(x) = \frac{1}{1-x} = 1 + x + x^2 + x^3 + \cdots + x^n
$$
证明：
$$
f(0) = 1
$$
对 $f(x)$ 求一阶导
$$
f'(x) = \frac{0 – (-1)}{(1-x)^2} = \frac{1}{(1-x)^2}
$$
对 $f(x)$ 求二阶导
$$
f^{(2)}(x) = \frac{0 – 2 \times (1 – x)}{(1-x)^4} = \frac{2}{(1-x)^3}
$$
对 $f(x)$ 求 $n$ 阶导
$$
f^{(n)}(x) = \frac{0 – n! \times (1-x)}{(1-x)^{2n}} = \frac{n!}{(1-x)^n}
$$
代入即可得证
一般生成函数 OGF
定义
一般生成函数是形如
$$
A(x) = \sum_{n=0}^{\infty}a_n x^n
$$
的生成函数
运算
加减运算
$$
F(x) \pm G(x) = \sum_{i=0}^{\infty} (f_i \pm g_i) [x^i]
$$
放缩
$$
cF(x) = \sum_{i=0}^{\infty} cf_i [x^i]
$$
乘法
$$
F(x) G(x) = \sum_{k=0}^{\infty} \sum_{i=0}^k f_i g_{k-i} [x^k]
$$
这是一个卷积运算
求导
$$
F'(x) = \sum_{k=0}^{\infty} (k+1) f_{k+1} [x^n]
$$
积分
$$
\int_0^x F(t) \mathrm{d}t = \sum_{k=0}^{\infty} [k > 0] \frac{f_{k-1}}{k} [x^k]
$$
右移
$$
x^m F(x) = \sum_{k=0}^{\infty} [k \geq m] f_{k-m} [x^k]
$$
左移
$$
\frac{F(x) – \sum_{k=0}^{m-1} f_k [x^k]}{x^m} = \sum_{k=0}^{\infty} f_{k+m} [x^k]
$$
常用形式
形式一
$$
[1, 1, 1, 1, \cdots] \Leftrightarrow \frac{1}{1-x} \\
$$
这个我们之前已经证明过了
形式二
$$
[1, 2, 3, 4, \cdots] \Leftrightarrow \frac{1}{(1-x)^2}
$$
这个我们可以看做 $\frac{1}{1-x}$ 乘上 $\frac{1}{1-x}$，即
$$
\sum_{k=0}^{\infty} \sum_{i=0}^k 1 [x^k] = \sum_{k=0}^{\infty} k [x^k]
$$
形式三
$$
[1, -1, 1, -1, \cdots] \Leftrightarrow \frac{1}{1+x}
$$
形式四
$$
[1, a, a^2, a^3 \cdots] \Leftrightarrow \frac{1}{1-ax}
$$
因为
$$
F(cx) = \sum_{k=0}^{\infty} c^k f_k [x^k]
$$
形式五
我们来考虑
$$
\frac{1}{(1-x)^m}
$$
它代表什么数列，我们可以得到
$$
\frac{1}{(1-x)^m} = \prod_{i=1}^m \frac{1}{1-x} = (1 + x + x^2 + \cdots + x^n)^m
$$
那么第 $[x^k]$ 项的系数就是非负整数不定方程
$$
f_1 + f_2 + f_3 + \cdots +f_m = k
$$
解的个数，也就是 $f_m = {m+k-1 \choose m-1}$，因此
$$
\frac{1}{(1-x)^m} = \sum_{k=0}^n {m+k-1 \choose m-1} [x^k]
$$
实际上，我们通过这个方法，得到了
$$
(1-x)^{-m}
$$
的二项式展开
形式六
$$
\frac{1}{(1-ax)^m} = \sum_{k=0}^n a^k {m + k – 1 \choose m – 1} [x^k]
$$
指数生成函数 EGF
定义
指数生成函数是形如
$$
A(x) = \sum_{n=0}^{\infty} \frac{a_n}{n!} x^n
$$
的生成函数
运算
加法
$$
F(x) \pm G(x) = \sum_{k=0}^{\infty} (f_i \pm g_i) \left[ \frac{x^k}{k!} \right]
$$
放缩
$$
cF(x) = \sum_{k=0}^{\infty} cf_i \left[ \frac{x^k}{k!} \right]
$$
乘法
$$
\begin{aligned}
F(x)G(x) & = \sum_{k=0}^{\infty} \sum_{i=0}^k \left( \frac{f_i}{i!} \times \frac{g_{k-i}}{(k-i)!} \right) [x^k] \\
& = \sum_{k=0}^{\infty} \sum_{i=0}^k \left( \frac{f_i}{i!} \times \frac{g_{k-i}}{(k-i)!} \times k!\right) \left[\frac{x^k}{k!} \right] \\
& = \sum_{k=0}^{\infty} \sum_{i=0}^k \left( f_i \times g_{k-i} \times \frac{k!}{i!(k-i)!}\right) \left[ \frac{x^k}{k!} \right] \\
& = \sum_{k=0}^{\infty} \sum_{i=0}^k \left( f_i \times g_{k-i} \times {k \choose i}\right) \left[ \frac{x^k}{k!} \right]
\end{aligned}
$$
求导
$$
F'(x) = \sum_{k=0}^{\infty} f_{k+1} \left[ \frac{x^k}{k!} \right]
$$
因此 $\mathrm{EGF}$ 的求导就已经起到了左移的效果
积分
$$
\int_0^x F(t) \mathrm{d}t = \sum_{k=0}^{\infty} [k > 0] f_{k-1} \left[ \frac{x^k}{k!} \right]
$$
因此 $\mathrm{EGF}$ 的积分就已经起到了右移的效果
常用形式
形式一
$$
[1, 1, 1, 1, \cdots] \Leftrightarrow e^x
$$
因为 $e^x$ 的 $n$ 阶导始终是 $e^x$，所以
$$
\begin{aligned}
F(x) & = 1 + \frac{1}{1!} x + \frac{1}{2!} x^2 + \cdots + \frac{1}{n!} x^n \\
& = 1 + 1 \left[ \frac{x}{1!} \right] + 1 \left[ \frac{x^2}{2!} \right] + \cdots + 1 \left[ \frac{x^n}{n!} \right]
\end{aligned}
$$
形式二
$$
[1, -1, 1, -1, \cdots] \Leftrightarrow e^{-x}
$$
形式三
$$
[1, 0, 1, 0, \cdots] \Leftrightarrow \frac{e^x + e^{-x}}{2}
$$
形式一加上形式二即可，那么同样的
$$
[0, 1, 0, 1, \cdots] \Leftrightarrow \frac{e^x – e^{-x}}{2}
$$