Bóna · 枚举与解析组合学导论 · 第 8 章 对称结构

8.4　对称结构的计数Counting symmetric structures

本页为译文 + 高中讲解合一：黑色正文为忠实翻译；彩色框（目标 / 例 / 分步推演）与配图为面向高中生的详解，逐步推演、举例、画图，不用比喻。

读者也许还记得，在第 5 章中，当我们计数图（graph）时，通常计数的是带标号顶点的图，这样就避免了对称性的出现。我们曾提到，无标号图的枚举通常更困难。这一点对其他结构也同样成立。为了说明原因，让我们来考虑这样一项工作：用 \(k\) 种颜色之一去给一个立方体的六个面分别上色。如果这六个面被看作彼此不同——例如它们被标记为 \(1\) 到 \(6\)——那么上色的方式数就是 \(k^6\)。然而，如果这些面是无法区分的，问题就要难得多。比方说，我们认为：若一种染色能通过一连串旋转变成另一种，则这两种染色视为相同。这时我们不能简单地把“不顾旋转的全部可能染色数”数出来，再除以“全部可能旋转的个数”，因为对每一种染色而言，可能的旋转个数并不相同。（比较一下：只用一种颜色的染色，与用满全部六种颜色的染色。）如果除旋转之外还允许经过平面的反射，情况会更加复杂。问题仍然在于：并非所有等价类都具有相同的大小。

本节目标当被计数的对象带有对称性（旋转、反射、图的自同构等会把“看起来不同”的摆法认成同一种）时，直接“总数 ÷ 对称个数”是错的。本节引入群（group）与置换群（permutation group）的基本概念，建立轨道（orbit）与稳定子（stabilizer），最后用一条主定理（Burnside 引理）：本质不同的对象个数 = 各个对称“不动的染色数”的平均值。
为什么不能直接除：立方体的小例 用 \(k=2\) 种颜色染立方体六个面。若六面有标号，共 \(2^6=64\) 种。立方体的旋转共有 \(24\) 个。若天真地算 \(64/24\)，得 \(64/24\approx2.67\)，根本不是整数——这说明“总数 ÷ 对称数”不可靠。根源是：全红的染色被任何旋转保持不变（它的轨道只有 \(1\) 个元素），而“五面红一面蓝”的染色却有 \(6\) 个旋转把它换来换去（轨道有 \(6\) 个元素）。各染色的轨道大小不一，不能用同一个数去除。
前面 顶面 右面 六个面共可染 \(k^6\) 种（有标号）；若面不可区分则需按对称归类
给立方体六面上色：有标号时方式数 \(=k^6\)；面无法区分时，需要把能互相旋转/反射得到的染色视为同一种，这正是本节要解决的计数问题。

为了能够讨论处理上述这类问题的工具，我们需要引入群论（Group Theory）的基本概念，特别是置换群（permutation groups）的理论。此前修过抽象代数课程的读者，大概会对这些概念感到熟悉。

群与对称群

定义 8.28 一个群（group）是指一个元素集合 \(G\) 连同一个定义在 \(G\) 的有序对集合上的运算（我们称之为乘法），并满足以下公理：
  1. 单位元存在：\(G\) 中存在一个单位元（identity element），即存在元素 \(e\in G\)，使得对一切 \(a\in G\) 都有 \(a\cdot e=e\cdot a=a\)。
  2. 封闭性：\(G\) 对乘法封闭，即若 \(a\in G\) 且 \(b\in G\)，则 \(a\cdot b\in G\)。
  3. 结合律：乘法满足结合律，即 \((a\cdot b)\cdot c=a\cdot(b\cdot c)\)。
  4. 逆元唯一：\(G\) 的每个元素都有唯一的逆元，即对每个 \(a\in G\)，存在唯一的元素 \(b\in G\)，使得 \(ab=ba=e\)。此时记 \(b=a^{-1}\)。

