2026-09-06 · 让对称作用在生成函数上

0. 导读与元结构 (Orientation & Meta-structure)

起点问题。 普通 Burnside 引理回答“有多少个对称等价类”，却会把类的内部统计量压成一个整数。例如，六颗珠子只允许黑白两色、只把旋转视为等价时，一共有多少条项链？进一步问：其中恰有三颗黑珠的有多少条？第一个问题只需轨道总数；第二个问题必须让“黑珠数”穿过取商过程而不丢失。

今天把两条既有路线合流：

• 2026-07-21 已建立有限群作用、轨道与 Burnside 平均；
• 2026-08-02 已把离散统计量编码进形式生成函数；
• 本期新增的桥是 cycle index（循环指标）：先按每个群元素的循环型分解固定着色，再把固定点数升级为固定点的权重库存。

对象层。 位置集 $D$、颜色集 $R$、置换群 $G\le \mathrm{Sym}(D)$、着色函数 $\varphi :D\to R$，以及每种颜色的交换形式权重 $x_r$。

量词层。 固定有限集合 $D,R$ 与有限群 $G$；对每个 $g\in G$，逐个考察其在 $D$ 上的循环；对每条循环独立选择一种颜色；最后对所有 $g$ 取平均。关键不是“平均很神奇”，而是下面的精确事实：

对任意 $g\in G$ 与任意着色 $\varphi$，$g\cdot \varphi =\varphi$ 当且仅当 $\varphi$ 在 $g$ 的每一条循环上恒定。

前置与去向。 前置只需有限群作用、置换循环分解、形式多项式。去向包括无标号图计数、化学异构体枚举、组合物种 (combinatorial species) 的循环指标级数，以及码的 weight enumerator（重枚举器）。本期是三日 exploration micro-arc 的第 1 日；主证明引擎是 加权双计数 + 循环上的乘法分解 + 形式代入。

1. 核心概念、定理与谱系 (Concept, Theorem & Lineage)

1.1 从着色作用到加权轨道

设 $D$ 是含 $n$ 个元素的有限集合，$R$ 是有限颜色集，$G\le \mathrm{Sym}(D)$ 是有限置换群。令

$$X:=R^D=\{\varphi :D\to R\}.$$

规定左作用

$$(g\cdot \varphi )(d):=\varphi (g^{-1}d),g\in G,\varphi \in X,d\in D.$$

为每个 $r\in R$ 引入交换变量 $x_r$。定义着色的权重

$$w(\varphi ):=\prod _{d\in D}{x}_{\varphi (d)}.$$

因为 $g$ 只重排位置，所以对所有 $g\in G$、$\varphi \in X$ 都有 $w(g\cdot \varphi )=w(\varphi )$；权重因而在每个轨道上为常数。我们要计算的不是 $|X/G|$，而是 orbit inventory（轨道库存）

$${\mathcal{I}}_{X/G}(\mathbf{x}):=\sum _{O\in X/G}w(O),$$

其中 $w(O)$ 表示轨道中任一着色的权重。

1.2 加权 Burnside 引理

定理（weighted Burnside lemma）。 设有限群 $G$ 作用于有限集 $X$，$A$ 是含 $\mathbb{Q}$ 的交换环，且 $w:X\to A$ 在每个 $G$-轨道上为常数。则

$$\sum _{O\in X/G}w(O)=\frac{1}{|G|}\sum _{g\in G}\sum _{x\in X:g\cdot x=x}w(x).$$

证明。 对每个轨道 $O$ 单独计算右端贡献。交换求和次序后，它等于

$$\frac{1}{|G|}\sum _{x\in O}|G_x|w(x),$$

其中 $G_x=\{g\in G:g\cdot x=x\}$。轨道—稳定子公式给出 $|O||G_x|=|G|$，且 $w(x)=w(O)$，故该轨道贡献恰为 $w(O)$。再对所有轨道求和即得。普通 Burnside 是把 $w\equiv 1$ 代入后的特例。$◻$

