普通生成函数（OGF）
形式
\[ F = \sum_{n \geq 0} \ f_n \ x^n
\]
基本运算
1.相加
\[ F \pm G = \sum_{n \geq 0} \ (f_n \pm g_n) \ x^n
\]
2.卷积
\[ F \cdot G = \sum_{n \geq 0} \ x^n\ \sum_{i = 0} ^ n f_ig_{n - i}
\]
几种常见的幂级数求和
\[f = {0, 1, 1, 1, ...} \\ 数列f的生成函数：F = \sum_{n \geq 0} x^n = \frac{x}{1 - x}
\]
\[f = {1, 0, 1, 0, 1, 0, ...} \\ 数列f的生成函数：F = \sum_{n \geq 0} x^{2n} = \frac{1}{1 - x^2}
\]
\[f = {1, 2, 3, 4, ...} \\ 数列f的生成函数：F = \sum_{n \geq 0} (n + 1) x^n = \frac{1}{(1 - x)^2}
\]
\[f_n = C_{m}^{n} \\ 数列f的生成函数：F = \sum_{n \geq 0} C_{m}^{n}x^n = (1 + x)^m
\]
\[f_n = C_{n + m}^{n} \\ 数列f的生成函数：F = \sum_{n \geq 0} C_{n + m}^{n} x^n = \frac{1}{(1 - x)^{m + 1}}
\]
指数生成函数（EGF）
形式：
\[ F = \sum_{n \geq 0} f_n \frac{x^n}{n!}
\]
卷积：
\[ F \cdot G = \sum_{n \geq 0} f_n \frac{x^n}{n!} \cdot \sum_{n \geq 0} g_n \frac{x^n}{n!} = \sum_{n \geq 0} \frac{x^n}{n!} \sum_{i = 0}^{n} C_n^i f_ig_{n - i}
\]
待续