注意，这里的“乘法”运算可以用任何满足上述公理的方式来定义；也就是说，它不必是我们在处理实数时通常所说的那种乘法。

如果这是读者第一次听说群，那么读者应当花点时间证明（通过逐条验证所有公理）：以加法为运算的全体实数构成一个群；以传统乘法为运算的全体非零实数也构成一个群。完成之后，读者应当解释：为什么以传统乘法为运算的全体实数不构成群。

例：验证三个“候选群”
  1. \((\mathbb{R},+)\) 是群：单位元 \(e=0\)（因为 \(a+0=a\)）；两实数之和仍是实数（封闭）；加法结合律成立；\(a\) 的逆元是 \(-a\)（因为 \(a+(-a)=0\)）。四条全满足。
  2. \((\mathbb{R}\setminus\{0\},\times)\) 是群：单位元 \(e=1\)；两非零实数之积非零（封闭）；乘法结合；\(a\) 的逆元是 \(1/a\)。四条全满足。
  3. \((\mathbb{R},\times)\) 不是群：问题出在第 4 条——元素 \(0\) 没有逆元，因为不存在实数 \(b\) 使 \(0\cdot b=1\)。一个公理被破坏，就不是群。

虽然可以用一整章来举各种有趣群的例子，但我们将聚焦于长度为 \(n\) 的全体置换构成的群。当然，首先必须证明：这个集合在那个最自然想到的运算——即第 4 章定义的置换的乘法——之下确实构成一个群。回忆一下，在定义 4.13 中我们简单地规定：两个 \(n\)-置换 \(f\) 与 \(g\) 的乘积，就是把它们作为从 \([n]\) 到 \([n]\) 的双射进行复合。

命题 8.29 全体 \(n\)-置换的集合，配以置换的乘法作为运算，构成一个群。

正如我们在第 4 章中提到的，这个群称为对称群（symmetric group），记作 \(S_n\)。

证明. 我们逐条验证所有公理成立。
  1. 置换 \(p=(1)(2)\cdots(n)\)（即把每个元素映到自身的恒等置换）是这个群的单位元。
  2. 两个 \(n\)-置换的乘积仍是一个 \(n\)-置换，因为两个从 \([n]\) 到 \([n]\) 的双射的复合仍是从 \([n]\) 到 \([n]\) 的双射。
  3. 设 \(f,g,h\) 为三个置换，并设 \(f(i)=j\)，\(g(j)=k\)，\(h(k)=m\)。则 \[((f\cdot g)\cdot h)(i)=h(g(f(i)))=h(g(j))=h(k)=m,\] 以及 \[(f\cdot(g\cdot h))(i)=(g\cdot h)(f(i))=h(g(j))=h(k)=m.\] 两者相等，故结合律成立。
  4. 置换 \(f\) 的逆元，就是 \(f\) 作为双射的逆映射。
♦

如果群 \(G\) 的元素的某个子集 \(H\) 在与 \(G\) 相同的运算下自身也构成一个群，我们就称 \(H\) 是 \(G\) 的一个子群（subgroup）。对称群 \(S_n\) 的子群称为置换群（permutation groups），因为它们的元素都是置换。

关键的概念是：置换会移动（置换）对象。在本章以及第 4 章迄今的例子里，这些被移动的对象通常就是集合 \([n]\) 的元素。然而，置换也可以作用在其他集合上。回忆第 5 章中图 \(M\)（顶点集为 \([n]\)）的自同构（automorphism）的定义：这样一个自同构是顶点集到自身的一个双射 \(f\)，使得 \(f(a)\) 与 \(f(b)\) 相邻当且仅当 \(a\) 与 \(b\) 相邻。换句话说，自同构就是顶点的一个置换。容易证明：\(M\) 的全体自同构构成一个群。把这个群记作 \(\mathrm{Aut}(M)\)；那么 \(\mathrm{Aut}(M)\) 是一个置换群，事实上它是 \(S_n\) 的一个子群。

