生成函数学习笔记（刚学，啥都没得）
生成函数学习笔记
普通生成函数（ordinary generating function，OGF）
普通生成函数的定义及简单例子
序列 \(a\) 的普通生成函数是形式幂级数 \(F(z)=\sum\limits_{i=0}^{+\infty}a_iz^i\)。后文的 \(\sum\limits_i\) 若不写上下界，默认为 \(\sum\limits_{i=0}^{+\infty}\)。
例如，对于数列 \(\langle 1,1,1,\cdots\rangle\)，它的普通生成函数是 \(F(z)=\sum\limits_iz^i\)。仿照等比数列求和公式，我们错位相减，可以得到 \(F(z)=\frac{1}{1-z}\)，这个形式称为普通生成函数的封闭形式。由于生成函数是形式幂级数，我们不关注其收敛性，因此这么变形是没有问题的。
一些常见的普通生成函数及其封闭形式有：
\[\begin{aligned}
\sum\limits_iz^i&=\frac{1}{1-z}\\
\sum\limits_{i=0}^nz^i&=\frac{1-z^{n+1}}{1-z}\\
\sum\limits_{2\mid i}z^i&=\frac{1}{1-z^2}\\
\sum\limits_{2\nmid i}z^i&=\frac{z}{1-z^2}\\
\end{aligned}
\]