生成函数

常生成函数

$$A(x)=\sum\limits_{n\ge0}a_nx^n$$

设$S=\{a_1,a_2,…,a_k\}$，且$a_i$可以取的次数集合为$M_i$，记$F_i(x)=\sum\limits_{u\in M_i}x^u$，则从$S$中取$n$个元素组成集合的方案数$g(n)$的常生成函数$G(x)=\sum\limits_{i\ge 0}g(i)x^i$满足

$$G(x)=\prod\limits_{i=1}^kF_i(x)$$

形式幂级数$A(x)$的逆元：$A(x)B(x)=1$
逆元存在的条件：$[x^0]A(x)\not=0$
常见的逆

$$A(x)=\sum\limits_{i\ge0}x^i=(1-x)^{-1}\\ A(x)=\sum\limits_{i\ge0}a^ix^i=(1-ax)^{-1}\\ A(x)=\sum\limits_{i\ge0}\begin{pmatrix}i+k-1\\i\end{pmatrix}x^i=[(1-x)^k]^{-1}$$

指数生成函数

$$A(x)=\sum\limits_{n\ge 0}a_n\dfrac{x^n}{n!}$$

设$S=\{a_1,a_2,…,a_k\}$，且$a_i$可以取的次数集合为$M_i$，记$F_i=\sum\limits_{u\in M_i}\dfrac{x^u}{u!}$，则从$S$中取$n$个元素排成一列的方案数$g(n)$的指数生成函数$G(x)=\sum\limits_{i\ge 0}g(i)\dfrac{x^i}{i!}$，满足

$$G(x)=\prod\limits_{i=1}^kF_i(x)$$

公式：

$$\exp(x)=\sum\limits_{i\ge0}\dfrac{x^i}{i!}\\ \exp(ax)=\sum\limits_{i\ge0}a^i\dfrac{x^i}{i!}\\ \ln(1+x)=\sum\limits_{i\ge1}(-1)^{i+1}\dfrac{x^n}{i}$$