这里要求权重在轨道上不变；否则“一个轨道的权重”本身没有定义。要求交换环，则保证来自不同循环的权重可以无歧义相乘。

1.3 循环指标

对 $g\in G$ 与 $1\le j\le n$，令 $c_j(g)$ 为 $g$ 在 $D$ 上的不交循环分解中长度为 $j$ 的循环数。于是

$$\sum _{j=1}^{n}j{c}_j(g)=n.$$

定义（cycle index polynomial）。 对上述有限置换群，定义

$$Z_G(s_1,\dots ,s_n):=\frac{1}{|G|}\sum _{g\in G}\prod _{j=1}^n{s}_j^{c_j(g)}.$$

注意：循环指标依赖于具体的置换作用，不只依赖抽象群。例如，同一个抽象群作用在顶点、边或面上时，循环型可以不同。

1.4 Redfield–Pólya 循环指标定理

定理（加权着色形式）。 在 1.1 的全部假设下，对每个 $j\ge 1$ 令

$$p_j(\mathbf{x}):=\sum _{r\in R}{x}_r^j.$$

则

$$\boxed{{\displaystyle {\mathcal{I}}_{X/G}(\mathbf{x})=Z_G(p_1(\mathbf{x}),p_2(\mathbf{x}),\dots ,p_n(\mathbf{x})).}}$$

换言之，在循环指标中作代入

$$s_j⟼\sum _{r\in R}{x}_r^j,$$

便得到按每种颜色使用次数分层的轨道生成多项式。

证明架构。 固定 $g\in G$。若 $C=(d_1{d}_2\cdots d_j)$ 是一条 $j$-循环，则 $g\cdot \varphi =\varphi$ 蕴含

$$\varphi (d_1)=\varphi (d_2)=\cdots =\varphi (d_j).$$

反之，若着色在 $g$ 的每条循环上恒定，它就被 $g$ 固定。给这条 $j$-循环选择颜色 $r$，对总权重贡献 $x_r^j$；对颜色求和得到 $p_j(\mathbf{x})$。不同循环互不相交，故选择相乘：

$$\sum _{\varphi :g\cdot \varphi =\varphi }w(\varphi )=\prod _{j=1}^n{p}_j(\mathbf{x}{)}^{c_j(g)}.$$

把此式代入加权 Burnside 引理，恰得到 $Z_G(p_1,\dots ,p_n)$。假设的作用也由此显露：有限性保证求和有限；交换性保证循环贡献可相乘；轨道不变性保证左端库存有定义。$◻$

1.5 六珠二色项链：一个可执行实例

令 $D=\mathbb{Z}/6\mathbb{Z}$，$G=C_6$ 以旋转作用于六个位置；黑珠权重为 $b$，白珠权重为 $w$。六次旋转的循环型分别为

• 恒等元：$1^6$，共 $1$ 个；
• 转 $1$ 或 $5$ 格：$6^1$，共 $2$ 个；
• 转 $2$ 或 $4$ 格：$3^2$，共 $2$ 个；
• 转 $3$ 格：$2^3$，共 $1$ 个。

所以

$$Z_{C_6}(s_1,\dots ,s_6)=\frac{1}{6}(s_1^6+2s_6+2s_3^2+s_2^3).$$

代入 $s_j=w^j+b^j$：

$${\mathcal{I}}_{C_6}(w,b)=\frac{1}{6}((w+b{)}^6+2(w^6+b^6)+2(w^3+b^3{)}^2+(w^2+b^2{)}^3)$$

并展开为

$$\boxed{{\displaystyle {\mathcal{I}}_{C_6}(w,b)=w^6+w^{5}b+3w^4{b}^2+4w^3{b}^3+3w^2{b}^4+w{b}^5+b^6.}}$$

于是二色六珠项链共有 ${\mathcal{I}}_{C_6}(1,1)=14$ 条；恰有三颗黑珠的有 $4$ 条。这里的系数不是标号着色数 $(\genfrac{}{}{0ex}{}{6}{3})=20$ 除以 $6$：周期较短的着色有非平凡稳定子，轨道大小并不全相同；循环指标正是对这些稳定子作了精确修正。

