组合类的循环构造 | Codeboy's Blog

形式陈述

给定没有大小零对象的组合类 $\mathcal B$ ，在组合计数的符号方法中， $\operatorname{CYC}_k(\mathcal B)$ 的对象是长度 $k\ge1$ 的 $\mathcal B$ -组件序列对循环旋转作用取商后的轨道；只认同旋转，不自动认同反射。条件 $B(0)=0$ 保证每个总大小只有有限多个组件。

在标号世界，若 $B(z)$ 是 EGF，则

\operatorname{CYC}_k(\mathcal B)\longleftrightarrow \frac{B(z)^k}{k}, \qquad \operatorname{CYC}(\mathcal B)\longleftrightarrow \sum_{k\ge1}\frac{B(z)^k}{k} =\log\frac1{1-B(z)}.

无标号循环必须按旋转置换的循环类型使用Pólya 枚举。若 $B(z)$ 是 OGF，则

\operatorname{CYC}(\mathcal B)\longleftrightarrow \sum_{k\ge1}\frac{\varphi(k)}k \log\frac1{1-B(z^k)},

其中 $\varphi$ 是 Euler φ 函数。标号公式是组合物种 CYC 的 EGF 投影；无标号公式保留了固定旋转造成的对称修正。

直觉

线性序列有起点，循环没有。把同一圈从不同组件开始读，会得到 $k$ 个线性表示；当所有位置都由标签区分时，除以 $k$ 即可。无标号循环却可能在非平凡旋转下保持不变，例如重复图案“abab”，轨道大小不一定等于 $k$ ，所以必须由 Burnside/Pólya 平均固定点，而不能机械除以长度。

对数来自“非空循环”的基本级数 $\sum_{k\ge1}x^k/k$ 。它不是解析上碰巧出现的函数，而是每个循环长度的旋转对称因子在生成函数中的压缩。

例子与边界

令 $\mathcal B=\mathcal Z$ 为一个标号原子。大小为 $n$ 的有向标号循环有 $(n-1)!$ 个，所以

\sum_{n\ge1}(n-1)!\frac{z^n}{n!} =\sum_{n\ge1}\frac{z^n}{n} =\log\frac1{1-z}.

一份排列唯一分解成若干互不相交循环，因而

\operatorname{PERM} =\operatorname{SET}(\operatorname{CYC}(\mathcal Z)), \qquad P(z)=\exp\left(\log\frac1{1-z}\right) =\frac1{1-z}.

于是 $n![z^n]P(z)=n!$ ，与排列总数一致。

再看由两种颜色组成、旋转视为相同的长度四循环。Burnside 公式给出

\frac14\sum_{d\mid4}\varphi(d)2^{4/d} =\frac14(16+4+4)=6.

若把线性词的 $2^4=16$ 直接除以四，得到 $4$ ，恰好漏算具有周期的词；这就是无标号公式需要 $\varphi(d)$ 修正的可见原因。

CYC 不包含空循环。若应用把正反方向也视为相同，对称群从循环群变为二面体群，需额外平均反射固定点；上述公式不适用。若组件本身大小可为零，则可以插入任意多零组件，同样破坏局部有限性。

推论与应用

CYC 描述排列循环、圆桌排列、有向环、项链以及周期轨道。结合 SET 可把“任意对象由循环组件组成”的规格转成指数—对数恒等式；结合额外变量 $u$ ，有

\operatorname{SET}\bigl(u\,\operatorname{CYC}(\mathcal Z)\bigr) \longleftrightarrow(1-z)^{-u},

其 $u^kz^n/n!$ 系数记录具有 $k$ 个循环的排列，并连接第一类 Stirling 数。

无标号 CYC 公式中的 $B(z^k)$ 同样警告我们：只要构造包含非自由群作用，普通的和、积、指数或对数就不足以处理轨道，必须追踪固定点数据。

参考资料

Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009, Chapters I–II, cycle constructions。
François Bergeron, Gilbert Labelle, and Pierre Leroux, Combinatorial Species and Tree-like Structures, Cambridge University Press, 1998, §1.2 and Chapter 2。
George Pólya and Robert C. Read, Combinatorial Enumeration of Groups, Graphs, and Chemical Compounds, Springer, 1987, Chapter 1。

形式陈述 ​

形式陈述