生成函数变换学习笔记

Part 1 前言

生成函数的变换是把一个生成函数变成另一个生成函数的一些式子，这些式子往往具有某种组合意义。

在本文中，我们讨论的是球盒模型，即统计在若干个盒子中放 $n$ 个小球的方案数的问题。

Part 2 一些约定

• $F(x)=\sum\limits_{i=0}^\infin f_ix^i$，$G(x)=\sum\limits_{i=0}^\infin f_i\frac{x^i}{i!}$：参与变换的生成函数，即 $f_i$ 的 OGF 与 EGF，$f_i$ 的意义是有 $f_i$ 种方式把 $i$ 个球放进同一个盒子中；
• 一般认为 $f_0=0$，即不能存在空盒子；
• $[x^n]H(x)$：若 $H(x)$ 为 OGF，则代表 $H(x)$ 中 $x^n$ 的系数；若 $H(x)$ 为 EGF，则代表 $H(x)$ 中 $\frac{x^n}{n!}$ 的系数。简单的说就是我们要求的答案；

Part 3 各种生成函数的变换

球无标号，盒有标号：不知道叫什么变换

最简单，根据 OGF 乘法的定义，枚举球一共占用了多少个盒子，有：

$\begin{aligned} \operatorname{???}(F(x))&=\sum\limits_{i=0}^\infin F(x)^i\\ &=\frac{1}{1-F(x)} \end{aligned}$

球有标号，盒有标号：$\operatorname{Invert}$ 变换

也可以叫 $\operatorname{SEQ}$ 变换。

根据 EGF 乘法的定义，枚举球一共占用了多少个盒子，有：

$\begin{aligned} \operatorname{Invert}(G(x))&=\sum\limits_{i=0}^\infin G(x)^i\\ &=\frac{1}{1-G(x)} \end{aligned}$

球有标号，盒无标号：$\operatorname{Exp}$ 变换

根据 EGF 乘法的定义，枚举球一共占用了多少个盒子，但这样盒子是有标号的。注意到每种标号方式都会被算到恰好一次，所以要除掉盒子个数的阶乘：

$\begin{aligned} \operatorname{Exp}(G(x))&=\sum\limits_{i=0}^\infin \frac{G(x)^i}{i!}\\ &=\exp(G(x)) \end{aligned}$

球无标号，盒无标号：$\operatorname{Weigh}\&\operatorname{Euler}$ 变换

$\operatorname{Weigh}$ 变换

放的球一样多，放球的方式也一样的盒子只能出现一次。

类似 $01$ 背包，放 $i$ 个球的盒子有 $f_i$ 种，每种只能出现一次，那么有：

$\operatorname{Weigh}(F(x))=\prod\limits_{i=0}^\infin (1+x^i)^{f_i}\\$

即枚举盒子大小，然后因为有 $f_i$ 种这样的盒子所以要乘那么多次 $1+x^i$。

这个东西不好化简，考虑 $\ln$ 再 $\exp$，要注意 $\ln(1+x)=-\sum\limits_{i=1}^\infin\frac{(-1)^{i}(i-1)!x^i}{i!}=-\sum\limits_{i=1}^\infin\frac{(-x)^i}{i}$：

$\begin{aligned} \ln(\operatorname{Weigh}(F(x)))&=\sum\limits_{i=0}^\infin f_i\ln(1+x^i)\\ &=-\sum\limits_{i=0}^\infin f_i\sum\limits_{j=1}^\infin\frac{(-x^i)^j}{j}\\ &=-\sum\limits_{i=1}^\infin \frac{(-1)^i}{i}\sum\limits_{j=0}^\infin f_jx^{ij}\\ &=-\sum\limits_{i=1}^\infin \frac{(-1)^i}{i}F(x^i)\\ \end{aligned}$

那么：

$\operatorname{Weigh}(F(x))=\exp\left(-\sum\limits_{i=1}^\infin \frac{(-1)^i}{i}F(x^i)\right)$

$\operatorname{Euler}$ 变换

无限制。

类似 Weigh，大小和放球方式都相同的盒子一起处理，相当于处理排序后的盒子。同种盒子允许有任意个可以通过套一层 Invert 变换来实现：

$\mathcal{E}(F(x))=\prod\limits_{i=0}^\infin \left(\frac{1}{1-x^i}\right)^{f_i}\\$

同样是 $\ln$ 再 $\exp$：

$\begin{aligned} \ln(\mathcal{E}(F(x)))&=\sum\limits_{i=0}^\infin f_i\ln\left(\frac{1}{1-x^i}\right)\\ &=-\sum\limits_{i=0}^\infin f_i\ln(1-x^i)\\ &=\sum\limits_{i=0}^\infin f_i\sum\limits_{j=1}^\infin\frac{x^{ij}}{j}\\ &=\sum\limits_{i=1}^\infin \frac{F(x^i)}{i} \end{aligned}$