1.6 谱系与现代延伸

今天这一定理通常称 Redfield–Pólya cycle index theorem（Redfield–Pólya 循环指标定理）。Shriya Anand 的公开讲义从 Burnside、循环指标一路推到加权形式，并展示项链、立方体着色和化学构型；Peter J. Cameron 则把循环指标解释为随机群元素循环结构的多变量概率生成函数，并说明其不同特化如何连接固定点、子集轨道和码的重枚举器。

研究生/现代延伸。 对线性码 $C\le {\mathbb{F}}_q^n$，码字的 Hamming weight distribution（Hamming 重分布）由重枚举多项式记录。Cameron 构造一个由码加法群诱导的置换群，使其归一化循环指标在适当代入后给出码的重枚举器，并进一步比较它与 matroid（拟阵）的 Tutte polynomial。这里显出的统一原则是：

先找到使结构等价成为轨道的群作用，再选择能记录所需统计量的多变量权重；循环指标是“对称类型”，形式代入是“局部构件”，两者合成得到无标号对象的库存。

在组合物种语言中，这一原则被扩展为 cycle-index series（循环指标级数）与物种复合；有限 Pólya 枚举正是其最可计算的原型。

2. 固定模板习题 (Template Exercise)

题目

设 $S_n$ 是 $\{1,\dots ,n\}$ 的全排列集合。称 $\sigma \in S_n$ 为 derangement（错排），若对所有 $1\le i\le n$ 都有 $\sigma (i)\ne i$。记错排数为 $D_n$。

1. 证明
   $$D_n=n!\sum _{k=0}^n\frac{(-1{)}^k}{k!}.$$
2. 证明对所有 $n\ge 1$，$D_n$ 是 $n!/e$ 的最近整数。
3. 若从 $S_n$ 均匀抽取一个排列，说明其无不动点概率为何趋于 $e^{-1}$。

模板识别

信号是“同时避开若干禁事件”：对每个位置定义 $A_i=\{\sigma :\sigma (i)=i\}$，目标是计算补集 $S_n\setminus \bigcup _i{A}_i$。一旦若干 $A_i$ 的交只依赖被指定固定的位置个数，就应优先尝试 inclusion–exclusion（容斥原理），再把阶乘比归一化成指数级数。

分级提示

1. 提示一： 固定一个 $k$ 元集合 $J\subseteq \{1,\dots ,n\}$，先数同时满足 $\sigma (j)=j$（$j\in J$）的排列数。
2. 提示二： 容斥中共有 $(\genfrac{}{}{0ex}{}{n}{k})$ 个这样的 $J$，而每个交集大小为 $(n-k)!$。
3. 提示三： 除以 $n!$ 后辨认 $e^{-1}=\sum _{k=0}^{\mathrm{\infty }}(-1{)}^k/k!$；最近整数需要定量控制截断余项。
4. 提示四： 把尾项写成
   $$\frac{n!}{(n+1)!}-\frac{n!}{(n+2)!}+\cdots ;$$
   用交错级数余项和首两项的差证明其绝对值严格小于 $1/2$。

3. 大家之言 (Mathematician in Their Own Words)

讲述者与语境。 Emmanuel Kowalski 在 ETH Zürich 的个人博客文章 Kloosterman paths（2014-10-29）中回顾：他长期画 Kloosterman 部分和的路径；一次对白板图像的追问，引出了这些路径向随机 Fourier 级数收敛的研究。他写道：

“The proof is actually relatively short, but nevertheless this is a very deep property.”

译文。 “这个证明其实相对很短，但这仍然是一个非常深刻的性质。”

这不是把“短”浪漫化。Kowalski 随即明确指出，该结论实质依赖 Deligne 的有限域上 Riemann hypothesis，以及 Katz 对 Kloosterman sheaf 单值群的计算；他还解释，控制任意矩需要群论式的等分布解释。