轨道

图及其自同构群，为我们接下来要讨论的概念——对象在置换群作用下的轨道（orbit）——提供了一种简单的可视化方式。

请读者考虑图 8.4 所示的图 \(G\)。群 \(\mathrm{Aut}(M)\) 在这些顶点之间进行置换。然而，无论我们选取哪个元素 \(f\in\mathrm{Aut}(M)\)，总有 \(f(4)=4\) 成立，因为 \(4\) 是图 \(G\) 中唯一一个度数为 \(5\) 的顶点，而我们知道 \(4\) 与 \(f(4)\) 的度数必须相同（因为自同构必须保持度数）。由类似的论证，\(f(1)\) 只能是 \(1\)、\(2\) 或 \(3\)，因为这是仅有的三个度数为 \(3\) 的顶点。对 \(f(2)\) 与 \(f(3)\) 同理。类似地，\(f(5)\) 只能等于 \(5\) 或 \(6\)，\(f(6)\) 同理，因为 \(5\) 与 \(6\) 是仅有的两个度数为 \(1\) 的顶点。

最后，这些选择中的任何一种确实都是可能的，即：存在 \(f\in\mathrm{Aut}(M)\) 使得 \(f(1)=3\)，存在 \(f\in\mathrm{Aut}(M)\) 使得 \(f(1)=2\)，依此类推。

1 2 3 4 5 6 轨道：{1,2,3}（绿，度数 3）、{4}（红，度数 5）、{5,6}（蓝，度数 1）
图 8.4　图 \(M\) 的顶点集在 \(\mathrm{Aut}(M)\) 作用下的轨道为 \(\{1,2,3\}\)、\(\{4\}\) 与 \(\{5,6\}\)。同一轨道内的顶点度数相同；自同构必须保持度数，故只能在度数相同的顶点之间互换。

上面描述的现象非常重要，值得给它一个名字。

定义 8.30 设 \(G\) 是作用在集合 \(S\) 上的置换群，设 \(i\in S\)。令 \[i^G=\{\,g(i)\mid g\in G\,\}.\] 换句话说，\(i^G\) 是 \(i\) 在 \(G\) 的某个元素作用下能被映成的全部顶点构成的集合。则 \(i^G\) 称为 \(i\) 在 \(G\) 下的轨道。
例 8.31 若 \(S\) 是图 8.4 所示图 \(M\) 的顶点集，且 \(G=\mathrm{Aut}(M)\)，则各元素在 \(\mathrm{Aut}(M)\) 下的轨道如下：

读者也许已经注意到：两个元素的轨道要么相等，要么不相交；绝不会发生“有几个公共元素、又有几个不同元素”的情形。如下面的引理所示，这总是成立的。

引理 8.32 设 \(G\) 是作用在集合 \(S\) 上的置换群，设 \(i\) 与 \(j\) 是 \(S\) 的两个不同元素。则要么 \(i^G=j^G\)，要么 \(i^G\cap j^G=\varnothing\)。

换句话说，如果我们把同一条轨道的重复副本去掉，那么这些轨道构成 \(S\) 的一个划分（partition）。

证明（引理 8.32）. 首先假设 \(j\in i^G\)，即存在 \(f\in G\) 使得 \(f(i)=j\)。现在假设 \(k\in j^G\)，即对某个 \(h\in G\) 有 \(h(j)=k\)。那么我们也有 \(k\in i^G\)，因为 \((f\cdot h)(i)=h(f(i))=h(j)=k\)。因此 \(j^G\subseteq i^G\)。再注意到 \(f^{-1}(j)=i\)，所以 \(i\in j^G\)。于是我们可以在上面的论证中交换 \(i\) 与 \(j\) 的角色，得到 \(i^G\subseteq j^G\)，从而 \(i^G=j^G\)。
现在假设 \(j\notin i^G\)。我们断言此时 \(i^G\) 与 \(j^G\) 必不相交。若不然，即假设存在元素 \(s\in S\) 使得对某些 \(p,q\in G\) 有 \(p(i)=s\) 且 \(q(j)=s\)。那么 \(q^{-1}(s)=j\)，于是 \((p\cdot q^{-1})(i)=q^{-1}(p(i))=q^{-1}(s)=j\)，这与 \(j\notin i^G\) 的假设矛盾。♦

