1.【理论】生成函数的引入

\[ \rm{Define\ \LaTeX \ Macros\ Here} \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\Endpos{\operatorname{Endpos}} \newcommand\Startpos{\operatorname{Startpos}} \newcommand\height{\operatorname{height}} \newcommand\SA{\operatorname{SA}} \newcommand\len{\operatorname{len}} \newcommand\chkmax{\operatorname{chkmax}} \newcommand\chkmin{\operatorname{chkmin}} \newcommand\siz{\operatorname{siz}} \newcommand\fa{\operatorname{fa}} \newcommand\LCP{\operatorname{LCP}} \newcommand\EGF{\operatorname{EGF}} \newcommand\OGF{\operatorname{OGF}} \newcommand\bd{\operatorname{Border}} \newcommand\mbd{\operatorname{MaxBorder}} \]

"A generating function is a device somewhat similar to a bag. Instead of carrying many little objects detachedly, which could be embarrassing, we put them all in a bag, and then we have only one object to carry, the bag."

— George Pólya, Mathematics and Plausible Reasoning (1954)

理论上，阅读本系列文章并不需要什么前置知识，遇到不会的再去查就够用了。但我仍然建议您最好掌握一些基础的微积分知识，和一些基础的组合计数手法。

本系列内容大量抄袭自如下资料：

1. command_block 老师的多项式计数杂谈。

我们会先略去各种在实际应用中不甚重要的基础证明，将一些运算法则当成公理来用，待到系列结束，我们会对所有不加证明地给出的结论作完整的证明。

生成函数的引入

正如 Pólya 所言，使用生成函数处理问题的一个基本思想就是试着将整个序列打包成一个整体，这个整体包含了序列的全部信息，那么接下来的处理中就只用考虑这个整体，而不是考虑数列的每一项。

那么该如何执行这个打包的过程？Euler 给出了一个办法，我们定义序列 \(\{a_n\}\) 的 OGF(Ordinary Generating Function， 普通生成函数) 为

\[ A(x)=\sum_{i=0}^{\infty}a_ix^i \]

其中，\(x\) 是用来区分数列各项的形式变元。记 \([x^n]A(x)=a_n\)，即 \(A(x)\) 的 \(n\) 次项系数。

这看起来只是换了一种方法写出我们的序列，这比起原先的方法有什么优越性？让我们先来尝试一个最简单的例子，即满足 \(f_n=1\) 的数列 \(\{f_n\}\)。它的生成函数 \(F(x)\) 为：

\[ F(x)=\sum_{i=0}^{\infty}x^i \]

要研究一个涉及无穷的结构，一种常用的方法是将其自我表示，我们有：

\[ \begin{aligned} F(x)&=1+x+x^2+x^3+x^4+x^5+\cdots\\ xF(x)&=\hspace{1.75em}x+x^2+x^3+x^4+x^5+\cdots \end{aligned} \]

所以有

\[ 1+xF(x)=F(x)\Longrightarrow F(x)=\frac{1}{1-x} \]

我们把右式这样¹的形式叫做封闭形式。

学过数学分析的朋友们会指出，我们刚刚操作无穷的过程过于轻率：如果 \(|x|\ge 1\)，那么 \(F(x)\) 不收敛，对两个无穷大加减是没有意义的。

这样的求和成立的原因是，\(x\) 在此处仅作形式变元，你可以把它看作是一个占位符，它存在的意义只是区分数列的各项，不会是任何的数（这就是它被称为形式的原因）。所以，我们不在乎它的敛散性，也不在乎它的取值，可以假定求和总是收敛。我们称这样 \(x\) 作为形式变元的幂级数是形式幂级数。

不加证明地，我们说生成函数的加，减，乘分别对应序列的如下变换：

1. \(C(x)=A(x)\pm B(x)\iff [x^n]C(x)=[x^n]A(x)\pm [x^n]B(x)\)
2. \(\displaystyle C(x)=A(x)B(x)\iff [x^n]C(x)=\sum_{i=0}^{n}[x^{n-i}]A(x)[x^i]B(x)\)

也就是说，对他们的封闭形式作前者的运算，就等于对它们的展开式作后者的变换。

生成函数与常系数齐次线性递推

斐波那契数列

上面只是讲了一些抽象的废话，接下来，我们试着用生成函数来解决一些简单的问题：求斐波那契数列² \(\{f_n\}\) 的通项公式。

先试着像上面一样表示出 \(\{f_n\}\) 的生成函数 \(F(x)\)，我们有：

\[ \begin{aligned} F(x)&=f_0+f_1x^1+f_2x^2+f_3x^3+\cdots\\ xF(x)&=\hspace{2.2em}f_0x^1+f_1x^2+f_2x^3+\cdots\\ x^2F(x)&=\hspace{5.4em}f_0x^2+f_1x^3+\cdots \end{aligned} \]

如此比对系数后我们可以发现，有

