2026-09-07 · 让顶点置换接管边

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

起点问题。 $n$ 个已编号顶点上有 $2^{(\genfrac{}{}{0ex}{}{n}{2})}$ 张简单图；删掉编号后却不能直接除以 $n!$，因为不同图的自同构群大小不同。真正的问题是：一个顶点置换会怎样重排所有潜在边？

本期是三日 exploration micro-arc 的第 2 日。昨日已经证明：若有限群置换一组“位置”，则固定着色在每条置换循环上恒定。今日把位置集具体化为

$$(\genfrac{}{}{0ex}{}{V}{2}):=\{\{u,v\}:u,v\in V,u\ne v\},$$

把一张简单图 $G=(V,E)$ 看成函数 ${\mathbf{1}}_E:(\genfrac{}{}{0ex}{}{V}{2})\to \{0,1\}$。于是：

• 对象层： 顶点集 $V$、潜在边集 $(\genfrac{}{}{0ex}{}{V}{2})$、边子集 $E$、顶点置换 $\sigma \in S_V$；
• 量词层： 固定 $n$；对所有 $\sigma \in S_n$，计算它在 $(\genfrac{}{}{0ex}{}{[n]}{2})$ 上的每条循环；每条边循环独立选择“全有”或“全无”；最后平均；
• 主证明引擎： 顶点循环分解、$gcd/\mathrm{lcm}$ 轨道计算、Burnside 平均；
• 前置： 有限群作用、不交循环分解、昨日的加权 Burnside；
• 去向： 无标号图生成函数、组合物种 (combinatorial species)、随机图的非对称性。

困难不在再说一次“用 Burnside”，而在求诱导边置换的循环型。今日将这一步完整拆开。

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

1.1 图同构就是轨道等价

令 $V=[n]=\{1,\dots ,n\}$，${\mathcal{G}}_n:=\mathcal{P}((\genfrac{}{}{0ex}{}{V}{2}))$ 为所有标号简单图的边集。对 $\sigma \in S_n$ 与 $E\in {\mathcal{G}}_n$ 定义

$$\sigma \cdot E:=\{\{\sigma (u),\sigma (v)\}:\{u,v\}\in E\}.$$

对任意 $E,F\in {\mathcal{G}}_n$，$E$ 与 $F$ 所表示的图同构，当且仅当存在 $\sigma \in S_n$ 使 $F=\sigma \cdot E$。故无标号图恰是商集 ${\mathcal{G}}_n/S_n$ 的元素。

设 $c_2(\sigma )$ 表示 $\sigma$ 在潜在边集 $(\genfrac{}{}{0ex}{}{V}{2})$ 上诱导置换的循环条数。一个图 $E$ 被 $\sigma$ 固定，当且仅当对诱导置换的每条边循环 $C$，都有 $C\subseteq E$ 或 $C\cap E=\varnothing$。每条循环有两个独立选择，所以

$$|{\mathrm{Fix}}_{{\mathcal{G}}_n}(\sigma )|=2^{c_2(\sigma )}.$$

由 Burnside 引理立即得到：

定理（无标号简单图计数）。 对每个整数 $n\ge 0$，$n$ 顶点无标号简单图数 $g_n$ 满足

$$\boxed{{\displaystyle g_n=\frac{1}{n!}\sum _{\sigma \in S_n}{2}^{c_2(\sigma )}.}}$$

若还要记录边数，设诱导边循环长度为 $d_1(\sigma ),\dots ,d_{c_2(\sigma )}(\sigma )$，则固定图的边数库存为

$$\sum _{E:\sigma E=E}{x}^{|E|}=\prod _{r=1}^{c_2(\sigma )}(1+x^{d_r(\sigma )}),$$

故按边数计数的无标号图多项式为

$$\boxed{{\displaystyle G_n(x)=\frac{1}{n!}\sum _{\sigma \in S_n}\prod _{r=1}^{c_2(\sigma )}(1+x^{d_r(\sigma )}).}}$$