所以：

$\mathcal{E}(F(x))=\exp\left(\sum\limits_{i=1}^\infin \frac{F(x^i)}{i}\right)$

复合变换

考虑另一个 OGF $H(x)=\sum\limits_{i=0}^\infin h_ix^i$，考虑复合函数 $H(F(x))$ 和 $H(G(x))$ 的意义：

• $[x^n]H(F(x))=[x^n]\sum\limits_{i=0}^\infin h_iF(x)^i$：$n$ 个无标号小球放入若干个有标号盒子中，每个盒子放 $i$ 个小球均有 $[x^i]F(x)$ 种方案。这若干个盒子放入一个大箱子中，大箱子中放 $i$ 个盒子有 $h_i$ 种方案；
• $[x^n]H(G(x))=[x^n]\sum\limits_{i=0}^\infin h_iG(x)^i$：$n$ 个有标号小球放入若干个有标号盒子中，每个盒子放 $i$ 个小球均有 $[x^i]G(x)$ 种方案。这若干个盒子放入一个大箱子中，大箱子中放 $i$ 个盒子有 $h_i$ 种方案；

注意 $H(x)$ 也可以是 EGF，并且可以复合再复合。

比较经典的是有标号有根树的 EGF $T(x)$ 复合上任意生成函数。

Part 4 各种变换的计算

• $\operatorname{???}(x)$ 和 $\operatorname{Invert}(x)$：求逆即可；

• $\operatorname{Exp}(x)$：直接多项式 exp；

• $\operatorname{Weigh}(x)$ 和 $\mathcal{E}(x)$：暴力调和级数；

• 复合变换：

  牛顿迭代。以有标号有根树的 EGF $T(x)=1+\sum\limits_{i=1}^\infin i^{i-1}\frac{x^i}{i!}$ 为例，考虑另一个生成函数 $H(x)$（不管是 OGF 还是 EGF），求解 $T(H(x))$。

  显然有 $T(x)=x\exp(T(x))$，那么有 $T(H(x))=H(x)\exp(T(H(x)))$。

  根据牛迭式子，构造 $P(A(x))=A(x)-H(x)\exp(A(x))$。

  $P(A(x))$ 很好算，但是求导的时候要注意实际上求的是关于 $A(x)$ 的偏导，即把 $A(x)$ 外的东西都看作常数，所以有：$P'(A(x))=1-H(x)\exp(A(x))$。

  那么牛顿迭代求解即可。

  求出来 $T(H(x))$ 后可以 $O(n)$ 算出有标号无根树复合 $H(x)$ 的结果，这样就可以算点双边双什么的了。

Part 5 拓展应用

无标号有根树计数

设无标号有根树个数的 OGF 为 $T(x)$，那么显然有 $T(x)=x\mathcal{E}(T(x))=x\exp\left(\sum\limits_{i=1}^\infin \frac{T(x^i)}{i}\right)$。那么构造 $P(T(x))=\ln\left(\frac{T(x)}{x}\right)-\sum\limits_{i=1}^\infin \frac{T(x^i)}{i}$。

注意到牛迭的前提是已知 $T_*(x)\equiv T(x)\pmod{x^\frac{n}{2}}$，要求 $\frac{P(T_*(x))}{P'(T_*(x))}\pmod{x^n}$。那么显然 $B(x)=\sum\limits_{i\ge 2}^\infin \frac{T_*(x^i)}{i}\mod{x^n}$ 是已知的，则有：

$P(T_*(x))\equiv \ln\left(\frac{T_*(x)}{x}\right)-T_*(x)-B(x)\pmod{x^n}\\ P'(T_*(x))\equiv \frac{1}{T_*(x)}-T_*(x)\pmod{x^n}\\$

发现 $[x^0]T_*(x)=0$，直接牛迭会解出 $0$，所以考虑用牛迭求解 $A(x)=\frac{T(x)}{x}$：

$P(A_*(x))\equiv \ln\left(A_*(x)\right)-xA_*(x)-B(x)\pmod{x^n}\\ P'(A_*(x))\equiv \frac{1}{A_*(x)}-x\pmod{x^n}\\$

注意到 $B(x)$ 可以在倍增的时候动态调和级数维护，所以 $\ln$ 加上两次求逆，再动态维护 $B(x)$ 即可。

时间复杂度 $O(n\log n)$，常数略大。

这个东西变成无根也很简单，只要减掉根不是重心的情况即可。