也就是说，关系“\(i\) 与 \(j\) 有相同的轨道”是 \(S\) 上的一个等价关系（equivalence relation）。等价类的个数恰好就是不同轨道的个数。在我们计数“互不等价的结构”的征途中，我们将设法把问题归结为“计数某个置换群作用在某集合上的轨道个数”这一问题。

把握主线“本质不同的对象个数” = “轨道个数”。难点在于轨道大小不一，不能直接除。下面再引入稳定子，并通过引理 8.34 建立“轨道大小 × 稳定子大小 = 群的大小”这一桥梁，最终导出主定理。

稳定子与不动点

在给出主结果之前，我们还需要引入最后一个概念。它是轨道概念的一个自然对应物。元素 \(i\) 的轨道大小告诉我们：在给定置换群 \(G\) 下，\(i\) 能被映成多少个不同的元素。我们也可以反过来问：\(G\) 中有多少个元素会把 \(i\) 保持在原处；或者问：一个给定的元素 \(g\) 会把 \(S\) 中的多少个元素保持不动。这两个有用的概念我们都需要。

定义 8.33 设 \(G\) 是作用在集合 \(S\) 上的置换群，设 \(i\in S\)。则集合 \[G_i=\{\,g\in G\mid g(i)=i\,\}\] 称为 \(i\) 的稳定子（stabilizer）。

在补充习题 15 中，请读者验证 \(G_i\) 总是 \(G\) 的一个子群。

此时合理的猜想是：当 \(G\) 与 \(S\) 固定时，\(i^G\) 越大，\(G_i\) 就越小。的确，\(i\) 能去的地方越多，能把它固定住的元素就应当越少。我们还想指出，例 8.31 暗示 \(|i^G|\) 总是 \(|G|\) 的一个因子。下面的引理将表明，这两个观察在一般情形下都成立。

