一、从小学数学开始
普通型生成函数：
\[F(x) = \sum_{n \ge 0} a_n x ^ n
\]
指数型生成函数：
\[F(x) = \sum_{n \ge 0} a_n \dfrac{x ^ n}{n!}
\]
这是最基础的两种生成函数。
普通型生成函数的 \(\times\) 对应卷积，组合意思为不考虑顺序。
指数型生成函数的 \(\times\) 对应二项卷积，组合意义为考虑顺序。
常见的生成函数：
\[\sum_{n \ge 0} x ^ n = \dfrac{1}{1 - x}
\]
\[\sum_{n \ge 0} \binom{n + m}{m} x ^ n = \dfrac{1}{(1 - x) ^ {m + 1}}
\]
\[\sum_{n \ge 0} \dfrac{x ^ n}{n!} = e ^ x
\]
\[\sum_{n \ge 0, n \equiv 0 \pmod{2}} \dfrac{x ^ n}{n!} = \dfrac{e ^ x + e ^ {-x}}{2}
\]
\[\sum_{n \ge 0, n \equiv 1 \pmod{2}} \dfrac{x ^ n}{n!} = \dfrac{e ^ x - e ^ {-x}}{2}
\]
\[\sum_{n \ge 0} \dfrac{x ^ n}{n} = \ln (1 - x)
\]
二项式定理：
\[(a + b) ^ n = \sum_{i = 0} ^ n \binom{n}{i} a ^ i b ^ {n - i}
\]
卡特兰数的生成函数：
设 \(f_n\) 表示卡特兰数第 \(n\) 项：
\[f_0 = 1, f_n = \sum_{i = 0} ^ {n - 1} f_i \cdot f_{n - i - 1}
\]
设 \(F(x) = \sum_{n \ge 0} f_n x ^ n\)。
\[F ^ 2 x + 1 = F
\]
解得：
\[F = \dfrac{1 \pm \sqrt{1 - 4x}}{2x} = \dfrac{2}{1 \mp \sqrt{1 - 4x}}
\]
代入 \(x = 0\)，取 \(+\) 时得到常数项 \(0\)，取 \(-\) 时不收敛，所以：
\[F(x) = \dfrac{2}{1 + \sqrt{1 - 4x}} = \dfrac{1 - \sqrt{1 - 4x}}{2x}
\]
双阶乘公式：
\[n!! = n \times (n - 2) \times \cdots
\]
\[n!! = \begin{cases} (n - 1)!! \times n \qquad n \equiv 1 \pmod{2} \\ 2 ^ {\frac{n}{2}} \times \left(\dfrac{n}{2}\right)! \qquad n \equiv 0 \pmod{2}
\end{cases}\]