1.1.1 生成函数与序列
目に写った景色を
虽然映在眼前的景色
世界だなんていうけど
就被称为是世界了
見えなかった景色は
但看不见的景色
間違いなくそこにあった
却也毫无疑问的就在那处
\[
\rm{Define\ \LaTeX \ Macros\ Here}
\newcommand\ag[1]{\left\langle#1\right\rangle}
\newcommand\ul[1]{\underline{#1}}
\newcommand\stirA[2]{\begin{bmatrix}#1\\ #2\end{bmatrix}}
\newcommand\stirB[2]{\begin{Bmatrix}#1\\ #2\end{Bmatrix}}
\newcommand\ul[1]{\underline{#1}}
\newcommand\dis{\operatorname{dis}}
\newcommand\edp{\operatorname{edp}}
\newcommand\deg{\operatorname{deg}}
\newcommand\pcnt{\operatorname{popcount}}
\]
引入
生成函数的想法出于一种设想：试图将计数对象组成的序列写成形式幂级数的形式，在对它对应的形式幂级数进行研究后，再用形式幂级数生成原来的计数序列。这样，一个代数式就涵盖了原来数列所有的信息，在研究的时候显得方便得多。注意区分形式幂级数与多项式的概念。
先引入形式幂级数的概念，设 \(x\) 是一个符号，而 \(\ag{a_0,a_1,a_2,\cdots, a_n\cdots}\) 是一个实数序列，那么若 \(F(x)\) 满足
\[
F(x)=\sum_{n=0}^{+\infty}a_nx^n
\]
称 \(F(x)\) 为一个以 \(x\) 为未定元的形式幂级数，而 \([x^n]F(x)=a_n\)。
之所以称其为形式幂级数而不是幂级数，因为我们并不关心其敛散性，也不关心 \(x\) 取何等的值，可以将其看作是一个占位符。
根据（多项式运算的）经验，可以定义形式幂级数的加，减，乘运算：
\[
C(n)=A(n)\pm B(n)\Longleftrightarrow \sum_{n=0}^{+\infty}c_nx^n=\qty(\sum_{n=0}^{+\infty}a_nx^n)\pm\qty(\sum_{n=0}^{+\infty}b_nx^n)
\]
而
\[
C(n)=A(n)B(n)\Longleftrightarrow \sum_{n=0}^{+\infty}c_nx^n=\qty(\sum_{n=0}^{+\infty}a_nx^n)\qty(\sum_{n=0}^{+\infty}b_nx^n)
\]
OGF
我们称序列 \(\ag{a_0,a_1,a_2,\cdots, a_n\cdots}\) 的普通生成函数（OGF）是直接对这个序列构造形式幂级数的结果，即
\[
\sum_{n=0}^{+\infty}a_nx^n
\]
这样的形式如何简化我们的计算？从一个最简单的例子，全 \(1\) 的数列 \(\ag{1,1,1,1,\cdots }\) 出发，令 \(F(x)\) 为其 OGF，则
\[
F(x)=\sum_{n=0}^{+\infty}x^n
\]
分析这个无穷求和的方法是经典的扰动法
\[
\begin{aligned}
F(x)&=1+x+x^2+x^3+\cdots\\
xF(x)&=\,\, \; \; \; \; \; x+x^2+x^3+\cdots\\
F(x)-xF(x)&=1\\
\end{aligned}
\]
从而有
\[
F(x)=\frac{1}{1-x}
\]
即 \(F(x)\) 为 \(1-x\) 的形式幂级数乘法逆。
我们指出，这样的分析要求 \(F(x)\) 是收敛的，但由于 \(x\) 是一个占位符，我们并不关心其收敛性，不妨直接假设它就是收敛的。
如果你不能接受这个看法，也可以就把这式看作是 \(\displaystyle \sum_{n=0}^{+\infty}x^n\) 的一种缩写，我们用这样的缩写式来避免每次都写出一长串式子的麻烦，并在最后求值的时候将得到的式子重新展开成无穷和式。对于这种变量和常数作有限次加减乘除，或某些重要的特殊运算（如阶乘）所得到的式子，我们称其为封闭形式。
这样的一个无穷幂级数收敛到一个封闭形式的样子很容易让我们联想到 Maclaurin 级数。于是我们立即由 Maclaurin 级数得到一系列的数列及其对应 OGF 的封闭形式：
\[
\begin{array}{ccc}
数列 &\text{OGF} &封闭形式\\
\ag{1,1,1,\cdots} &\displaystyle\sum_{k=0}^{+\infty}x^k &\dfrac{1}{1-x}\\
\ag{1,c,c^2,c^3,\cdots} &\displaystyle\sum_{k=0}^{+\infty}c^kx^k &\dfrac{1}{1-cx}\\
\ag{1,1,\frac{1}{2},\frac{1}{6},\cdots, \frac{1}{n!},\cdots} &\displaystyle\sum_{k=0}^{+\infty}\dfrac{1}{k!}x^k &\mathrm{e}^x\\
\ag{\displaystyle\binom{n}{0},\binom{n}{1},\binom{n}{2},\cdots} &\displaystyle\sum_{k=0}^{+\infty}\binom{n}{k}x^k &(1+x)^n\\
\ag{0,1,-\frac{1}{2},\frac{1}{3},-\frac{1}{4},\cdots} &\displaystyle\sum_{k=0}^{+\infty}\dfrac{(-1)^k}{k+1}x^{k+1} &\ln(1+x)\\
\ag{0,1,\frac{1}{2},\frac{1}{3},\frac{1}{4},\cdots} &\displaystyle\sum_{k=0}^{+\infty}\dfrac{1}{k+1}x^{k+1} &\ln(1-x)\\
\end{array}
\]
这些序列与生成函数之间的对应是接下来的基础。
二阶线性递推
斐波那契数列的通项
事到如今，我们还不知道这样的工具怎么简化我们的计算。我们从一个简单的例子引入：斐波那契数列。
考虑斐波那契数列 \(f_i\) 的 OGF
\[
F(x)=\sum_{i=0}^{+\infty}f_ix^i
\]
我们知道，斐波那契数列的递推公式是 \(f_{i}=f_{i-1}+f_{i-2}\)，其中 \(f_0=0,f_1=1\)，那么就有
\[
\begin{aligned}
F(x)&=0+1x+1x^2+2x^3+3x^4+\cdots\\
xF(x)&=\,\, \; \; \; \; \; 0x+1x^2+1x^3+2x^4+\cdots\\
x^2F(x)&=\,\, \; \; \; \; \; \,\, \; \; \; \; \;\, \, \; 0x^2+1x^3+1x^4+\cdots \\
\end{aligned}
\]
所以是
\[
F(x)=xF(x)+x^2F(x)+x
\]
得到的是 \(F(x)=\dfrac{x}{1-x-x^2}\)。
但是这有什么用？考虑通过一些手段反向得到它的通项。
尝试把 \(F(x)\) 分解成若干个形如 \(\dfrac{1}{1-cx^k}\) 的分式之和，设 \(x_1,x_2,a,b\) 使得
\[
\frac{x}{1-x-x^2}=\frac{x}{(x-x_1)(x-x_2)}=\frac{a}{x-x_1}+\frac{b}{x-x_2}
\]
可以解得 \(x_1=\frac{-\sqrt 5-1}{2},x_2=\frac{\sqrt 5-1}{2}\)
再考虑
\[
\frac{x}{(x-x_1)(x-x_2)}=\frac{a}{x-x_1}+\frac{b}{x-x_2}
\]
这说明 \(a(x-x_2)+b(x-x_1)=x\)
那么就有
\[
\begin{cases}
a+b=1\\
ax_2+bx_1=0\\
\end{cases}
\]
经过解方程可以解出
\[
a=\frac{5-\sqrt 5}{10},b=\frac{5+\sqrt 5}{10}
\]
接下来就是要计算
\[
[x^n]\qty(\frac{a}{x-x_1}+\frac{b}{x-x_2})
\]
把它变成两个 \(\frac{1}{1-cx^k}\) 的和的样子，那就是
\[
[x^n]\frac{-\frac{a}{x_1}}{1-\frac{x}{x_1}}+[x^n]\frac{-\frac{b}{x_2}}{1-\frac{x}{x_2}}
\]
等于
\[
-\qty(\dfrac{a}{x_1}\cdot \frac{1}{x_1^n})-\qty(\dfrac{b}{x_2}\cdot \frac{1}{x_2^n})
\]
经过整理即得
\[
[x^n]F(x)=\frac{\sqrt 5}{5}\qty[\qty(\frac{1+\sqrt 5}{2})^n-\qty(\frac{1-\sqrt 5}{2})^n]
\]
能不能再给力一点啊？
我们试图对一般的二阶线性递推式解出其通项公式，即我们已知 \(f_0,f_1\)，且对于 \(i\ge 2\) 有 \(f_i=af_{i-1}+bf_{i-2}\)。
有
\[
[x^n]F(x)=a\cdot [x^n]xF(x)+b\cdot [x^n]x^2F(x)
\]
加上系数补正，即
\[
F(x)=axF(x)+bx^2F(x)+(f_1-f_0)x
\]
一样有
\[
F(x)=\frac{(f_1-f_0)x}{1-ax-bx^2}
\]
我们要找到 \(\lambda_0,\lambda_1\) 使得 \((1-\lambda_0x)(1-\lambda_1x)=1-ax-bx^2\)，展开比对系数可得 \(\lambda_0\lambda_1=-b,\lambda_0+\lambda_1=a\)。
逆用韦达定理，这就是说 \(\lambda_0,\lambda_1\) 是方程 \(\lambda^2-a\lambda -b=0\) 的两根。
如果没有初始两项的系数修正，那么任意 \(\forall p,q\in\mathbb C,F(x)=\dfrac{p}{1-\lambda_0x}+\dfrac{q}{1-\lambda_1x}\) 都是一个可能的 \(\text{OGF}\)。
考虑最开始的系数修正，我们把 \(p,q\) 解出来。
\[
p(1-\lambda_1x)+q(1-\lambda_0)x=(f_1-f_0)x
\]
也就是
\[
p+q=0,-p\lambda_1-q\lambda_0=f_1-f_0
\]
从而可以解出 \(p,q\)，最后的通项即 \(f_k=p^k\lambda_0^k+q^k\lambda_1^k\)。
我们还可以进一步解决 \(k\) 阶的常系数齐次线性递推问题，不过暂时到此为止。
Catlan 数
定义 \(c_n\) 为 \(n\) 对括号组成的合法括号序列方案数，\(c_0=1\)。
那么有
\[
c_{n+1}=\sum_{i=0}^{n}c_ic_{n-i}
\]
组合意义即考虑 (x)y，枚举 \(x\) 的括号对数。
这就是说，设 \(C(x)\) 为 Catlan 数序列的 \(\text{OGF}\)，那么有
\[
[x^{k+1}]C(x)=[x^k]C^2(x)
\]
这就是说：
\[
[x^k]\qty(\frac{C(x)-1}{x})=[x^k]C^2(x)
\]
解得
\[
C(x)=\frac{1\pm \sqrt{1-4x}}{2x}
\]
无穷求和的系数敛散性
我们求出 \(C(x)\) 的两个解，但我们究竟该取哪个解？我们引入无穷求和收敛的概念：
- 一个无穷求和收敛，当且仅当对于任意大的 \(n\)，其前 \(n\) 项系数均收敛。
- 一个无穷求和的结果是无穷多项式 \(S(x)\)，当且仅当对于任意大的 \(n\)，其前 \(n\) 项系数相同。
那么来考察 \([x^0]C(x)\)，当取 \(\dfrac{1+\sqrt{1-4x}}{2x}\) 时，\([x^0]C(x)\) 为
\[
\lim_{x\rightarrow 0}\frac{1+\sqrt{1-4x}}{2x}
\]
左右极限分别为 \(-\infty,+\infty\)，此极限不存在，舍去。因为数列存在，所以必定有一根正确，\(C(x)=\dfrac{1-\sqrt{1-4x}}{2x}\)。正确性也可以自己验证一下。
通过广义二项式定理拆开根号，可以得到一个漂亮的通项：
$$
[x^n]C(x)=\dfrac{1}{n+1}\binom{2n}{n}
$$