组合类的循环构造 | 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\ge1$ 的标号循环排列有 $(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)$ 同样警告我们：只要构造包含非自由群作用，普通的和、积、指数或对数就不足以处理轨道，必须追踪固定点数据。

限制循环长度后，规格怎样迁移

若只允许正整数集合 $L$ 中的循环长度，每个允许长度 $m$ 的循环贡献 $z^m/m$ ，因为 $m$ 个给定标签有 $(m-1)!$ 种有向循环。用 $u$ 记录循环数，仍由互不共享标签的循环集合唯一组成排列，因而得到

P_L(z,u)=\exp\left(u\sum_{m\in L}\frac{z^m}{m}\right).

更具体地，若有 $a_m$ 个长度 $m$ 的循环，且 $\sum_mma_m=n$ ，则先排全部标签，再忘掉各循环的起点和同长度循环间顺序，得到

\frac{n!}{\prod_m m^{a_m}a_m!}

份排列。每份结果恰有相同的被遗忘表示数，故除法成立。这份系数证明也直接推出上面的指数式。

例如 $L=\{2,3\}$ ，四个标签只能组成两个二循环，数目为 $4!/(2^2\cdot2!)=3$ ；五个标签只能组成一个二循环和一个三循环，数目为 $5!/(2\cdot3)=20$ 。EGF展开分别给 $3u^2$ 与 $20u^2$ 的 $z^n/n!$ 系数。若只是禁止固定点，应取所有 $m\ge2$ ，不能误写成只允许一个大循环。

这一规格不会处理“单行列表没有下降”之类位置条件，因为循环分解没有保存列表相邻关系。第一类 Stirling 数补足按循环数的插入递推；Foata基本变换精确说明哪些列表统计能由标准循环书写迁移过去。受限循环型的公式可对照 Stanley 的 Enumerative Combinatorics Vol.1，§1.3，Proposition 1.3.2及循环指标展开。

参考资料

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。

形式陈述 ​

限制循环长度后，规格怎样迁移 ​

反向链接

形式陈述

限制循环长度后，规格怎样迁移