生成函数
\[
无穷多项的多项式，成为函数与数列之间的桥梁。\]
\[
\begin{align}f(x)&=a_0+a_1x+a_2x^2+a_3x^3+\cdots \\
&= \sum_{i=0}^{+\infty} a_ix^i\end{align}\]
等于号的含义：在某个范围内（如 \(0<x<1\) ），等号左右“要多接近有多接近”.
当 $$ a=[1,1,1,\dots] $$ 时，
\[
F(x)=\sum_{i=0}^{+\infty} x^i=\frac{1}{1-x}\]
又，
\[
\frac{1}{1-ax}=\sum_{i=0}^{+\infty} a^ix^i\]
当 $$ a=[0,1,1,2,3,5,8,13,\dots] $$ ，即斐波那契数列时，
\[\begin{align}F(x)&=\sum_{i=0}^{+\infty} a_ix^i \\xF(x)&=\sum_{i=0}^{+\infty} a_ix^{i+1}\\x^2F(x)&=\sum_{i=0}^{+\infty} a_ix^{i+2}\end{align}
\]
由 $ (3)-(4)-(5) $ 得，
\[x=(1-x-x^2)F(x)\]
即，
\[F(x)=\frac{x}{1-x-x^2}
\]
又，
\[
\frac{x}{1-x-x^2}=\frac{1}{\sqrt{5}}\cdot(\frac{1}{1-(\frac{1+\sqrt{5}}{2})x}-\frac{1}{1-(\frac{1-\sqrt{5}}{2})x})\]
故，
\[
a_n=\frac{1}{\sqrt{5}}\cdot[(\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n]\]
- \(c\cdot f(x) \to\) 数列倍增
- \(x\cdot f(x) \to\) 数列右移
- \([f(x)-f(0)] \div x \to\) 数列左移
- \(f_1(x)\pm f_2(x) \to\) 数列求和/差
数列卷积：
\[F(x)=\sum_{i=0}^{+\infty}a_ix^i ~~~G(x)=\sum_{i=0}^{+\infty}b_ix^i
\]
\[F(x)\cdot G(x)=\sum_{k=0}^{+\infty}\sum_{i=0}^{k}a^{i}b^{k-i}x^k
\]
特别地，
\[F(x)=\sum_{i=0}^{+\infty}a_ix^i
\]
\[\frac{1}{1-x} \cdot F(x)=\sum_{k=0}^{+\infty}\sum_{i=0}^{k}a_ix^k
\]
即对数列进行前缀和.
通过 \(n-1\) 次前缀和，可以得到二项式定理扩展：
\[(1-x)^{-n}=\sum_{i=0}^{+\infty}\binom{n-1+i}{n-1}x^i
\]
另外还可以这样理解：
\[\begin{align}
\frac{1}{(1-x)^n}&=\frac{1}{1-x}\cdot\frac{1}{1-x}\cdot\ldots\cdot\frac{1}{1-x}\\
&=\left(\sum_{e_1\geq0}x^{e_1}\right)\left(\sum_{e_2\geq0}x^{e_2}\right)\dots\left(\sum_{e_n\geq0}x^{e_n}\right)\\
&=\sum_{e_1+e_2+\dots+e_n=m}x^m\\
&=\binom{n-1+m}{m}x^m
\end{align}
\]
\[x^m$$ 的系数即为满足 $$e_1+e_2+\dots+e_n=m$$ 的解的个数.更一般地，广义牛顿二项式定理：$$(x+y)^\alpha=\sum_{i=0}^{+\infty}\binom{\alpha}{i}x^{\alpha-i}y^i\]
其中，
\[
\binom{n}{m}=\frac{n(n-1)\cdots(n-m+1)}{m!}=\frac{(n)_m}{m!}\]
补充多项式定理：
\[(x_1+x_2+\dots+x_n)^m=\sum_{\alpha_1+\alpha_2+\dots+\alpha_n=k}\frac{m!}{\alpha_1!\alpha_2!\cdots\alpha_n!}x_1^{\alpha_1}x_2^{\alpha_2}\cdots x_n^{\alpha_n}
\]
证明如下：
\[\begin{align}
(x_1+x_2+\dots+x_n)^m&=\left((x_1+x_2+\cdots+x_{n-1})+x_n\right)^m\\
&=\sum_{\alpha_n\geq 0}^m\binom{m}{\alpha_n}x_n^{\alpha_n}(x_1+x_2+\cdots+x_{n-1})^{m-\alpha_n}\\
&=\sum_{\alpha_1+\alpha_2+\cdots+\alpha_n=m}\left.\binom{m}{\alpha_n}\binom{m-\alpha_n}{\alpha_{n-1}}\cdots\binom{m-\alpha_n-\cdots-\alpha_2}{\alpha_1}\right.\\
&=\sum_{\alpha_1+\alpha_2+\dots+\alpha_n=k}\frac{m!}{\alpha_1!\alpha_2!\cdots\alpha_n!}x_1^{\alpha_1}x_2^{\alpha_2}\cdots x_n^{\alpha_n}
\end{align}
\]
指数生成函数：
\[f(x)=\sum_{i=0}^{+\infty}a_i\frac{x^i}{i!}
\]
特别地，
\[e^x=\sum_{i=0}^{+\infty}\frac{x^i}{i!}
\]
而该种生成函数的卷积可以将系数乘上组合数：
\[F(x)=\sum_{i=0}^{+\infty}a_i\frac{x^i}{i!}~~~G(x)=\sum_{i=0}^{+\infty}b_i\frac{x^i}{i!}
\]
\[F(x) \cdot G(x)=\sum_{k=0}^{+\infty}\sum_{i=0}^{k}\binom{k}{i}a^ib^{k-i}\frac{x^k}{k!}\]
Dirichlet级数生成函数：
\[F(s)=\sum_{i=1}^{+\infty}\frac{a_i}{i^s}
\]
而该种生成函数的卷积在数论方面有重要用途：
\[F(s)=\sum_{i=1}^{+\infty}\frac{a_i}{i^s}~~~G(s)=\sum_{i=1}^{+\infty}\frac{b_i}{i^s}
\]
\[F(s)\cdot G(s)=\sum_{k=1}^{+\infty}\frac{\sum_{i|k}a_ib_{k/i}}{k^s}
\]
特别地，
\[F(s)=\sum_{i=1}^{+\infty}\frac{1}{i^s}
\]
\[F^2(s)=\sum_{k=1}^{+\infty}\frac{d(k)}{k^s}
\]
其中，\(d(k)\) 代表 \(k\) 的约数个数.
例题：求长度为 \(n\) 的 \(01\) 字符串中的不可分解的字符串的个数
- “不可分解”指不能写成两个或多个相同字符串的拼接
- $“100100100”= “100” * 3 $ 可分解
- \(“1110”\) 不可分解
设 \(f(x)\) 代表长度为 \(x\) 的不可分解的 \(01\) 字符串的数量.
因为将任意一个 \(01\) 字符串分解为一个不可分解的 \(01\) 字符串的方式唯一.
故，
\[2^n=\sum_{i|n}f(i)
\]
利用莫比乌斯反演可得，
\[f(n)=\sum_{i|n}\mu (\frac{n}{i})\cdot 2^i
\]