符号化方法小记
zhiyangfan
·
·
个人记录
符号化方法
OI wiki 新增加的一页，在 GF 计数领域非常有用，所以总结一下。
一些符号约定
符号化方法是把组合对象（比如树，字符串，图等我们关心它组合意义的东西）转化为 GF 形式表达的一种方法，考虑把在这些组合对象组成的集合上进行的操作，变成在 GF 上进行的操作，从而大大提升效率。一般地，我们定义组合类：
(\mathcal{A},\lvert\cdot\rvert)
其中 \mathcal{A} 为组合对象组成的集合，\lvert\cdot\rvert 是一个单元操作，把一个组合对象映射为一个非负整数。举个例子，比如对于一棵树，我们关心它的结点数，所以就定义 |t| 为 t 这棵树的结点数量。我们定义 \mathcal{A}_n=\{\alpha\in\mathcal{A}||\alpha|=n\}。
对于组合类 (\mathcal{A},\lvert\cdot\rvert) ，其对应的 OGF 为：
A(z)=\sum_{\alpha\in \mathcal{A}}z^{|\alpha|}=\sum_{n\ge 0}a_nz^n
对应的 EGF 为：
\hat{A}(z)=\sum_{\alpha\in \mathcal{A}}\dfrac{z^{|\alpha|}}{|\alpha|!}=\sum_{n\ge 0}\dfrac{a_nz^n}{n!}
其中 a_n=\operatorname{card}(\mathcal{A}_n)，\operatorname{card} 表示集合的基数。一般来说，OGF 用于无标号的情况，EGF 用于有标号的情况。
定义中性对象 \epsilon 满足 |\epsilon|=0，和中性集合 \mathcal{E}=\{\epsilon\}，其对应的 OGF，EGF 为：
\mathcal{E}(z)=\hat{\mathcal{E}}(z)=1
定义原子对象 \circ 满足 \lvert\circ\rvert=1，和原子集合 \mathcal{Z}=\{\circ\}，其对应的 OGF，EGF 为：
\mathcal{Z}(z)=\hat{\mathcal{Z}}(z)=z
显然我们能得到结论，\forall\mathcal{A}，都有 \mathcal{A}\cong\mathcal{A}\times\mathcal{E}\cong\mathcal{E}\times \mathcal{A}，其中我们称两个组合集 \mathcal{A},\mathcal{B} 满足 \mathcal{A}\cong\mathcal{B} 当且仅当它们不平凡同构。
无标号
本部分介绍的所有操作是基于无标号的，所以对应的 GF 均采用 OGF。
不相交并
对于两个组合类的并 \mathcal{A},\mathcal{B}，如果我们单纯将它记为：
\mathcal{A}+\mathcal{B}
即简单的拼接，如果 \mathcal{A}\cap\mathcal{B}\ne\emptyset，就会与不相交的前提相违背。所以我们把它记为：
(\mathcal{E}_1\times\mathcal{A})+(\mathcal{E}_2\times\mathcal{B})
即给两个乘上不同的中性对象，不改变集合的元素本质，但给它们“染上了颜色”，从而不管是否有 \mathcal{A}\cap\mathcal{B}=\emptyset，都可以直接拼接。而对应的 OGF 为：
A(z)+B(z)=\sum_{\alpha\in\mathcal{A}}z^{|\alpha|}+\sum_{\beta\in\mathcal{B}}z^{|\beta|}=\sum_{n\ge 0}(a_n+b_n)z^n
即两个集合对应 OGF 的幂级数加法。
笛卡尔积
我们定义两个集合的笛卡尔积 \mathcal{A}\times\mathcal{B} 为：
\mathcal{A}\times\mathcal{B}=\{(\alpha,\beta)|\alpha\in\mathcal{A},\beta\in\mathcal{B}\}
其中如果 \gamma=(\alpha_1,\alpha_2,\cdots,\alpha_n)，则我们记 |\gamma|=|\alpha_1|+|\alpha_2|+\cdots+|\alpha_n|。通过定义可以找到对应的 OGF：
A(z)B(z)=\sum_{(\alpha,\beta)\in(\mathcal{A}\times\mathcal{B})}z^{|\alpha|+|\beta|}=\sum_{n\ge 0}\sum_{i+j=n}a_ib_jz^n
即两个集合对应 OGF 的幂级数乘法。
序列构造
我们定义一个集合的序列构造 \operatorname{SEQ}(\mathcal{C}) 为：
\operatorname{SEQ}(\mathcal{C})=\{\epsilon\}+\mathcal{C}+\mathcal{C}^2+\mathcal{C}^3+\cdots
其中为了保证构造出的集合合理，必须有 \mathcal{C}_0=\emptyset。感性理解就是在这个集合里选 0 个的方案，选 1 个的方案，选 2 个的方案等等的并，且选择组成的是序列，即顺序有所谓。对应的 OGF 为：
\operatorname{SEQ}(C(z))=\sum_{n\ge 0}C^n(z)=\dfrac{1}{1-C(z)}
循环构造
我们定义一个集合的循环构造 \operatorname{CYC}(\mathcal{B}) 为：
\operatorname{CYC}(\mathcal{B})=\operatorname{SEQ}(\mathcal{B})/\mathbf{S}
其中 \mathbf{S} 为一个等价关系，表示二者循环同构，/\mathbf{S} 表示把原集合按照在这个等价意义下等价的元素剔除。感性理解就是在 \operatorname{SEQ}(\mathcal{B}) 的集合中，去掉循环同构的序列。其对应的 OGF 不那么显然，根据 OI wiki，式子是：
\operatorname{CYC}(B(z))=\sum_{n\ge 1}\dfrac{\varphi(n)}{n}\ln\dfrac{1}{1-B(z^n)}
其中 \varphi 为欧拉函数。
可重集构造
我们定义一个集合的可重集构造 \operatorname{MSET}(\mathcal{A}) 为：
\operatorname{MSET}(\mathcal{A})=\operatorname{SEQ}(\mathcal{A})/\mathbf{R}
其中 \mathbf{R} 为一个等价关系，表示两个序列对应同一个可重集，/\mathbf{R} 表示把原集合按照该等价关系相同的元素剔除。感性来看就是在序列构造的基础上，要求组成的是可重集，即顺序无所谓。除定义外，我们还能得到这样的递推式：
\operatorname{MSET}(\{\alpha_0,\alpha_1,\cdots\alpha_n\})=\operatorname{MSET}(\{\alpha_0,\alpha_1,\cdots\alpha_{n-1}\})\times\operatorname{SEQ}(\{\alpha_n\})
表示在原有的生成的可重集内，每个都加入若干个 \alpha_n。更进一步，我们能发现：
\operatorname{MSET}(\mathcal{A})=\prod_{\alpha\in\mathcal{A}}\operatorname{SEQ}(\{\alpha\})
因为 \operatorname{SEQ} 对应的 OGF 已知，所以 \operatorname{MSET} 对应的 OGF 为：
\operatorname{MSET}(A(z))=\prod_{\alpha\in\mathcal{A}}(1-z^{|\alpha|})^{-1}=\prod_{n\ge 1}(1-z^n)^{-a_n}
不要忘了 \operatorname{SEQ} 要求不能出现大小为 0 的元素。
进一步地，我们还能通过取对数继续化简这个 OGF（具体过程可以参考我的 一篇题解）：
\operatorname{MSET}(A(z))=\exp\left(\sum_{n\ge 1}\dfrac{A(z^n)}{n}\right)
可重集构造又被称作 Euler 变换。
幂集构造
我们定义一个集合的幂集构造 \operatorname{PSET}(\mathcal{B}) 为其所有子集的并。有递推式：
\operatorname{PSET}(\{\beta_0,\beta_1,\cdots,\beta_n\})=\operatorname{PSET}(\{\beta_0,\beta_1,\cdots,\beta_{n-1}\})\times(\{\epsilon,\beta_n\})
即剩下一个元素可以选，也可以不选。进一步地，我们有：
\operatorname{PSET}(\mathcal{B})=\prod_{\beta\in\mathcal{B}}(\{\epsilon,\beta\})
对应的 OGF 为：
\operatorname{PSET}(B(z))=\prod_{\beta\in\mathcal{B}}(1+z^{|\beta|})=\prod_{n\ge 1}(1+z^n)^{b_n}
可以发现与 \operatorname{MSET} 的非常像，仅仅是换了几个符号，所以另一种 \exp 的形式也可以类似地得出：
\operatorname{PSET}(B(z))=\exp\left(\sum_{n\ge 1}\dfrac{(-1)^{n-1}B(z^n)}{n}\right)
根据定义容易得到：
\operatorname{PSET}(\mathcal{B})\subset\operatorname{MSET}(\mathcal{B})
带限制的情况
上面所有的讨论都是基于不限组成部分的情况，但如果要求原序列生成的可重集个数满足某种限制——比如恰为 k——那就无法解决了。定义 \mathfrak{K} 为上述 \operatorname{SEQ,MSET,PSET,CYC} 的其中的一种操作，定义以下三种限制：
\mathfrak{K}_{\ge l}(\mathcal{B})\qquad\mathfrak{K}_{k}(\mathcal{B})\qquad\mathfrak{K}_{l..r}(\mathcal{B})
为组成部分大于等于 l，恰等于 k，和位于 l..r 中。以 \mathcal{A}=\mathfrak{K}_{l..r}(\mathcal{B}) 为例，这要求：
\forall\alpha\in\mathcal{A},\alpha=\{(\beta_0,\beta_1,\cdots,\beta_k)|\beta\in\mathcal{B}\},l\le k\le r
考虑引入二元 GF 来解决这个问题，如果设 \mathcal{X}(\alpha) 表示组成 \alpha 的元素个数，则我们定义 A_{n,k} 为：
A_{n,k}=\operatorname{card}(\{\alpha\in\mathcal{A}||\alpha|=n,\mathcal{X}(\alpha)=k\})
则对应的二元 GF 为：
A(z,u)=\sum_{n,k}A_{n,k}u^kz^n=\sum_{\alpha\in\mathcal{A}}u^{\mathcal{X}(\alpha)}z^{|\alpha|}
容易发现，\mathfrak{K}_{l..r} 的限制只需要提取出 u^{l..r} 的系数，就能得到对应的 OGF，其他两个限制是类似的。
具体来看，对于 \operatorname{SEQ}(\mathcal{B})：
A(z,u)=\sum_{n,k}A_{n,k}z^nu^k=\sum_{k\ge 0}B^k(z)u^k=\dfrac{1}{1-uB(z)}
其中 A_{n,k}z^n=B^k(z) 是由于对于 \operatorname{SEQ} 构造，B(z)^k 就表示组成部分为 k 个的 OGF。这样显然有：
[u^l]A(z,u)=B^l(z)
对于 \operatorname{MSET}(\mathcal{B})：
A(z,u)=\prod_{n}(1-uz^n)^{-b_n}
只是给每一个元素增加了一个 u，表示这个元素单独的时候表示 1 个元素，从而两个相乘表示拼接的时候也会把 u 的指数相加。可以用类似的方法得到 \exp 形式：
A(z,u)=\exp\left(\sum_{n\ge 1}\dfrac{u^nB(z^n)}{n}\right)
把 \exp 展开后即可提取 u^l 的系数。
注意在这种情况下，对于 b_0 的定义很重要。如果 b_0=1，则有可能出现较多的常数项不便于计算。
对于 \operatorname{PSET}(\mathcal{B})，可以采用类似的思路：
A(z,u)=\prod_{n}(1+uz^n)^{b_n}
$$A(z,u)=\exp\left(\sum_{n\ge 1}\dfrac{(-1)^{n-1}u^nB(z^n)}{n}\right)$$
依然是把 $\exp$ 展开提取系数。
#### 一些例题
> [loj#6268. 分拆数](https://loj.ac/p/6268)
>
> 定义 $f(i)$ 为把 $i$ 表示成若干正整数之和的方案数，正整数之间的顺序无所谓。求 $f(1\sim10^5)$，答案对 $998,244,353$ 取模。
如果我们定义组合类 $(\mathcal{I},\lvert\cdot\rvert)$，其中 $\mathcal{I}=\mathbb{N}_+$，$\lvert i \rvert=i$，则我们发现题目里给出的分拆其实相当于：
$$\operatorname{MSET}(\mathcal{I})$$
因为不同的数组成成一个新的组合类，它的大小恰等于各个组分之和，即对于正整数的分拆，又因为顺序无所谓，所以用 $\operatorname{MSET}$。具体算的方法，可以考虑把 $\operatorname{MSET}$ 的形式展开一下：
$$\operatorname{MSET}(I(z))=\exp\left(\sum_{n\ge 1}\dfrac{I(z^n)}{n}\right)=\exp\left(\sum_{n\ge 1}\sum_{k\ge 1}\dfrac{i_kz^{kn}}{n}\right)$$
这样每个 $i_k$ 会对所有 $k$ 的倍数做贡献，枚举倍数预处理出多项式就可以直接做 $\exp$ 了，时间复杂度 $\mathcal{O}(n\log n)$。
```cpp
int main()
{
int n, m = 1; scanf("%d", &n); while (m <= n) m <<= 1;
for (int i = 1; i <= n; ++i)
for (int j = i; j < m; j += i) (F[j] += ksm(j / i, mod - 2)) %= mod;
getExp(F, G, m);
for (int i = 1; i <= n; ++i) printf("%d\n", G[i]);
return 0;
}
```
> [洛谷 P5900 无标号无根树计数](https://www.luogu.com.cn/problem/P5900)
>
> 求 $n$ 个点的无标号无根树数量，答案对 $998244353$ 取模。($1\le n\le 2\times10^5$)
发现如果我们求的是有根树，则钦定一个根后，剩下的点其实是分成若干集合，变成子树，且各个子树又是递归结构。所以定义组合类 $(\mathcal{T},\lvert\cdot\rvert)$，其中 $\mathcal{T}$ 表示所有无标号有根树的集合，$|t|$ 表示这棵树结点大小，则：
$$\mathcal{T}=\{\circ\}\times\operatorname{MSET}(\mathcal{T})$$
展开成 OGF 就可以做了：
$$\operatorname{MSET}(T(z))=z\exp\left(\sum_{n\ge1}\dfrac{T(z^n)}{n}\right)$$
具体做法见我的 [一篇题解](https://www.luogu.com.cn/blog/i-am-zhiyangfan/solution-p5900)。
> [烷基计数 加强版 加强版](https://loj.ac/p/6538)
>
> 求 $n$ 个点的每个点度数不超过 $4$ 且根的度数不超过 $3$ 的有根树的数目。($1\le n\le 10^5$)
这道题一个显然的想法是设组合类 $(\mathcal{T},\lvert\cdot\rvert)$，与上一道题类似的意义，有等式：
$$\mathcal{T}=\{\circ\}\times\operatorname{MSET}_{0..3}(\mathcal{T})$$
不幸的是，如果按照这个等式进行 OGF 的展开，会得到一个非常长的式子，非常不便于计算。注意到这个等式必须要求 $\operatorname{MSET}$ 取 $0..3$ 是因为 $\mathcal{T}$ 内没有 $\epsilon$ 元素，这样的话，满足度数 $\le 3$ 就必须显式表示。而如果我们定义 $\hat{\mathcal{T}}=\mathcal{T}+\{\epsilon\}$，则会有：
$$\hat{\mathcal{T}}=\{\epsilon\}+\{\circ\}\times\operatorname{MSET}_3(\hat{\mathcal{T}})$$
而这个式子展开就会方便很多了。考虑把 $\exp$ 展开：
$$\begin{aligned}\operatorname{MSET}_3(T(z))&=[u^3]\exp\left(\sum_{n\ge 1}\dfrac{u^nT(z^n)}{n}\right)\\&=[u^3]\sum_{i\ge 0}\dfrac{\left(\sum_{n\ge 1}\dfrac{u^nT(z^n)}{n}\right)^i}{i!}\\&=[u^3]1+[u^3]\left(\cdots+\dfrac{u^3T(z^3)}{3}+\cdots\right)+[u^3]\dfrac{\left(\dfrac{uT(z)}{1}+\dfrac{u^2T(z^2)}{2}+\cdots\right)^2}{2}\\&+[u^3]\dfrac{\left(\dfrac{uT(z)}{1}+\cdots\right)^3}{6}\\&=\dfrac{T(z^3)}{3}+\dfrac{T(z)T(z^2)}{2}+\dfrac{T^3(z)}{6}\end{aligned}$$
这样能得到：
$$T(z)=1+\dfrac{z}{6}(2T(z^3)+3T(z)T(z^2)+T^3(z))$$
可以用半在线卷积或者牛顿迭代分别在 $\mathcal{O}(n\log^2n)$ 和 $\mathcal{O}(n\log n)$ 的时间内求解。
```cpp
inline void copy(int* f, int* g, int n) { for (int i = 0; i < n; ++i) g[i] = f[i]; }
inline void clear(int* f, int n) { for (int i = 0; i < n; ++i) f[i] = 0; }
inline void cdq(int l, int r)
{
if (l + 1 == r) return (l % 3 == 1) ? ((A[l] += (ll)A[l / 3] * inv3 % mod) %= mod, void()) : void();
int mid = (l + r) >> 1; cdq(l, mid); init(r - l);
copy(A + l, F, mid - l); clear(F + mid - l, lim - mid + l);
copy(A, G, r - l); clear(G + r - l, lim - r + l);
for (int i = 0; i < lim; ++i) H[i] = 0;
for (int i = 0; i < r - l; ++i) if (!(i & 1)) H[i] = A[i / 2];
NTT(F, lim, 1); NTT(G, lim, 1); NTT(H, lim, 1);
for (int i = 0; i < lim; ++i)
F[i] = ((ll)F[i] * H[i] % mod * inv2 % mod + (ll)F[i] * G[i] % mod * G[i] % mod * inv2 % mod * (!l ? inv3 : 1) % mod) % mod;
NTT(F, lim, mod - 2);
for (int i = mid; i < r; ++i) (A[i] += F[i - l - 1]) %= mod;
cdq(mid, r);
}
int main()
{
int m; scanf("%d", &m); while (n <= m) n <<= 1; A[0] = 1;
cdq(0, n); printf("%d\n", A[m]); return 0;
}
```
顺便提一句，如果按照 $\mathcal{T}=\{\circ\}\times\operatorname{MSET}_{0..3}(\mathcal{T})$ 展开得到的是：
$$T(z)=\dfrac{z}{6}(1+6T(z)+3T^2(z)+3T(z^2)+3T(z)T(z^2)+2T(z^3)+T^3(z))$$
如果把 $T(z)$ 换为 $T(z)+1$，那就跟上面那个式子一样了。所以常数项一般来说处理为 $0$ 会更加方便，甚至有时候必须处理为 $0$（比如上题无标号无根树，因为没有限制，所以一旦不处理为 $0$，那常数项就会爆炸）
### 有标号
本部分介绍的所有内容是基于有标号的，所以对应的 GF 采用 EGF。
#### 一些有标号的例子
对于排列组成的组合类 $(\mathcal{P},\lvert\cdot\rvert)$，定义 $|p|$ 为排列的长度，则其 EGF 为：
$$\hat{P}(z)=\sum_{p\in\mathcal{P}}\dfrac{z^{|p|}}{|p|!}=\sum_{n\ge 0}\dfrac{n!z^n}{n!}=\dfrac{1}{1-z}$$
对于圆排列组成的组合类 $(\mathcal{C},\lvert\cdot\rvert)$，定义 $|c|$ 为圆排列的长度，则其 EGF 为：
$$\hat{C}(z)=\sum_{c\in\mathcal{C}}\dfrac{z^{|c|}}{|c|!}=\sum_{n\ge 0}\dfrac{(n-1)!z^n}{n!}=\ln\dfrac{1}{1-z}$$
能看出 $\exp \hat{C}(z)=\hat{P}(z)$。
对于图 $G=(V,E)$，且 $|E|=0$，定义其组合类 $(\mathcal{U},\lvert\cdot\rvert)$，定义 $|u|=|V|$，则其 EGF 为：
$$\hat{U}(z)=\sum_{u\in\mathcal{U}}\dfrac{z^{|u|}}{|u|!}=\sum_{n\ge 0}\dfrac{z^n}{n!}=e^z$$
这是由于完全没有边的图，相同大小的点集仅对应一个。
#### 集合的有标号乘法
首先我们要知道，把两个元素做有标号乘法会有什么结果。比如 $\beta,\gamma$ 为两个有标号元素，则我们定义二者的有标号乘法为这两个元素拼接在一起，**并重新标号**。而对一个元素重新标号有两种情况，要么是把标号的值域扩大，要么缩小，这导出了对元素有标号乘法两种等价的定义：
$$\beta\ast\gamma=\{(\beta',\gamma')|(\beta',\gamma') 的标号是良定义的,\rho(\beta')=\beta,\rho(\gamma')=\gamma\}$$
其中 $\rho$ 表示将标号的值域缩小后的对应。
$$\beta\ast\gamma=\{(e(\beta),f(\gamma))|\operatorname{Im}(e)\cap\operatorname{Im}(f)=\emptyset,\operatorname{Im}(e)\cup\operatorname{Im}(f)=\{1,2,\cdots,|\beta|+|\gamma|\}\}$$
其中 $f,e$ 表示将标号的值域扩大后的对应，$\operatorname{Im}(e)$ 表示对应到的值的集合。可能有点难理解，举个例子吧，比如将一个三角形 $1-2-3$ 和一个线段 $1-2$ 乘在一起会得到 $10$ 个结果：
$$\begin{aligned}&(1-2-3,4-5),(1-2-4,3-5),(1-2-5,3-4),(1-3-4,2-5),(1-3-5,2-4)\\&(1-4-5,2-3),(2-3-4,1-5),(2-3-5,1-4),(2-4-5,1-3),(3-4-5,1-2)\end{aligned}$$
可以观察到，两个集合 $\beta,\gamma$ 大小分别为 $n_1,n_2$，如果令 $n=n_1+n_2$，则：
$$\operatorname{card}(\beta\ast\gamma)=\dbinom{n}{n_1,n_2}$$
有了这个定义，我们就能得到两个集合的有标号乘法 $\mathcal{B}\ast\mathcal{C}$ 为：
$$\mathcal{B}\ast\mathcal{C}=\bigcup_{\beta\in\mathcal{B},\gamma\in\mathcal{C}}(\beta\ast\gamma)$$
对应的 EGF 操作为：
$$\hat{A}(z)=\hat{B}(z)\times \hat{C}(z)\iff a_n=\sum_{|\beta|+|\gamma|=n}\dbinom{|\beta|+|\gamma|}{|\beta|,|\gamma|}=\sum_{n_1+n_2=n}\dbinom{n}{n_1,n_2}b_{n_1}c_{n_2}$$
其中：
$$\dbinom{n}{n_1,n_2,\cdots,n_k}=\dfrac{n!}{n_1!n_2!\cdots n_k!}$$
即 EGF 的幂级数乘法。容易发现这个乘法满足结合律：
$$\mathcal{A}\ast(\mathcal{B}\ast\mathcal{C})=(\mathcal{A}\ast\mathcal{B})\ast\mathcal{C}$$
#### 序列构造
我们定义一个集合的序列构造 $\operatorname{SEQ}(\mathcal{B})$ 为：
$$\operatorname{SEQ}(\mathcal{B})=\{\epsilon\}+\mathcal{B}+\mathcal{B}^2+\mathcal{B}^3+\cdots$$
其中 $\mathcal{B}^n=(\mathcal{B}\ast\mathcal{B}\ast\mathcal{B}\ast\cdots)$，共 $n$ 个 $\mathcal{B}$。定义 $k$ 序列构造 $\operatorname{SEQ}_k(\mathcal{B})$ 为：
$$\operatorname{SEQ}_k(\mathcal{B})=\mathcal{B}^k$$
可以找到对应的 EGF：
$$\operatorname{SEQ}(\hat{B}(z))=\dfrac{1}{1-\hat{B}(z)},\operatorname{SEQ}_k(\hat{B}(z))=\hat{B}^k(z)$$
$\operatorname{SEQ}$ 构造依然要求 $\mathcal{B}_0=\emptyset$。
感性理解就是选取 $0,1,2,\cdots$ 个元素构成的有标号，顺序有所谓的序列。
#### 集合构造
我们定义一个集合的集合构造 $\operatorname{SET}(\mathcal{B})$ 为：
$$\operatorname{SET}(\mathcal{B})=\{\epsilon\}+\mathcal{B}+\operatorname{SET}_1(\mathcal{B})+\operatorname{SET}_2(\mathcal{B})+\cdots=\bigcup_{k\ge 0}\operatorname{SET}_k(\mathcal{B})$$
其中 $k$ 集合构造 $\operatorname{SET}_k(\mathcal{B})=\operatorname{SEQ}_k(\mathcal{B})/\mathbf{R}$，$\mathbf{R}$ 为等价关系，表示两个序列中一个是另一个的排列，$/\mathbf{R}$ 表示去掉等价的元素。可以找到对应的 EGF：
$$\operatorname{SET}_k(\hat{B}(z))=\dfrac{1}{k!}\hat{B}^k(z),\operatorname{SET}(\hat{B}(z))=\sum_{k\ge 0}\dfrac{1}{k!}\hat{B}^k(z)=\exp (\hat{B}(z))$$
注意到所有东西都是有标号的，所以所有的数都是不同的，这样的话，$\operatorname{MSET,PSET}$ 都会对应到 $\operatorname{SET}$，即它们都是等价的。感性理解就是选取 $0,1,2,\cdots$ 个元素构成的有标号，顺序无所谓的序列。
#### 循环构造
我们定义一个集合的循环构造 $\operatorname{CYC}(\mathcal{B})$ 为：
$$\operatorname{CYC}(\mathcal{B})=\{\epsilon\}+\operatorname{CYC}_1(\mathcal{B})+\operatorname{CYC}_2(\mathcal{B})+\cdots=\bigcup_{k\ge 0}\operatorname{CYC}_k(\mathcal{B})$$
其中 $k$ 循环构造 $\operatorname{CYC}_k=\operatorname{SEQ}_k/\mathbf{S}$，$\mathbf{S}$ 为等价关系，表示两个序列循环同构。这样可以找到对应的 EGF：
$$\operatorname{CYC}_k(\hat{B}(z))=\dfrac{1}{k}\hat{B}^k(z),\operatorname{CYC}(\hat{B}(z))=\sum_{k\ge 0}\dfrac{1}{k}\hat{B}^k(z)=\ln\dfrac{1}{1-\hat{B}(z)}$$
通过以上这些操作，我们可以构造出一开始举出的三个例子 $\mathcal{U,P,S}$：
$$\mathcal{P}=\operatorname{SEQ}(\mathcal{Z}),\mathcal{U}=\operatorname{SET}(\mathcal{Z}),\mathcal{C}=\operatorname{CYC}(\mathcal{Z})$$
受这个启发，可以构造出的更多操作
#### 满射
满射，即从集合 $\mathcal{A}$ 到集合 $\mathcal{B}$ 的一种函数，且每个值至少用到一次。我们定义满射集合 $\mathcal{R}$ 为：
$$\mathcal{R}=\operatorname{SEQ}\{\operatorname{SET}_{\ge 1}(\mathcal{Z})\}$$
如果给出一个 $r\ge 1$，我们定义 $\mathcal{R}^{(r)}_n$ 为从 $[1\cdots n]$ 到 $[1\cdots r]$ 的满射的集合，一个例子 $\mathcal{R}_9^{(5)}$ 的元素之一：
$$\phi=(1\rightarrow \mathbf{2},2\rightarrow\mathbf{1},3\rightarrow\mathbf{2},4\rightarrow\mathbf{3},5\rightarrow\mathbf{5},6\rightarrow\mathbf{3},7\rightarrow\mathbf{5},8\rightarrow\mathbf{3},9\rightarrow\mathbf{4})$$
注意如果把 $9\rightarrow\mathbf{4}$ 换为 $9\rightarrow\mathbf{3}$，$\phi$ 就不是个满射。此外，我们定义：
$$\mathcal{R}^{(r)}=\bigcup_{n}\mathcal{R}_{n}^{(r)}$$
注意到 $\mathcal{R}^{(r)}$ 可以用一个 $r$ 元组集合，且它们的并集是 $A$ 集合表示：
$$(\phi^{-1}(1),\phi^{-1}(2),\cdots,\phi^{-1}(r))$$
即 $B$ 集合对应的 $A$ 集合的元素的集合，上面举的例子就是：
$$(\{2\},\{1,3\},\{4,6,8\},\{9\},\{5,7\})$$
这样就可以找到对应的 EGF 了：
$$\mathcal{R}^{(r)}=\operatorname{SEQ}_r\{\operatorname{SET}_{\ge 1}(\mathcal{Z})\}\Rightarrow \hat{R}^{(r)}(z)=(e^z-1)^r$$
这样 $n![z^n]\hat{R}^{(r)}=R^{(r)}_n$，二项式定理爆拆：
$$R_n^{(r)}=n![z^n]\sum_{j=0}^r\dbinom{r}{j}(-1)^je^{(r-j)z}=\sum_{j=0}^r\dbinom{r}{j}(-1)^j(r-j)^n$$
注意到 $\mathcal{R}=\operatorname{SEQ}(\operatorname{SET}_{\ge 1}(\mathcal{Z}))$，这样可以导出：
$$\hat{R}(z)=\dfrac{1}{2-e^z}$$
简单推导一下：
$$\hat{R}(z)=\dfrac{1}{2}\dfrac{1}{1-\frac{1}{2}e^z}=\sum_{l\ge 0}\dfrac{e^{lz}}{2^{l+1}}$$
可以得到：
$$R_n=n![z^n]\hat{R}(z)=\dfrac{1}{2}\sum_{l\ge 0}\dfrac{l^n}{2^l}$$
#### 分割集合
定义 $S^{(r)}_n$ 表示把集合 $\{1,2,\cdots,n\}$ 分成 $r$ 个不相交集合的方案数，定义 $\mathcal{S}^{(r)}=\bigcup_n \mathcal{S}^{(r)}_n$，这个组合集对应的元素为一种分割，分割的每一部分被叫做一个块。而一个分割可以被一个有标号类的集合表示（每个代表一个块），所以有：
$$\mathcal{S}^{(r)}=\operatorname{SET}_r\{\operatorname{SET}_{\ge 1}(\mathcal{Z})\}\Rightarrow \hat{S}^{(r)}(z)=\dfrac{1}{r!}(e^z-1)^r$$
可以发现，$S^{(r)}_n=\dfrac{1}{r!}R^{(r)}_n$。从组合意义可以看出，一个 $r$ 分割恰好对应 $r!$ 个 $r$ 满射，两个满射在分割意义下是等价的，当且仅当一个是另一个的排列。
容易发现，分割数跟第二类斯特林数有很大的关系，即：
$$S_{n}^{(r)}=\begin{Bmatrix}n\\r\end{Bmatrix}$$
根据第二类斯特林数的定义可以得出。所以有：
$$R_n=\sum_{r\ge 0}r!\begin{Bmatrix}n\\r\end{Bmatrix},S_n=\sum_{r\ge 0}\begin{Bmatrix}n\\r\end{Bmatrix}$$
观察到 $S_n$ 其实就是贝尔数。
注意到 $\mathcal{S}=\operatorname{SET}\{\operatorname{SET}_{\ge 1}(\mathcal{Z})\}$，这样可以导出：
$$\hat{S}(z)=e^{e^z-1}$$
简单推导一下：
$$\hat{S}(z)=\dfrac{1}{e}e^{e^z}=\dfrac{1}{e}\sum_{l\ge 0}\dfrac{e^{lz}}{l!}$$
可以得到：
$$S_n=n![z^n]\hat{S}(z)=\dfrac{1}{e}\sum_{l\ge 0}\dfrac{l^n}{l!}$$
#### 平面图
这个 "Alignments" 我也不知道怎么翻译好，于是就直译了。一个平面图被定义为一个良标号的圆组成的序列，定义 $\mathcal{O}$ 为平面图的集合，则显然有：
$$\mathcal{O}=\operatorname{SEQ}\{\operatorname{CYC}(\mathcal{Z})\}\Rightarrow \hat{O}(z)=\dfrac{1}{1-\ln(1-z)^{-1}}$$
#### 排列
注意到一个排列其实就是若干圆排列的集合，可以从置换环的角度考虑，这样排列的集合 $\mathcal{P}$ 就有：
$$\mathcal{P}=\operatorname{SET}\{\operatorname{CYC}(\mathcal{Z})\}\cong\operatorname{SEQ}(\mathcal{Z})$$
能导出 EGF：
$$\hat{P}(z)=\exp\left(\ln\dfrac{1}{1-z}\right)=\dfrac{1}{1-z}$$
接下来就用刚刚的方法推导一些东西吧。
#### 树
树分为两种，一种是平面树，特点是子树之间有顺序，另一种是非平面树，特点是子树之间无顺序。此外，我们定义集合 $\Omega\in\mathbb{N}$ 为树的所有点的出度的集合，其中因为树有叶子，所以一定有 $0\in\Omega$。
对于平面有根树，本质上就是确定根之后，剩下的点分成若干部分变成子树，然后递归下去，所以对于平面有根树的集合 $\mathcal{A}$ 有：
$$\mathcal{A}=\mathcal{Z}\ast\operatorname{SEQ}_{\Omega}(\mathcal{A})$$
这样对应的 EGF 为：
$$\hat{A}(z)=z\sum_{w\in\Omega}\hat{A}^w(z)$$
容易发现这个和不带标号的平面有根树很像，具体来讲，不带标号的平面有根树个数为：
$$\dfrac{1}{n!}A_n$$
原因根据组合意义显然。而根据我不会的拉格朗日反演可以得到：
$$A_n=n![z^n]\hat{A}(z)=(n-1)![u^{n-1}]\left(\sum_{w\in\Omega}u^w\right)^n$$
而对于非平面有根树，思路类似，对于它的集合 $\mathcal{T}$，我们有：
$$\mathcal{T}=\mathcal{Z}\ast\operatorname{SET}_{\Omega}(\mathcal{T})$$
这样对应的 EGF 为：
$$\hat{T}(z)=z\sum_{w\in\Omega}\dfrac{\hat{T}^w(z)}{w!}$$
注意到如果 $\Omega=\mathbb{N}$，则有：
$$\hat{T}(z)=ze^{\hat{T}(z)}$$
可与通过我不会的拉格朗日反演得到：
$$T_n=n^{n-1}$$
如果我们考虑森林，其实就是把若干个树组成一个森林，且顺序无所谓，所以森林的集合 $\mathcal{F}$ 为：
$$\mathcal{F}=\operatorname{SET}\{\mathcal{T}\}$$
即 $\hat{F}(z)=\exp\hat{T}(z)$。
### 写在最后
本篇文章参考 [Analytic Combinatorics](http://algo.inria.fr/flajolet/Publications/books.html) 这本书的第一，二章，对原文内容做了很大简化，有需要的同学可以找来原书看。由于本人数学很差，所以如果有错还请请喷并指出qwq