生成函数，又叫母函数，是一种形式幂级数(废话)
普通生成函数
若 $f(x)=\sum_{i=0}^{\infty}x^i$
有 $x\cdot f(x)=\sum_{i=1}^{\infty}x^i$
$f(x)=x\cdot f(x)+1$
即 $f(x)=\frac{1}{1-x}$
此时 $x\in(-1,1)$ 时函数收敛
$\frac{1}{1-x}$ 即为 $f(x)$ 生成函数
因而 $\frac{1}{1-x}$ 对应数列 $1,1,1,1,1,1,1,……$
那么,推导得出以下关系(证明略)
$\frac{k}{1-x}\to k,k,k,k,k,k\cdots$
$\frac{1}{(1-x)^2}\to 1,2,3,4,5,6\cdots$
$\frac{1}{(1-x)^n}$ 对应 $f(x)=\sum_{i=0}^{\infty}C^{i-1}_{n+i-1}x^i$
$\frac{k}{(1-x)^n}$ 对应 $f(x)=\sum_{i=0}^{\infty}k\cdot C^{i-1}_{n+i-1}x^i$
例题：试试求斐波那契数列通项公式
主要解决组合计算问题
指数生成函数
参考了算法学习笔记(6)：指数生成函数（EGF） - 知乎 (zhihu.com)
$$
\begin{aligned}
&引入：n个球，其中有k种不同的球，第i种球有n_i个，问有多少种排列 \\
&答案：\frac{n!}{\prod_{i=1}^kn_i!} \\
&不难发现其中全排列有n!种，但种类相同一种算了n_i!次，故要\div n_i! \\
&弱化一下就变成了组合数了 \\
&那么形如f(x)=\sum_{i=0}^{\infty}a_i\frac{x^i}{i!}即为指数生成函数 \\
&基本形式f(x)=\sum_{i=0}^{\infty}\frac{x^i}{i!}\to e^x \\
\end{aligned}
$$
解决排列计数问题