。。。我最近写数学越来越多了，人都麻了
前置知识
好像没啥，看得懂公式就行了。
引入
一般的生成函数会和某个数列 \(a_0,a_1,\dots,a_n\) 建立关系，它是一个多项式函数，其中每一项的系数等于对应数列每一位的值，这样的函数有时候也叫形式幂级数。
最常见的形式（普通生成函数）是这样的：
\[g(x)=\sum^\infin_{i=0}a_ix^i\]
用于组合数学
当然，有时用在组合数学时会把生成函数缩减到一个有限项多项式，但无限项多项式不一定求不出有意义的解。
先来看一个简单的计数问题：
有一个苹果，一只香蕉和一个菠萝，求：
- 不选有几种选法
- 选一个有几种选法
- 选两个有几种选法
- 选三个有几种选法
平时解这类问题时，我们一般都用组合数，上述问题直接对应了 \(\dbinom{3}{0}\)，\(\dbinom{3}{1}\)，\(\dbinom{3}{2}\) 和 \(\dbinom{3}{3}\)。但这里要用一种不太一样的方式，以此更好的理解生成函数。
我们用 \(1\) 代表不选，\(x\) 代表选一个，\(x^2\) 代表选两个，etc.
对于每种水果，都有选一个和不选两种可能，也就是 \((x+1)\)。
那么对于三种水果，就可以列一个这样的式子：
\[\begin{array}{rl} &(x+1)(x+1)(x+1)\\ =&1+3x+3x^2+x^3 \end{array}\]
发现每一项的系数刚好对应了上面问题的答案。
所以 \(g(x)=(x+1)(x+1)(x+1)\) 是 \(\dbinom{3}{0},\dbinom{3}{1},\dbinom{3}{2},\dbinom{3}{3}\) 这个数列的生成函数。
对于更大的范围它同样成立：
\[g(x)=(x+1)^n\rightarrow\dbinom{n}{0},\dbinom{n}{1},\cdots,\dbinom{n}{n}\]
还有更神奇的应用：
\[\prod_{i=1}^n(1+c_ix)\]
\[=1+(c_1+\cdots+c_n)x+(c_1c_2+c_1c_3+\cdots+c_{n-1}c_n)x^2+\cdots+(c_1c_2\cdots c_n)x^n\]
则 \(x^i\) 项的系数就是从 \(n\) 个元素中选取 \(i\) 个进行组合的全体。令全体 \(c_i=1\)，就是上面的结论。再令 \(x=1\)，得到 \(\sum\limits_{i=0}^n\dbinom{n}{i}=(1+1)^n=2^n\)。
有人可能发现这完全就是二项式定理，但是它可以拓展到更大的范围。
样例一
\[c_1+c_2+c_3+c_4+c_5=30\] 其中： \[2\leq c_1\leq4,3\leq c_i\leq8(2\leq i \leq5)\] 解法： \[ (x^2+x^3+x^4)(x^3+x^4+x^5+x^6+x^7+x^8)^4 \] 找到其中 \(x^{30}\) 的系数即可。
样例二
依然是 \[c_1+c_2+c_3+c_4+c_5=30\] 其中： \[0\leq c_i(1\leq i \leq5),c_2\in\mathbb{E},c_3\in\mathbb{O}\] （\(c_2\) 是偶数，\(c_3\) 是奇数，注意没有上界，从这里开始接触到形式幂级数的本质了）
解法： \[ (1+x^1+x^2\cdots)^3(1+x^2+x^4+\cdots)(x+x^3+x^5+\cdots) \]
同样地，找到 \(x^{30}\) 的系数。
用于数列通项公式
特殊形式
先来看一个最简单的序列：
\[a=1,1,1,1,1\]
也就是五个一。
它的生成函数就是：
\[g(x)=1+x+x^2+x^3+x^4\]
经过等比数列求和的转化可以变为：
\[g(x)=\dfrac{1-x^5}{1-x}\]
如果 \(a\) 有无限项呢？
\[a=1,1,1,\cdots\]
\[g(x)=1+x+x^2+\cdots\]
\[\sum_{i=0}^nx^i=\dfrac{1-x^n}{1-x}\]
\[n\to\infin\]
当 \(x\in(1,-1)\) 时
\[x^n\to 0\]
\[\therefore g(x)=\dfrac{1}{1-x}\]
你可能疑惑为什么能直接给 \(x\) 限定域，但是上面提到了，生成函数是形式幂级数，\(x\) 的值没有意义。从这里开始对于没有上界的生成函数，出现了一种能大大简化计算的表达方式。
\[g(x)=\sum_{i=0}^\infin x^i=\dfrac{1}{1-x}\]
将 \(x\) 改为 \(x^2\) 得到：
\[g(x)=1+x^2+x^4+\cdots=\sum_{i=0}^\infin x^{2i}=\dfrac{1}{1-x^2}\]
将 \(x\) 改为 \(x^k\) 得到：
\[g(x)=\sum_{i=0}^\infin x^{ki}=\dfrac{1}{1-x^k}\]
所以 \(1,0,1,0,1,\cdots\) 的生成函数是 \(\dfrac{1}{1-x^2}\)。
求以下数列的生成函数：
\[\dbinom{1}{k},\dbinom{2}{k},\dbinom{3}{k},\cdots\]
\[g(x)=\dbinom{1}{k}+\dbinom{2}{k}x+\dbinom{3}{k}x^2+\cdots\]
\[g(x)=\sum_{i=0}^\infin\dbinom{i+1}{k}x^i\]
运用广义二项式定理可得：
\[g(x)=(1+x^2+x^3+\cdots)^k=\dfrac{1}{(1-x)^k}\]
两个生成函数相加是什么呢？
设：
\[g_a(x)=\sum_{i=0}^\infin a_ix^i\]
\[g_b(x)=\sum_{i=0}^\infin b_ix^i\]
\[g_a(x)+g_b(x)=\sum_{i=0}^\infin(a_i+b_i)x^i\]
好像没什么可解释的。这就是数列的每一项分别相加。
两个生成函数相乘是什么呢？
设：
\[g_a(x)=\sum_{i=0}^\infin a_ix^i\]
\[g_b(x)=\sum_{i=0}^\infin b_ix^i\]
那么它们相乘的结果就是它们的卷积：
\[g_a(x)g_b(x)=\sum_{i=0}^\infin(\sum_{k=0}^ia_kb_{i-k})x^i\]
你可能觉得这和卷积毫无关系，但是仔细想想，这就是多项式相乘啊，做快速傅里叶变换的时候不就是加速的卷积吗？
知道了这几种特殊形式，就可以快速解出很多问题，比如著名的 Luogu P2000。你也可以用这个方式快速解出上面的样例二。
\[g(x)=(1+x^1+x^2\cdots)^3(1+x^2+x^4+\cdots)(x+x^3+x^5+\cdots)\]
\[g(x)=\left(\dfrac{1}{1-x}\right)^3\times\dfrac{1}{1-x^2}\times\dfrac{x}{1-x^2}\]
斐波那契数列
很久之前我曾经发过一个快速求斐波那契的通项公式，实际上它是从生成函数来的。具体看看过程：
设 \(F_0=0\)，\(F_1=1\)。
\[g(x)=x+x^2+2x^3+3x^4+5x^5+\cdots\]
将生成函数乘上 \(x\)，就相当于将其整体后移一位。又因为数列每一项都是前面两项的和（除了初始值不是，它会留下一个富余的 \(x\)），所以：
\[g(x)-xg(x)-x^2g(x)=x\]
解得：
\[g(x)=\dfrac{x}{1-x-x^2}\]
因式分解得到：
\[g(x)=\dfrac{x}{\left(1-\dfrac{1-\sqrt{5}}{2}x\right)\left(1-\dfrac{1+\sqrt{5}}{2}x\right)}\]
运用裂项法得到：
\[g(x)=-\dfrac{1}{\sqrt5}\dfrac{1}{\left(1-\dfrac{1-\sqrt5}{2}x\right)} + \dfrac{1}{\sqrt5}\dfrac{1}{\left(1-\dfrac{1+\sqrt5}{2}x\right)}\]
可见它是两个类似上面等比数列求和 \(\dfrac{1}{1-x}\) 的形式，然后乘上常数并求和。
反向运用上面的方式将其还原成数列，得到：
\[\operatorname{F}(n)=\dfrac{\sqrt{5}}{5}\left[\left(\frac{1+\sqrt5}{2}\right)^n-\left(\frac{1-\sqrt5}{2}\right)^n\right]\]
理论上，这种方法可以应用于任何线性齐次递推中，比如：
\[\begin{array}{rcl} F(n,1)&=&F(n-1,2)+2F(n-3,1)+5,\\ F(n,2)&=&F(n-1,1)+3F(n-3,1)+2F(n-3,2)+3 \end{array}\]
但是由于它过于复杂，我不会推。