这正是昨日加权 Pólya 公式对“边不存在/存在”两种颜色的具体化。

1.2 从顶点循环计算边循环

设 $\sigma$ 的顶点循环长度为 $a_1,\dots ,a_m$。潜在边分成两类：连接不同顶点循环的边，以及位于同一顶点循环内部的边。

不同顶点循环之间

取长度分别为 $a,b$ 的两个顶点循环 $A,B$。将它们编号为 $\mathbb{Z}/a\mathbb{Z}$ 与 $\mathbb{Z}/b\mathbb{Z}$；诱导作用是

$$(i,j)⟼(i+1,j+1).$$

一条边回到自身，恰当且仅当步数 $t$ 同时被 $a,b$ 整除；最小正步数为 $\mathrm{lcm}(a,b)$。共有 $ab$ 条跨接边，因此它们分成

$$\frac{ab}{\mathrm{lcm}(a,b)}=gcd(a,b)$$

条循环，每条长度 $\mathrm{lcm}(a,b)$。

同一顶点循环内部

取一条长度为 $a$ 的顶点循环，编号为 $\mathbb{Z}/a\mathbb{Z}$。内部无序边 $\{i,j\}$ 的 circular distance（圆周距离）定义为

$$d(\{i,j\})=min\{|i-j|,a-|i-j|\}\in \{1,\dots ,\lfloor a/2\rfloor \}.$$

距离在旋转下不变。对每个 $1\le d<a/2$，全部距离为 $d$ 的边形成一条长度为 $a$ 的循环。若 $a$ 为偶数，距离 $a/2$ 的“直径边”只有 $a/2$ 条，形成一条长度为 $a/2$ 的循环。因此一条 $a$-顶点循环内部贡献

$$\lfloor \frac{a-1}{2}\rfloor$$

条长度 $a$ 的边循环，并在 $a$ 为偶数时额外贡献一条长度 $a/2$ 的边循环。

合并两类边即得：

命题（诱导二元子集循环公式）。 若 $\sigma \in S_n$ 的顶点循环长度为 $a_1,\dots ,a_m$，则其诱导边置换的循环多重集由以下部分组成：

1. 对每对 $1\le i<j\le m$，加入 $gcd(a_i,a_j)$ 条长度 $\mathrm{lcm}(a_i,a_j)$ 的循环；
2. 对每个 $i$，加入 $\lfloor (a_i-1)/2\rfloor$ 条长度 $a_i$ 的循环；若 $a_i$ 为偶数，再加入一条长度 $a_i/2$ 的循环。

每条潜在边恰属于其中一类，且上述循环长度总和为 $(\genfrac{}{}{0ex}{}{n}{2})$，所以没有遗漏。

1.3 四个顶点：按共轭类计算

$S_4$ 的五种顶点循环型给出如下诱导边循环型：

顶点循环型	置换数	边循环型	固定图数
$1^4$	$1$	$1^6$	$2^6$
$2,1^2$	$6$	$1^2{2}^2$	$2^4$
$2^2$	$3$	$1^2{2}^2$	$2^4$
$3,1$	$8$	$3^2$	$2^2$
$4$	$6$	$2,4$	$2^2$

于是

$$g_4=\frac{1}{24}(2^6+9\cdot 2^4+8\cdot 2^2+6\cdot 2^2)=11.$$

保留边数变量则

$$\begin{array}{rl}{G}_4(x)=\frac{1}{24}(& (1+x{)}^6+9(1+x{)}^2(1+x^2{)}^2\\ & +8(1+x^3{)}^2+6(1+x^2)(1+x^4)),\end{array}$$

展开为

$$\boxed{{\displaystyle G_4(x)=1+x+2x^2+3x^3+2x^4+x^5+x^6.}}$$