评注。 今天的循环指标也展示同一种结构压缩：最终公式很短，并不意味着输入浅。真正的工作是选对 representation（表示）——把一个置换换成循环型，把固定着色换成循环上的独立选择。公式之短，往往是对象已经被放进了正确坐标，而不是论证跳过了深处。

4. 反例与边界 (Counterexample & Boundary)

4.1 项链不是手链：错选群会得到错误答案

“只允许旋转重合”的 necklace（项链）由 $C_6$ 取商；“允许翻面后再旋转”的 bracelet（手链）由二面体群 $D_6$ 取商。二者不是同一个等价关系。

考虑二元循环词

$$u=001011.$$

它的六个旋转依次构成集合

$$\{001011,010110,011001,100101,101100,110010\}.$$

反序词是 $110100$，逐项检查可见它不在上述集合中。因此 $u$ 与其镜像：

• 在 $C_6$ 作用下属于两个不同轨道；
• 在 $D_6$ 作用下属于同一个轨道。

直接对全部 $2^6$ 个二元着色核验可得：按黑珠数从 $0$ 到 $6$ 排列，$C_6$-轨道系数为

$$(1,1,3,4,3,1,1),$$

而 $D_6$-轨道系数为

$$(1,1,3,3,3,1,1).$$

差异只出现在三黑三白层：一对互为镜像、但不能由旋转重合的手性项链，在允许反射后合并。因此，“Pólya 公式给错了一个”是错误诊断；真正的错误是把物理允许的对称误写成了另一个群。

4.2 两个易混边界

1. 作用不必忠实。 若某些 $g\ne e$ 在 $D$ 上作用相同，Burnside 仍成立；每个核元素都出现在群平均中，分子与 $|G|$ 同时带上同一倍数。循环指标记录的是置换作用，忠实化只会约去这层重复。
2. 不能只看循环条数来保留含量。 令所有 $x_r=1$，固定着色贡献才退化为 $|R{|}^{\sum _j{c}_j(g)}$。若要区分颜色使用次数，长度为 $j$ 的循环必须贡献 $\sum _r{x}_r^j$；只记总循环数会把不同长度造成的含量约束抹掉。

5. 今日一问与数学地图 (Question & Map)

今日一问。 对长度 $n$ 的二色项链，只把旋转视为等价。若一条项链与其镜像不属于同一旋转轨道，称它是 chiral（手性的）。试证明：当 $n\to \mathrm{\infty }$ 时，手性项链占全部二色项链的比例趋于 $1$。

允许使用 Burnside 引理，但请区分三类对象：标号二元词、$C_n$-轨道、$D_n$-轨道。不要把“随机标号词大概率无对称”直接当成轨道比例结论。

方向提示。 估计每个反射固定多少个二元词：反射把位置分成大约 $n/2$ 个自由轨道，因此其固定词数至多是 $2^{\lceil n/2\rceil }$ 量级；再与二元项链总数的 $2^n/n$ 主量级比较。需要小心处理具有旋转稳定子的词，但它们同样只占较低指数阶。

数学地图。

$$\begin{array}{c}\text{有限群作用、轨道—稳定子}\\ \downarrow \text{加权 Burnside 双计数}\\ \downarrow \text{置换循环型}⟶\text{循环指标 }{Z}_G\\ \downarrow \downarrow \text{形式代入}\text{Pólya 着色库存}⟶\text{无标号结构生成函数}\\ \swarrow \downarrow \searrow \text{项链与手性}\text{无标号图}\text{码重枚举器与 Tutte 多项式}\\ \downarrow \text{组合物种、plethysm 与 cycle-index series}\end{array}$$

明日可把位置集从“珠子”换成“顶点对”：$S_n$ 作用于 $(\genfrac{}{}{0ex}{}{n}{2})$ 条潜在边，二色着色就是简单图，轨道便是同构类。困难随即从写出公式转为理解顶点置换在边集上诱导出的循环型。

附录 A：习题完整解答 (Full Solution)

展开完整解答

模板名：禁事件容斥 → 阶乘归一化 → 交错级数余项。

令

$$A_i:=\{\sigma \in S_n:\sigma (i)=i\},1\le i\le n.$$

