生成函数初步

标签：geq frac 函数 sum 生成 初步 数列

普通生成函数（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} \]

待续

标签：geq,frac,函数,sum,生成,初步,数列
From： https://www.cnblogs.com/mcggvc/p/17770351.html