\[ x+xF(x)+x^2F(x)=F(x)\iff F(x)=\frac{x}{1-x-x^2} \]

我们尽量往之前的例子 \(\frac{1}{1-x}\) 的形式上凑，即分子是个常数，分母是个一次式。

我们断言 \(\frac{x}{1-x-x^2}\) 能被写成这样的两个分式之和，即：

\[ \frac{x}{1-x-x^2}=\frac{-x}{x^2+x-1}=\frac{a}{x-\alpha}+\frac{b}{x-\beta} \]

接下来，我们把这些参数一一求出，首先肯定有 \(\alpha，\beta\) 是 \(x^2+x-1\) 的两根，解得 \(\alpha=\frac{-1-\sqrt 5}{2}，\beta=\frac{-1+\sqrt 5}{2}\)。

又知道 \(a(x-\beta)+b(x-\alpha)=-x\)，比对系数有 \(a+b=-1\land a\beta +b\alpha =0\)，解得 \(a=\frac{-5-\sqrt 5}{10}，b=\frac{-5+\sqrt 5}{10}\)。

如此，四个常数均已知，由一开始的方法，我们知道 \(\displaystyle \frac{1}{1-qx}=\sum_{i=0}^{\infty}q^ix^i\)。从而：

\[ \frac{a}{x-\alpha}+\frac{b}{x-\beta}=\frac{-\frac{a}{\alpha}}{1-\frac{1}{\alpha}x}+\frac{-\frac{b}{\beta}}{1-\frac{1}{\beta}x}=-\frac{a}{\alpha}\sum_{i=0}^{\infty}\frac{1}{\alpha^i}x^i-\frac{b}{\beta}\sum_{i=0}^{\infty}\frac{1}{\beta^i}x^i \]

提取其第 \(n\) 次项并整理：

\[ \begin{aligned} \phantom{-}[x^n]\frac{1}{1-x-x^2}&=-\qty(\frac{a}{\alpha^{n+1}}+\frac{b}{\beta^{n+1}})\\ &=-\qty(\dfrac{\frac{-5-\sqrt 5}{10}}{\qty(\frac{-1-\sqrt 5}{2})^{n+1}}+\dfrac{\frac{-5+\sqrt 5}{10}}{\qty(\frac{-1+\sqrt 5}{2})^{n+1}})\\ &=-\frac{1}{\sqrt 5}\qty(\dfrac{1}{\qty(\frac{-1-\sqrt 5}{2})^{n}}-\dfrac{1}{\qty(\frac{-1+\sqrt 5}{2})^{n}})\\ &=-\frac{1}{\sqrt 5}\qty(\dfrac{2^n}{\qty(-1-\sqrt 5)^{n}}-\dfrac{2^n}{\qty(-1+\sqrt 5)^{n}})\\ &=\frac{1}{\sqrt 5}\qty(\qty(\dfrac{\sqrt 5+1}{2})^n-\qty(\dfrac{-\sqrt 5 +1}{2})^n)&\text{Rationalizing the denominator} \end{aligned} \]

于是，我们得到了斐波那契数列的通项公式：

\[ f_n=\frac{1}{\sqrt 5}\qty(\qty(\dfrac{\sqrt 5+1}{2})^n-\qty(\dfrac{-\sqrt 5 +1}{2})^n) \]

更一般的情形？

假设有序列 \(\{f_n\}\)，给出其 \(0\sim m-1\) 项，再给出一个常数序列 \(\langle a_1,a_2,\cdots, a_m\rangle\)，对于 \(k\ge m\) 有：

\[ f_k=\sum_{i=1}^{m}f_{k-i}a_i \]

这样的递推，我们称之为常系数齐次线性递推，我们试着为它构造一个生成函数。

仍然试着做上面类似的尝试，称其生成函数为 \(F(x)\)，构造一个 \(m\) 次多项式 \(Q\)，使其有 \([x^0]Q(x)=-1,[x^k]Q(x)=a_k(0<k\le m)\)。

容易知道 \([x^k]F(x)Q(x)\) 在 \(k\ge m\) 的情况下为 \(0\)，而 \(F(x)\) 的 \(<m\) 次项已知，\(Q(x)\) 的 \(\le m\) 次项已知，我们可以构造出 \(P(x)\) 为

\[ P(x)=F(x)Q(x)\pmod {x^m} \]

其中一个形式幂级数 \(G(x)\) 对 \(x^k\) 取模的意义为，将其 \(\ge k\) 次幂的系数设置为 \(0\)。

这样就有：

\[ F(x)Q(x)-P(x)=0\iff F(x)=\frac{P(x)}{Q(x)} \]

我们还不会对这个式子进行进一步的处理，暂时到此为止吧。

---

1. 由常数，变量，基本函数的有限次四则运算/乘方/函数复合得来的式子 ↩

2. \(f_0=0，f_1=1， f_{n}=f_{n-1}+f_{n-2}(n\ge 2)\) ↩