标签：1.1 多项式 sum nf 生成 ge 函数

1. 生成函数

1.1 普通型生成函数 OGF

1.1.1 基础

序列 \(\{f_i\}_{i=0}^n\) 的普通型生成函数是 \(F(x) = \sum_{i=0}^nf_ix^i\)。\(n\) 可以等于 \(\infty\)。

有一些常用的运算规则需要记住：

\[F(x) + G(x) = H(x) \iff h_n = f_n + g_n \]

\[F(x)G(x) = H(x) \iff h_n = \sum_{i=0}^nf_ig_{n-i} \]

\[x^kF(x) = \sum_{i \ge k}f_{i - k}x^i \]

\[F'(x) = \sum_{i \ge 0} (i+1)f_{i+1} x^i \]

还有一个关于幂级数的和式：\(\sum_{i \ge 0}x^i = \frac{1}{1 - x}\)

1.1.1 解递推式

生成函数可以用来解递推式。

比如斐波那契数列，卡特兰数列等。

关键在于将每一项都变成生成函数的形式。

比如 \(f_{0} = 0, f_{1} = 1, f_{i} = f_{i - 1} + f_{i - 2}\)。

我们将其变成：\(F(x) = xF(x) + x^2F(x)\) 然后解出 \(F(x)\) 即可。

标签：1.1,多项式,sum,nf,生成,ge,函数
From： https://www.cnblogs.com/rlc202204/p/18091350