引理 8.34（轨道–稳定子定理） 设 \(G\) 是作用在集合 \(S\) 上的有限置换群，设 \(i\in S\)。则 \[\frac{|G|}{|G_i|}=\bigl|\,i^G\,\bigr|.\]
证明. 若 \(g\in G\)，记 \(gG_i\) 表示集合 \(\{h\in G\mid gx=h\ \text{对某个}\ x\in G_i\}\)。这些集合 \(gG_i\) 称为 \(G_i\) 在 \(G\) 中的陪集（cosets）。
我们首先断言：\(G_i\) 在 \(G\) 中的两个陪集要么相等，要么不相交。此断言的证明与引理 8.32 的证明非常相似，故留作习题 12。
请读者验证：所有陪集 \(gG_i\) 与 \(G_i\) 具有相同的大小。事实上，\(gG_i\) 的元素是乘积 \(gx\)，其中 \(x\) 取遍 \(G_i\) 的全部元素。这意味着共有 \(|G_i|\) 个乘积，而且它们两两不同——若不然，则会有 \(gx=gx'\)，两边左乘 \(g^{-1}\) 后得 \(x=x'\)，矛盾。
由于 \(G_i\) 的不同陪集构成 \(G\) 的一个划分，这就证明了 \(|G_i|\) 整除 \(|G|\)。
讨论完这些陪集的大小，现在把注意力转向它们的个数。我们断言：\(G_i\) 的陪集个数等于 \(|i^G|\)，即 \(i\) 的轨道大小。
我们将通过构造一个从 \(i^G\) 到“\(G_i\) 在 \(G\) 中全体陪集”集合上的双射 \(\alpha\) 来证明此断言。\(i^G\) 的元素可写成 \(g(i)\) 的形式，其中 \(g\in G\)（但 \(g\) 未必唯一）。现令 \(\alpha(g(i))=gG_i\)。
在试图证明 \(\alpha\) 确实是双射之前，我们必须先证明它是良定义的，即：若 \(g\) 与 \(g_1\) 满足 \(g(i)=g_1(i)\)，则 \(\alpha(g(i))=\alpha(g_1(i))\)。这将表明 \(\alpha\) 确实是定义在 \(i\) 的轨道元素上的映射，且不依赖于诸如 \(g\) 的选取之类的其他东西。为此，注意 \(g(i)=g_1(i)\) 等价于 \(g_1^{-1}g(i)=i\)，即 \(g_1^{-1}g\in G_i\)。这导致 \(g_1^{-1}gG_i=G_i\)，从而 \(gG_i=g_1G_i\)；于是 \(\alpha(g(i))=\alpha(g_1(i))\)，正如所断言。
最后，为证明 \(\alpha\) 是双射，我们来构造它的逆。设 \(gG_i\) 是 \(G_i\) 的一个陪集，则该陪集的所有元素都形如 \(gx\)，其中 \(x(i)=i\)。因此，对该陪集的所有元素 \(gx\)，有 \(gx(i)=g(i)\)。于是 \(g(i)\in i^G\) 就是 \(gG_i\) 在 \(\alpha\) 下的原像，且此原像唯一。
所以 \(G_i\) 的陪集个数为 \(|i^G|\)，引理得证。♦
例：在图 8.4 上验证引理 8.34 取 \(G=\mathrm{Aut}(M)\)，\(|G|=12\)（见后面的例 8.37）。
  1. 取 \(i=4\)：它的轨道 \(4^G=\{4\}\)，大小 \(1\)。稳定子 \(G_4\) = 全部把 \(4\) 固定的自同构 = 整个群，\(|G_4|=12\)。验证：\(|G|/|G_4|=12/12=1=|4^G|\)。
  2. 取 \(i=1\)：轨道 \(1^G=\{1,2,3\}\)，大小 \(3\)。稳定子 \(G_1\) = 固定 \(1\) 的自同构 = 可任意交换 \(2,3\)（\(2\) 种）× 可任意交换 \(5,6\)（\(2\) 种），共 \(|G_1|=4\)。验证：\(|G|/|G_1|=12/4=3=|1^G|\)。
  3. 取 \(i=5\)：轨道 \(5^G=\{5,6\}\)，大小 \(2\)。稳定子 \(G_5\) = 固定 \(5\)（从而固定 \(6\)）的自同构 = 可任意排列 \(1,2,3\)（\(3!=6\) 种），\(|G_5|=6\)。验证：\(12/6=2=|5^G|\)。
三处都满足“轨道大 ⟺ 稳定子小，且乘积恒为 \(|G|\)”。

请注意，“\(G_i\) 在 \(G\) 中的两个陪集必定要么不相交、要么相等”这一简单事实，在更一般的意义下也成立。更一般的版本见习题 12。

定义 8.35 设 \(G\) 是作用在集合 \(S\) 上的置换群，设 \(g\in G\)。令 \[F_g=\{\,i\in S\mid g(i)=i\,\}.\] （即 \(F_g\) 是被 \(g\) 保持不动的元素集合，其大小 \(|F_g|\) 就是 \(g\) 的不动点（fixed points）个数。）

主定理：Burnside 引理

现在我们可以宣布并证明本节的主要结果了。

定理 8.36 设 \(G\) 是作用在集合 \(S\) 上的置换群。则 \(S\) 在 \(G\) 作用下的轨道个数等于 \[\frac{1}{|G|}\sum_{g\in G}|F_g|.\]

