生成函数学习笔记

初探生成函数

生成函数

普通生成函数(OGF)

定义序列$a$的生成函数为

$$F(x) = \sum_{i = 0} ^ {\infty} a_ix^i$$

运算

其加法运算为

$$F(x) \pm G(x) = \sum_{i = 0} ^ {\infty} (a_i \pm b_i) x^ i$$

乘法运算，也就是卷积为

$$F(x) \ast G(x) = \sum_{i = 0} ^ {\infty} \bigg( \sum_{j = 0} ^ i a_jb_{i - j} \bigg)x^i$$

其为序列$\sum_ {i = 0}^n a_i b_{n - i}$的生成函数。

封闭形式

根据等比数列求和公式可得

$$F(x) = \sum_{i = 0} ^ {\infty} a_i x^i = a_0 \times \frac{1 - x ^ {\infty}}{1 - x} = \frac{a_0}{1 - x}$$

牛顿二项式定理

定义组合数为

$$\dbinom{n}{m} = \frac{n ^ {\underline{m}}}{m!}, n \in \mathbb{C}, m \in \mathbb{N}$$

指数型生成函数(EGF)

定义序列$a$的指数型生成函数为

$$F(x) = \sum_{i = 0} ^ {\infty} a_i \frac{x^i}{i !}$$

显然有

$$e^x = \sum_{i = 1}^{\infty} \frac{e^0 x^i}{i!} = \sum_{i = 1}^{\infty}\frac{x^i}{i!} \\ \frac{e^x + e^{-x}}{2} = \sum_{i = 0}^{\infty} \frac{x^{2i}}{(2i)!} \\ \frac{e^x - e ^ {-x}}{2} =\sum_{i = 0}^{\infty} \frac{x ^ {2i + 1}}{(2i+1)!}$$

可以应用到组合数学中。