错排集合是 $S_n\setminus \bigcup _{i=1}^n{A}_i$。若 $J\subseteq \{1,\dots ,n\}$ 且 $|J|=k$，则要求 $J$ 中所有位置固定后，剩余 $n-k$ 个元素可任意排列，所以

$$\left|\bigcap _{j\in J}{A}_j\right|=(n-k)!.$$

容斥原理给出

$$\begin{array}{rl}{D}_n& =\sum _{J\subseteq \{1,\dots ,n\}}(-1{)}^{|J|}\left|\bigcap _{j\in J}{A}_j\right|\\ & =\sum _{k=0}^n(-1{)}^k(\genfrac{}{}{0ex}{}{n}{k})(n-k)!\\ & =n!\sum _{k=0}^n\frac{(-1{)}^k}{k!}.\end{array}$$

这证明第一问。除以 $n!$：

$$\frac{D_n}{n!}=\sum _{k=0}^n\frac{(-1{)}^k}{k!}.$$

由于

$$e^{-1}=\sum _{k=0}^{\mathrm{\infty }}\frac{(-1{)}^k}{k!},$$

交错级数判别立即给出

$$|\frac{D_n}{n!}-e^{-1}|<\frac{1}{(n+1)!},$$

从而 $D_n/n!\to e^{-1}$。这回答第三问：均匀随机排列无不动点的概率趋于 $e^{-1}$。

为证明最近整数结论，需要对乘回 $n!$ 后的误差再精细一点。令

$$E_n:=D_n-\frac{n!}{e}=(-1{)}^n(\frac{1}{n+1}-\frac{1}{(n+1)(n+2)}+\frac{1}{(n+1)(n+2)(n+3)}-\cdots ).$$

括号内为正，并严格小于首项 $1/(n+1)$。当 $n\ge 2$ 时，

$$|E_n|<\frac{1}{n+1}\le \frac{1}{3}<\frac{1}{2}.$$

当 $n=1$ 时，$D_1=0$，而 $1/e<1/2$。因此对所有 $n\ge 1$ 都有

$$|D_n-\frac{n!}{e}|<\frac{1}{2}.$$

因为 $D_n$ 是整数，它必是 $n!/e$ 的唯一最近整数，即

$$\boxed{{\displaystyle D_n=\lfloor \frac{n!}{e}+\frac{1}{2}\rfloor .}}$$

这里可复用的结构是：先把“避开所有坏事件”写成补集；按交集规模分组完成容斥；最后用一个已知幂级数识别归一化极限，并用余项控制把渐近结论加强为精确取整。

资料与来源 (Sources)

1. Shriya Anand, “How to count—an exposition of Pólya’s theory of enumeration,” Resonance, September 2002, pp. 19–35. 本期用于核验 Burnside、循环指标、加权 Pólya 代入及项链实例的完整推导。Indian Statistical Institute 公开全文：
   https://www.isibang.ac.in/~sury/polya
2. Peter J. Cameron, “Cycle index, weight enumerator, and Tutte polynomial,” The Electronic Journal of Combinatorics 9 (2002), Note N2, submitted 2002-01-09, accepted 2002-02-27. 本期用于循环指标的现代概率生成函数解释，以及码重枚举器、拟阵与 Tutte 多项式延伸。期刊 PDF：
   https://www.combinatorics.org/ojs/index.php/eljc/article/download/v9i1n2/pdf/
   EuDML 书目信息与全文入口：
   https://eudml.org/doc/121792
3. Emmanuel Kowalski, “Kloosterman paths,” E. Kowalski’s blog, ETH Zürich, 2014-10-29. 本期“大家之言”的第一人称原文与研究语境；引文已按原页核对：
   https://blogs.ethz.ch/kowalski/2014/10/29/kloosterman-paths/

本期计算核验。 六珠 $C_6$ 与 $D_6$ 的二色轨道库存、手性词 $001011$ 的旋转轨道，以及 $1\le n\le 8$ 的错排公式，均以穷举独立核验；正文只保留数学推导与可复查结果。