这条定理是一个经典结果，它有许多名字，例如 Frobenius 定理、Cauchy 定理、Burnside 引理，或者由上述三个名字中某个非空子集拼成的名字。

主定理在说什么“本质不同的对象个数（= 轨道个数）”等于“群中每个元素 \(g\) 所固定的对象数 \(|F_g|\) 的平均值”。它把难以直接处理的“轨道大小不一”问题，转化为对每个对称逐个数“有多少染色不动”，再取平均——这是可操作的。

下面的例子提供了一个机会，让我们在证明定理之前先练习定理中的各个概念。

例 8.37 设 \(S\) 是图 8.4 所示图 \(M\) 的顶点集，并设 \(G=\mathrm{Aut}(M)\)。则 \(|G|=6\cdot2=12\)，因为顶点 \(1,2,3\) 可以任意互相置换（\(3!=6\) 种），顶点 \(5,6\) 可以任意互相置换（\(2!=2\) 种），且没有其他的自同构。
这 \(12\) 个自同构都会把 \(4\) 映到 \(4\)。其中一半会把 \(5\) 映到 \(5\)、\(6\) 映到 \(6\)，另一半会把 \(5\) 映到 \(6\)、\(6\) 映到 \(5\)。在集合 \(\{1,2,3\}\) 上，其中两个有三个不动点，六个有一个不动点，四个没有不动点。
所以总的说来：\(G\) 中有一个元素（恒等置换）有六个不动点；有四个元素有四个不动点（其中一个固定 \(1,2,3,4\)，另外三个对某 \(i\in[3]\) 固定 \(i,4,5,6\)）；有两个元素有三个不动点（固定 \(4,5,6\)）；有三个元素有两个不动点（对某 \(i\in[3]\) 固定 \(i\) 与 \(4\)）；有两个元素有一个不动点（固定 \(4\)）。
因此，定理 8.36 表明 \(G\) 在 \(S\) 上的轨道个数为 \[\frac{1}{|G|}\sum_{g\in G}|F_g|=\frac{1\cdot6+4\cdot4+2\cdot3+3\cdot2+2\cdot1}{12}=\frac{36}{12}=3,\] 这与我们已经看到的相符，即轨道为 \(\{1,2,3\}\)、\(\{4\}\) 与 \(\{5,6\}\)。
把例 8.37 的统计列成表
不动点个数这样的元素有几个对求和的贡献
6（恒等）1\(1\cdot6=6\)
44\(4\cdot4=16\)
32\(2\cdot3=6\)
23\(3\cdot2=6\)
12\(2\cdot1=2\)
合计\(1+4+2+3+2=12=|G|\)\(6+16+6+6+2=36\)
平均不动点数 \(=36/12=3=\) 轨道数。注意元素个数合计恰为 \(|G|=12\)，这是一个有用的自检。
证明（定理 8.36）. \(G\) 的轨道个数当然等于 \[\sum_{i}\frac{1}{|i^G|},\] 其中 \(i\) 取遍 \(S\) 的全部元素。的确，每条轨道对这个和的总贡献恰好是 \(1\)（一条大小为 \(m\) 的轨道里有 \(m\) 个元素，每个贡献 \(1/m\)，合计为 \(1\)）。现在我们如下变形这个和： \[\sum_{i}\frac{1}{|i^G|}=\sum_{i}\frac{|G_i|}{|G|}=\frac{1}{|G|}\sum_{i}|G_i|.\] 第一步用到了引理 8.34。最后这个等式很有希望，因为它已经含有因子 \(\dfrac{1}{|G|}\)，乘上一个求和。唯一的问题是：这个和是对所有 \(i\) 求的，而不是对 \(g\)。然而，仔细审视和式 \(\sum_i|G_i|\)，我们看到它实际上在计数所有满足 \(g\in G\)、\(i\in S\) 且 \(g(i)=i\) 的有序对 \((g,i)\)。因此，若改为先对 \(g\) 求和、再对 \(i\) 求和（交换求和次序），这个和不会改变。这表明 \[\sum_{i}|G_i|=\sum_{g\in G}|F_g|,\] 定理得证。♦
双重计数：为什么 \(\sum_i|G_i|=\sum_g|F_g|\) 两边都在数同一批“满足 \(g(i)=i\) 的有序对 \((g,i)\)”，只是数法不同：
  1. 左边：固定一个对象 \(i\)，数“有多少个 \(g\) 把它固定”，即 \(|G_i|\)；再对所有 \(i\) 求和。
  2. 右边：固定一个对称 \(g\)，数“它固定多少个对象”，即 \(|F_g|\)；再对所有 \(g\) 求和。
  3. 同一张“不动对照表”按行加与按列加，结果当然相同。这就是组合学里反复出现的双重计数思想。

