GF 相关

OGF

无穷序列 $a$ 的 OGF 为 $F(x)=\sum\limits_{k\geq 0}a_kx^k$ ， $x$ 为占位符，没有实际意义，但可以用于分析 OGF 的敛散。

记 $[x^n]F(x)=a_n$

如果将 $a$ 看作一个背包序列，则其组合意义为选出和为 $k$ 的无标号元素方案数为 $[x^k]F(x)$ 。

这个形式幂级数的形式可以从代数意义上探究组合对象的性质。

可以定义 OGF 加法，减法，卷积，对应在 $a$ 上的加法，减法，卷积。

OGF 卷积的组合意义为合并两个背包。

OGF 可以写出封闭形式，将无穷项的级数写成有限项的多项式（分式），而不丢失组合上的性质，这可以方便维护。

$F(x)=\sum\limits_{k\geq 0}x^k=\dfrac{1}{1-x}$
考虑 $xF(x)+1=F(x)$ ，解方程即可。
从卷积角度入手可以说明卷上一个 $\dfrac{1}{1-x}$ 的组合意义是对 OGF 做前缀和，卷上 $1-x$ 的组合意义是对 OGF 差分。
同理可以得到 $F(x)=\sum\limits_{k\geq 0}c^kx^k=\dfrac{1}{1-cx}$
$F(x)=\sum\limits_{k\geq 0}\binom{\alpha}{k}x^k=(1+x)^{\alpha}$ 。
广义二项式定理。
$F(x)=\sum\limits_{k\geq 0}\binom{n+k-1}{n-1}x^k=\dfrac{1}{(1-x)^n}$
考虑操作实际意义为对杨辉三角第一列做 $n$ 次前缀和，套用组合数列前缀和的性质我们可以说明其为第 $n$ 列杨辉三角值。

也可以由封闭形式反推展开形式得到通项。

形如 $\dfrac{A}{1-Bx}$ 的 OGF 容易得到其展开形式为 $A\sum\limits_{k\geq 0}B^kx^k$ ，通项为 $a_n=AB^n$ ，若干形如这种形式的项加起来也同理。对于不满足这种形式的 OGF，考虑通过分式分解的方法转成这个形式然后展开。

考虑斐波那契数列， $F_n=F_{n-1}+F{n-2}$ 容易写出其封闭形式的生成函数：

$F(x)=xF(x)+x^2F(x)+x$

$F(x)=\dfrac{x}{1-x-x^2}$

考虑待定系数，我们断言其可以被分解为 $\dfrac{A}{1-ax}+\dfrac{B}{1-bx}$ 解出待定系数方程可以得到：

\begin{cases} A=\dfrac{1}{\sqrt{5}}\\ a=\dfrac{1+\sqrt{5}}{2}\\ B=-\dfrac{1}{\sqrt{5}}\\ b=\dfrac{1-\sqrt{5}}{2}\\ \end{cases}

然后就可以得到斐波那契通项公式：

$F_n=\dfrac{\bigg(\dfrac{1+\sqrt{5}}{2}\bigg)^n-\bigg(\dfrac{1-\sqrt{5}}{2}\bigg)}{\sqrt{5}}$

这里有些惊人的，与递推式的特征方程相关的性质，但是我不会。

EGF

无穷序列 $a$ 的 EGF 为 $F(x)=\sum\limits_{k\geq 0}\dfrac{a_kx^k}{k!}$ 。

这个除以 $k!$ 可以这么理解： $a_k$ 为 $k$ 有标号元素组合的方案数，因此除掉 $k!$ 在 EGF 内部就不考虑顺序了，这样可以应用幂级数的相关代数性质。因此 EGF 用于维护有标号集合。

同样可以定义 EGF 的加减法，而卷积在 $\dfrac{a_k}{k!}$ 上为普通卷积，在 $a_k$ 上为二项卷积。这也说明了 EGF 和乘法的组合意义。

EGF 极其关键的性质是 $\e^x=\sum\limits_{k\geq 0}\dfrac{x^k}{k!}$ 。这是 $\e^x$ 的泰勒展开，其组合意义为将 $x$ 这个有标号组合体自由组合得到的 EGF（枚举个数然后组合，再考虑内部的顺序）。

考虑贝尔数的 EGF，选出一个大小为 $x$ 的有标号非空集合 EGF 为 $\e^x-1$ ，再自由组合为 $\e^{\e^x-1}$ 。

考虑第二类斯特林数的 EGF，相当于只能自由组合 $k$ 次了，那么为 $(\e^x-1)^k$ 。

考虑一个有 $m$ 种颜色的序列，每种颜色的 EGF 为 $F_i(x)$ ，那么用这 $m$ 种颜色排出一个长为 $n$ 的序列的方案数为 $[\dfrac{x^n}{n!}]\prod\limits_{i=1}^m F_i(x)$ 。这说明可以用 EGF 的乘积来从每种颜色的方向刻画序列方案数（有标号 SEQ 构造是吧）。