组合物种 | Codeboy's Blog

形式陈述

组合物种把标号组合类的重标原则形式化。物种 $F$ 是从有限集合与双射组成的群胚到有限集合范畴的函子：它给每个有限集合 $U$ 指派 $F$ -结构集合 $F[U]$ ，并给每个双射 $\sigma:U\to V$ 指派重标映射

F[\sigma]:F[U]\longrightarrow F[V],

满足

F[\operatorname{id}_U]=\operatorname{id}_{F[U]}, \qquad F[\tau\circ\sigma]=F[\tau]\circ F[\sigma].

因此重标不改变结构，只改变原子的名字。令 $[n]=\{1,\ldots,n\}$ ，物种的标号计数与指数生成函数为

f_n=|F[n]|,\qquad F(z)=\sum_{n\ge0}f_n\frac{z^n}{n!}.

要同时记录对称性，定义循环指标

Z_F(p_1,p_2,\ldots) =\sum_{n\ge0}\frac1{n!} \sum_{\sigma\in S_n}|\operatorname{Fix}F[\sigma]| \prod_{j\ge1}p_j^{c_j(\sigma)},

其中 $c_j(\sigma)$ 是 $\sigma$ 的 $j$ -循环数。于是

F(z)=Z_F(z,0,0,\ldots),\qquad \widetilde F(z)=Z_F(z,z^2,z^3,\ldots),

后式是按同构类型计数的无标号生成函数。对每个 $n$ ，重标置换群 $S_n$ 作用于 $F[n]$ ；Burnside 引理把同构类型数写成 $n!$ 分之一的不动点总和。代入 $p_j=z^j$ 后，每项的总次数为 $\sum_j j c_j(\sigma)=n$ ，正好得到该轨道数作为 $z^n$ 系数。

直觉

只列出 $F[n]$ 还不足以说明标签怎样更名。物种把每一种重命名都纳入数据，并要求先重命名再重命名与一次完成得到同一结果。这一自然性排除了依赖标签拼写的伪结构，同时保留自同构：若某个置换固定结构，它就贡献到循环指标，告诉我们该结构拥有什么对称。

EGF 只看每个标签集上结构总数；循环指标则保留置换固定点信息，因此能在标号与无标号计数之间搭桥。两个物种可以有相同 EGF，却因对称性不同而拥有不同循环指标和不同无标号枚举。

例子与边界

集合物种 $E$ 在每个 $U$ 上只有一个结构，即集合 $U$ 本身。故

E(z)=e^z,\qquad Z_E=\exp\left(\sum_{k\ge1}\frac{p_k}{k}\right).

代入 $(p_1,p_2,\ldots)=(z,z^2,\ldots)$ 得

\widetilde E(z)=\exp\left(\sum_{k\ge1}\frac{z^k}{k}\right) =\frac1{1-z},

与“每个大小恰有一个无标号集合类型”一致。这一次计算同时展示 EGF 的 $e^z$ 与无标号 OGF 的 $(1-z)^{-1}$ 为何都正确，它们回答的是不同问题。

线性次序物种 $L$ 在 $U$ 上包含 $U$ 的全部线性排列，所以 $|L[n]|=n!$ 、 $L(z)=1/(1-z)$ 。集合物种与线性次序物种的无标号生成函数相同，但 EGF 不同；反过来也可构造 EGF 相同而循环指标不同的物种。任何只记录一条数列的定义都无法捕捉这些差别。

物种只允许双射作为标签变换，因为结构的搬运应可逆。若希望沿任意映射推进结构，需使用解析函子、容器或其他范畴化对象。无限标签集、无限结构和带权物种也有推广，但有限物种的局部有限性不能自动带到这些版本。

推论与应用

物种具有和、积、导数、指点以及代入等运算，并与生成函数运算相容。若 $G[\varnothing]=\varnothing$ ，代入 $F\circ G$ 把标签集分成若干非空块，在每块放一个 $G$ -结构，再在块集上放 $F$ -结构；标号 EGF 满足

(F\circ G)(z)=F(G(z)).

取 $F=E$ 就得到“组件的集合”，从而导出组合指数公式。循环指标下的对应运算是 plethystic 代入，它进一步产生无标号 SET 与 CYC 公式中的 $z^k$ 修正。物种因此不仅是优雅语言，也是检查标号分配、自动同构与对称修正是否遗漏的工具。

参考资料

André Joyal, “Une théorie combinatoire des séries formelles,” Advances in Mathematics 42(1), 1981, pp. 1–82。
François Bergeron, Gilbert Labelle, and Pierre Leroux, Combinatorial Species and Tree-like Structures, Cambridge University Press, 1998, Chapters 1–2。
Ira M. Gessel and Gilbert Labelle, “Lagrange inversion for species,” Journal of Combinatorial Theory, Series A 72(1), 1995, pp. 95–117。

形式陈述 ​

反向链接

形式陈述