系数和为 $11$；系数关于 $x^3$ 对称，因为取补图把 $k$ 边图与 $(6-k)$ 边图双射起来。

1.4 谱系与现代延伸

Pólya 枚举把“群如何作用在位置上”压成循环指标；图枚举的关键推进，是让 $S_n$ 先作用于顶点，再通过二元子集函子作用于边。直接逐个枚举 $n!$ 个置换虽正确，却重复计算大量同循环型元素；按整数分拆 $\lambda ⊢n$ 汇总共轭类，才得到可扩展公式。

研究生/现代延伸。 在组合物种语言中，简单图是结构函子

$$\mathrm{Graph}[V]=\mathcal{P}\left((\genfrac{}{}{0ex}{}{V}{2})\right),$$

顶点双射自然诱导图的重标号。标号指数生成函数只数 $2^{(\genfrac{}{}{0ex}{}{n}{2})}$；无标号普通生成函数必须保留自同构信息，因而需要 cycle-index series（循环指标级数），不能从标号计数机械地“除以 $n!$”。今日的诱导边循环公式正是这层自同构数据的有限阶实例。

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

题目

将 $m$ 个有编号的球独立、等概率投入 $n$ 个有编号的盒子，每个球选择每个盒子的概率均为 $1/n$。设 $N_0$ 为空盒数。

1. 证明
   $$\mathbb{P}(N_0=0)=\frac{1}{n^m}\sum _{k=0}^n(-1{)}^k(\genfrac{}{}{0ex}{}{n}{k})(n-k{)}^m.$$