应用：染色计数

在定理 8.36 的一个典型应用中，我们计数按某种定义“互不等价”的结构。结果表明，这种不等价意味着它们属于某个群作用下的不同轨道，而轨道的个数就是这些不等价结构的个数。于是我们用定理 8.36 计数轨道，并断定它等于不等价结构的个数。

让我们从一个非常简单的例子开始。

例 8.38 我们有一个带围栏的矩形后院，尺寸为 \(90\times100\)。我们想用红、蓝两种油漆给围栏的四条边上色，每条边只用一种颜色。如果两种染色仅相差一个 \(180^\circ\) 旋转就被视为等价，那么共有多少种不同的染法？
解：在这个例子里，旋转群 \(R\) 只由两个元素构成：恒等与 \(180^\circ\) 旋转。这个群作用在全部 \(16\) 种可能的染色上（若把四条边都看作可区分、且不把相差旋转的染色等同，则共有 \(2^4=16\) 种染色）。这个作用的轨道恰好就是各不等价的染色，因为两种染色相同当且仅当它们能通过旋转互相变换。恒等会固定全部 \(16\) 种染色；而 \(180^\circ\) 旋转会固定那些“对边同色”的染色，这样的染色有四种。因此，由定理 8.36，不等价染色的个数为 \[\frac{1}{2}(16+4)=10.\] ♦
上(红) 下(红) 右(蓝) 左(蓝) 恒等固定 16 种 180°固定“对边同色” 的 4 种 (16+4)/2 = 10
矩形（非正方形）只有 \(180^\circ\) 旋转这一个非平凡对称。\(180^\circ\) 旋转把上↔下、左↔右对调，故被它固定的染色须“对边同色”：上下各 \(2\) 种 × 左右各 \(2\) 种 \(=4\) 种。

下面的例子要稍微难一些。

例 8.39 我们用红或蓝给一个正方形的各边上色。若存在一个把一种染色变成另一种的对称（旋转或反射），就认为这两种染色等价。问共有多少种不等价的染色？
解：不难看出，正方形有八个对称：四个旋转（连同恒等在内，记为 \(r,r^2,r^3,\mathrm{id}\)）和四个反射。其中两个反射（\(a\) 和 \(b\)）是关于对角线的，另外两个（\(c\) 和 \(d\)）是关于平分对边的直线的。
这些对称会置换正方形的各边，并在此过程中把各种染色互相置换。所以它们正是作用在“全体染色集合”上的置换。现在我们来找出每个对称固定多少种染色。
  1. 每个对称都固定那些只用一种颜色的染色（共 \(2\) 种：全红、全蓝）。
  2. 旋转 \(r\) 与 \(r^3\) 不固定别的染色，因为它们把每条边映到相邻的边（若它们固定了某染色，则该染色只能用一种颜色）。故 \(|F_r|=|F_{r^3}|=2\)。
  3. 旋转 \(r^2\) 固定两个“双色”染色，即对边同色的那些。故 \(|F_{r^2}|=2+2=4\)。
  4. 反射 \(c\) 与 \(d\) 各固定两个双色染色，即在反射轴上彼此相交的那两条边须同色的染色。故 \(|F_c|=|F_d|=2+2=4\)。
  5. 反射 \(a\) 与 \(b\) 各固定六个双色染色（在这些染色里，平行于反射轴的两条边须同色）。见图 8.5 的列举。把这六个双色染色再加上全红、全蓝两种单色染色，得 \(|F_a|=|F_b|=6+2=8\)。
  6. 最后，\(\mathrm{id}\) 固定全部 \(16\) 种染色。
应用定理 8.36，并记住所有对称都固定那两个只用一种颜色的染色，得到不等价染色的个数为 \[\frac{1}{8}\bigl(2\cdot2+3\cdot4+2\cdot8+1\cdot16\bigr)=\frac{48}{8}=6.\] ♦
把例 8.39 的八个对称逐一列清楚 这里 \(|F_g|\) 已含“全红、全蓝”两种单色染色。把八个对称按“固定染色数”分组：
对称 \(g\)类型\(|F_g|\)
\(r\)旋转 90°2
\(r^3\)旋转 270°2
\(r^2\)旋转 180°4
\(c\)关于平分对边的轴反射4
\(d\)关于平分对边的轴反射4
\(a\)关于对角线反射8
\(b\)关于对角线反射8
\(\mathrm{id}\)恒等16
求和：\(\underbrace{2+2}_{2\cdot2}+\underbrace{4+4+4}_{3\cdot4}+\underbrace{8+8}_{2\cdot8}+\underbrace{16}_{1\cdot16}=4+12+16+16=48\)。除以 \(|G|=8\) 得 \(48/8=6\)。
说明：正文求和式 \(2\cdot2+3\cdot4+2\cdot8+1\cdot16\) 中的系数 \(2,3,2,1\) 正是“固定 \(2\) 种、\(4\) 种、\(8\) 种、\(16\) 种染色”各自的对称个数（\(2+3+2+1=8=|G|\)）。
反射 \(a\) 固定的 6 个双色染色：左、右两边（平行于轴）须同色，上、下两边各自任选 红 = 深红，蓝 = 深蓝；虚线为反射轴。左、右两边被轴互换故须同色，上、下两边各自不动可自由取色
图 8.5　反射 \(a\) 所固定的六个双色染色。其反射轴（图中虚线）使被它互换的一对边（这里取左、右两条平行于轴的边）必须同色，而被它各自保持不动的另一对边（上、下两条）可各自独立取色。于是固定的双色染色共有 \(2\)（上）\(\times\,2\)（下）\(\times\,2\)（左=右）\(-2\)（全红、全蓝）\(=6\) 个；再算上全红、全蓝两种单色染色，反射 \(a\) 共固定 \(8\) 种染色。

读者不应由此产生“给多边形的边上色是定理 8.36 的唯一应用”的印象。在补充习题 16 中，我们请读者用定理 8.36 重新证明“平均每个 \(n\)-置换有一个不动点”这一事实。在习题 13 中，我们请读者用同样的技巧证明 Fermat 的一个经典数论结果。习题 14 则声称：定理 5.7 只是引理 8.34 的一个特例。

即时自测
  1. 设 \(A\) 是四个顶点的完全图去掉一条边所得的图。若两种染色在“存在一个自同构把一种变成另一种”时视为相同，那么用红、蓝、绿三色给 \(A\) 的各边上色共有多少种方式？
  2. 求用红、蓝、绿给一个正五边形的各边上色的方式数，其中两种染色在“存在一个旋转或反射把一种变成另一种”时视为相同。
  3. 设 \(A\) 是在一个 \(C_5\)（五元圈）上添加一条对角线所得的图。若两种染色在存在一个把一种变成另一种的自同构时视为相同，求用红、蓝、绿给 \(A\) 的各边上色的方式数。

返回 全书目录