2. 推出满射数公式
   $$\mathrm{\#}\{f:[m]\twoheadrightarrow [n]\}=\sum _{k=0}^n(-1{)}^k(\genfrac{}{}{0ex}{}{n}{k})(n-k{)}^m=n!S(m,n),$$
   其中 $S(m,n)$ 是第二类 Stirling 数。
3. 证明若 $m=n\log n+cn$，则
   $$\mathbb{P}(N_0>0)\le e^{-c}.$$

模板识别

目标是“每个类别至少出现一次”。令 $A_i$ 表示第 $i$ 个盒子为空：精确计数用 inclusion–exclusion（容斥），粗阈值上界用 union bound（并集界）。若固定 $k$ 个盒子为空，所有球只能落入其余 $n-k$ 个盒子，交集概率只依赖 $k$。

分级提示

1. 提示一： 写出 $\{N_0=0\}=\bigcap _{i=1}^n{A}_i^c$。
2. 提示二： 若 $J\subseteq [n]$ 且 $|J|=k$，则 $\mathbb{P}(\bigcap _{j\in J}{A}_j)=((n-k)/n{)}^m$。
3. 提示三： 乘以总函数数 $n^m$，即可把概率公式改写为满射计数。
4. 提示四： 第三问不必做完整容斥；使用 $\mathbb{P}(A_i)=(1-1/n{)}^m\le e^{-m/n}$。

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

讲述者与语境。 John Baez 在第一人称专栏 This Week’s Finds in Mathematical Physics, Week 202（2004-02-21）介绍 André Joyal 的组合物种及范畴化时写道：

“instead of merely proving equations between generating functions, we can construct isomorphisms between their underlying structure types — which imply such equations, but are worth much more.”

译文。 “我们不再只是证明生成函数之间的方程，而可以构造其底层结构类型之间的同构；这些同构蕴含方程，却比方程本身包含更多。”

评注。 今日算出 $G_4(x)$ 只是数值层；更深的对象层是：每个顶点双射都明确搬运边集，图同构类则是这种搬运形成的轨道。Baez 强调的不是用范畴语言替换等号，而是保留“为何相等”的见证。补图对称使 $G_4(x)$ 系数反向相等，也不仅是代数巧合：映射 $E\mapsto (\genfrac{}{}{0ex}{}{V}{2})\setminus E$ 与所有重标号交换，给出了逐个同构类的双射。结构映射在先，系数恒等式是其影子。

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

4.1 同样的顶点数和边数，仍可不同构

考虑四顶点路径

$$P_4:1-2-3-4$$

与三叶星

$$K_{1,3}:E=\{\{1,2\},\{1,3\},\{1,4\}\}.$$

逐项检查：

• 二者都有 $4$ 个顶点、$3$ 条边；
• 二者都连通且无环，所以都是树；
• 但 $P_4$ 的度数多重集为 $\{2,2,1,1\}$，$K_{1,3}$ 的度数多重集为 $\{3,1,1,1\}$。

因此只按边数分层的 $G_4(x)$ 当然不能判定同构。即使两个图度数列相同，度数列一般也不是完全不变量；它只记录每个顶点邻边的数量，不记录这些邻接如何彼此配合。

这个小例还暴露自同构造成的“不能除以 $n!$”：

• $|\mathrm{Aut}(P_4)|=2$，只有恒等和路径反向，故标号轨道大小为 $24/2=12$；
• $|\mathrm{Aut}(K_{1,3})|=6$，中心必须固定、三片叶子可任意置换，故轨道大小为 $24/6=4$。

同为三边无标号图，一个同构类包含 $12$ 张标号图，另一个只含 $4$ 张；统一除以 $24$ 不可能逐类正确。

4.2 不能让所有边任意置换

顶点置换确实诱导潜在边的置换，但通常并不能产生 $S_{(\genfrac{}{}{0ex}{}{n}{2})}$ 的全部元素。允许任意交换两条边而不顾共享端点，会改变 incidence（关联）关系，不再对应图的顶点重标号。故这里必须使用 $S_n\to \mathrm{Sym}((\genfrac{}{}{0ex}{}{[n]}{2}))$ 的诱导像，而不是误把边集当成具有全部对称的独立位置。

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

今日一问。 设 $g_n$ 为 $n$ 顶点无标号简单图数。试证明

$$g_n\sim \frac{2^{(\genfrac{}{}{0ex}{}{n}{2})}}{n!},n\to \mathrm{\infty }.$$

等价地，试说明几乎所有标号简单图的自同构群都是平凡群。不要只说“随机图看起来不对称”；请从 Burnside 公式出发，估计所有非恒等 $\sigma$ 的总贡献

$$\sum _{\sigma \ne \mathrm{id}}{2}^{c_2(\sigma )}.$$

方向提示。 先按 $\sigma$ 移动的顶点数分类。一个非恒等置换至少含一个长度不小于 $2$ 的顶点循环，它会迫使许多边成批同步；真正需要控制的是 $(\genfrac{}{}{0ex}{}{n}{2})-c_2(\sigma )$ 的下界能否压过具有相应支撑大小的置换数。只处理换位可看见主危险项，但完整证明还要统一覆盖更长循环。

数学地图。

$$\begin{array}{c}\text{顶点置换与不交循环}\\ \downarrow \text{无序顶点对上的诱导作用}\\ \downarrow gcd/\mathrm{lcm}\text{ 边循环公式}\\ \downarrow \text{固定图}=\text{边循环的二色选择}\\ \downarrow \text{Burnside 平均与无标号图库存}\\ \swarrow \searrow \text{整数分拆压缩计算}\text{补图与自同构}\\ \downarrow \downarrow \text{组合物种循环指标}\text{随机图非对称性}\end{array}$$

明日可进一步问：为什么标号生成函数、无标号生成函数和按 $1/|\mathrm{Aut}|$ 加权的生成函数是三种不同投影？组合物种的循环指标级数将把今日逐个 $n$ 的 Burnside 计算组织成一个统一对象。

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

展开完整解答

模板名：缺失类别事件 → 容斥精确式 → 并集界阈值估计。

令 $A_i$ 为第 $i$ 个盒子为空的事件。则

$$\{N_0=0\}=\bigcap _{i=1}^n{A}_i^c={\left(\bigcup _{i=1}^n{A}_i\right)}^c.$$

若 $J\subseteq [n]$ 且 $|J|=k$，事件 $\bigcap _{j\in J}{A}_j$ 要求每个球都避开 $J$ 中的盒子。每个球有 $(n-k)/n$ 的概率做到，且各球独立，所以

$$\mathbb{P}\left(\bigcap _{j\in J}{A}_j\right)={\left(\frac{n-k}{n}\right)}^m.$$

容斥原理给出

$$\begin{array}{rl}\mathbb{P}(N_0=0)& =\sum _{J\subseteq [n]}(-1{)}^{|J|}\mathbb{P}\left(\bigcap _{j\in J}{A}_j\right)\\ & =\sum _{k=0}^n(-1{)}^k(\genfrac{}{}{0ex}{}{n}{k}){\left(\frac{n-k}{n}\right)}^m\\ & =\frac{1}{n^m}\sum _{k=0}^n(-1{)}^k(\genfrac{}{}{0ex}{}{n}{k})(n-k{)}^m.\end{array}$$

每一种投球结果等价于一个函数 $f:[m]\to [n]$，总数为 $n^m$；没有空盒恰等价于 $f$ 为满射。故乘回 $n^m$ 得

$$\mathrm{\#}\{f:[m]\twoheadrightarrow [n]\}=\sum _{k=0}^n(-1{)}^k(\genfrac{}{}{0ex}{}{n}{k})(n-k{)}^m.$$

另一方面，将 $[m]$ 按满射的纤维分成 $n$ 个非空、无标号块有 $S(m,n)$ 种；再把这些块双射到 $n$ 个有标号盒子有 $n!$ 种。因此

$$\mathrm{\#}\{f:[m]\twoheadrightarrow [n]\}=n!S(m,n).$$

最后，由并集界及 $1-x\le e^{-x}$，

$$\begin{array}{rl}\mathbb{P}(N_0>0)& =\mathbb{P}\left(\bigcup _{i=1}^n{A}_i\right)\le \sum _{i=1}^n\mathbb{P}(A_i)\\ & =n{(1-\frac{1}{n})}^m\le n{e}^{-m/n}.\end{array}$$

当 $m=n\log n+cn$ 时，

$$n{e}^{-m/n}=n{e}^{-\log n-c}=e^{-c},$$

故 $\mathbb{P}(N_0>0)\le e^{-c}$。

该模板的分工是：容斥保留各坏事件交叠，给精确答案；并集界丢掉交叠，却能用一次指数估计迅速确定覆盖阈值的上侧尺度。

资料与来源 (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 加权公式，并把简单图明确建模为顶点对的 $0/1$ 构型；其四顶点计算得到 $1+x+2x^2+3x^3+2x^4+x^5+x^6$。Indian Statistical Institute 公开全文：
   https://www.isibang.ac.in/~sury/polya
2. Columbia University course text, Chapter 9, “Graph Enumeration,” sections 9.3–9.6. 本期用于交叉核验顶点自同构、边上的诱导作用、小图与一般图枚举的章节结构；PDF 原件：
   https://www.cs.columbia.edu/~cs4205/files/CM9.pdf
3. John Baez, “This Week’s Finds in Mathematical Physics, Week 202,” 2004-02-21. 本期“大家之言”的第一人称原文、组合物种与“方程—同构”语境；纯文本原页：
   https://math.ucr.edu/home/baez/twf_ascii/week202

本期计算核验。 诱导二元子集循环公式已对 $1\le n\le 7$ 的每个顶点置换逐一与显式边轨道比较；由 Burnside 得到无标号图数 $1,2,4,11,34,156,1044$。四顶点边数库存及 $P_4,K_{1,3}$ 的自同构群大小也以独立穷举核验；正文保留可复查的数学推导。