Pólya 计数

前置知识：置换和排列

引入

Pólya 计数原理通常用来解决一些涉及「本质不同」的计数问题．

本文可能涉及群论的相关内容

本文可能涉及到群论的相关内容．本文会对涉及到的群论概念做简单的解释，以便于不熟悉相关内容的读者理解和应用 Pólya 计数原理．关于群论的内容，严格的表述和讨论请参考 抽象代数基本概念、群论 等章节．

「空间对称群」、「对称群」与「置换群」

本文中将不可避免地同时使用这三类群的名字．尽管可能很容易造成混淆，但它们确实代指不同的概念．给定几何结构，它上面的对称操作指的是能够使它与它自身重合的几何变换，而空间对称群（symmetry group）就是这些对称操作的集合．对称群（symmetric group）是给定集合上的全体置换的集合．置换群（permutation group）则是对称群的子群，即一些（未必是全体）置换构成的群．后文会解释如何将给定几何结构的空间对称群表示成置换群的形式，并用于计数问题．

Burnside 引理

相关阅读：Burnside 引理

Pólya 计数原理是 Burnside 引理的应用和推广．在介绍 Pólya 计数原理之前，需要先简单地回顾 Burnside 引理的内容．

为了总结出一般的规律，首先考虑简单的例子．

项链染色

现在有一串共四个珠子的项链，每个珠子可以是红色或者蓝色，计算共有几种本质不同的珠子．（如果两种染色的结果可以通过旋转项链重合，就认为是相同的．)

解答和分析

这个问题足够简单，可以通过枚举的方式加以解答．珠子共计 $4$ 个，每个珠子可以染 $2$ 种颜色，所以，项链所有可能的染色方案共计 $2^4=16$ 种．将可以通过旋转相互得到的分到一组，共计 $6$ 组，如下图所示．（其中，单个染色方案的编码表示了自左下角的珠子开始顺时针染的颜色，$B$ 表示蓝色，$R$ 表示红色；分到同一组的染色方案的编码有着相同的背景颜色．）

从这个例子中可以看到，要计算本质不同的染色的种类数，关键其实是知道每种本质相同的染色对应几种不同的染色方案．也就是说，要搞清楚上图中每个分组的大小．

能够分到同一个组中的染色方案，就是指它们之间能够通过旋转操作互相转化的染色方案．总共有 $4$ 种旋转的方式，即

$$G=\{r_0,r_1,r_2,r_3\},$$

分别表示旋转 $0,1,2,3$ 次．旋转 $0$ 次就是原地不动．

首先看染色方案 $RRBB$ 所在的分组．对它施加这四种操作，将分别得到

$$RRBB, RBBR, BBRR, BRRB.$$

四种染色方案互不相同，因此这个组就有 $4$ 个元素．

再看染色方案 $BRBR$ 所在的分组．对它同样施加这四种操作，将分别得到

$$BRBR, RBRB, BRBR, RBRB.$$

此时，旋转两次的结果和不旋转的结果是一致的，旋转三次和旋转一次的结果是一致的．所以，这个组就有 $2$ 个元素．

如果看染色方案 $BBBB$ 和 $RRRR$ 所在的分组．对它们施加四种操作得到的结果都是它们自身．因而，每个组就只有 $1$ 个元素．

如果用 $x$ 表示染色方案，$Gx$ 表示对染色方案 $x$ 操作后能够得到的颜色编码的集合，那么从上面的例子可以总结出一个规律，那就是 $G$ 的操作对于 $x$ 的影响存在某种「周期性」．

设 $|G|$ 表示操作的总个数，这种影响的「周期性」意味着，如果有 $m$ 个不同的 $G$ 中的操作将染色方案 $x$ 变换到它自身，那么 $x$ 在这些操作下的结果就会重复出现 $m$ 次．因而，染色方案 $x$ 在这些操作下共计有 $|G|/m$ 种不同的结果，这也就是 $x$ 所在分组的大小．

这个例子中，因为只有旋转零次 $r_0$ 才能够将 $RRBB$ 变换到它自身，所以，它所在分组的大小等于 $4/1=4$；而旋转零次 $r_0$ 和两次 $r_2$ 都能将 $BRBR$ 变换到它自身，所以，它所在分组的大小等于 $4/2=2$；无论旋转几次都能将 $BBBB$ 变换到它自身，所以，它所在分组的大小就是 $4/4=1$．

在下面的叙述中，用 $G_x$ 表示能够将 $x$ 变换到它自身的操作的数目，所以，$|G_x|$ 就是上面的 $m$．此时，$X$ 所在分组大小是 $|G|/|G_x|$．要计算染色方案的分组的数目，只需要穷举所有可能的染色方案 $x\in X$，对所在分组大小为 $|Gx|$ 的染色方案 $x$ 赋以权重 $1/|Gx|$，就能够将分组的数目表达为

$$|X/G|=\sum_{x\in X}\frac{1}{|Gx|}=\sum_{x\in X}\frac{|G_x|}{|G|}.$$

现在这个式子的形式并不便于应用．记 $gx$ 是对染色方案 $x\in X$ 应用操作 $g\in G$ 的结果，那么上面描述的集合 $G_x$ 就是 $\{g\in G:gx=x\}$，所以交换求和顺序就有

$$\begin{aligned} \sum_{x\in X}|G_x| &=\sum_{x\in X}|\{g\in G:gx=x\}|\\ &=\sum_{x\in X}\sum_{g\in G}[gx=x]\\ &=\sum_{g\in G}\sum_{x\in X}[gx=x]\\ &=\sum_{g\in G}|\{x\in X:gx=x\}|\\ &=\sum_{g\in G}|X^g|. \end{aligned}$$

其中 $[\cdot]$ 为 Iverson 括号．交换求和记号的结果中，$X^g=\{x\in X:gx=x\}$ 是指在操作 $g$ 下保持不变的染色方案 $x$ 的集合．简言之，它是操作 $g$ 的不动点．

在这些讨论之后，现在可以将分组的个数写作

$$|X/G|=\frac{1}{|G|}\sum_{g\in G}|X^g|.$$

也就是说，分组的个数是各种旋转操作的不动点的平均个数．

作为这个结果的应用，再次计算项链染色的个数．这些旋转操作的不动点可以列举如下．

操作	不动点
$r_0$	$X$
$r_1$	$\{BBBB,RRRR\}$
$r_2$	$\{BBBB,BRBR,RBRB,RRRR\}$
$r_3$	$\{BBBB,RRRR\}$

因而，分组的个数就等于

$$\frac{16+2+4+2}{4} = 6.$$

这样就得到了前面的结果．

从这个例子中，可以归纳出一般的结果，用于求解这类计数问题．为了方便讨论，本文考虑的情景是染色问题，当然也可以应用到别的情景上去，在文末会提供相应的例子．

染色问题是说，给定某个结构，在它的每个顶点上染色，会得到不同的染色方案．这个结构拥有某种对称性，使得看似不同的染色方案在经过一系列对称操作后能够互相转化．这些能互相转化的染色方案就称为本质相同的．问题是要求解本质不同的染色的数目．

根据例子中的分析，要求解这样的问题，首先要讨论给定的结构都有哪些对称操作．这些对称操作的集合 $G$ 称为给定结构的空间对称群．实际应用中，大多时候无需了解群的定义，只需要能够不重不漏地讨论所有的空间对称操作就可以了．本文后面分析了几个常见的空间对称群的结构，那里解释了群的定义．

所有染色方案的集合记作 $X$，其中的单个染色方案记作 $x$．操作 $g\in G$ 作用在染色方案 $x\in X$ 的结果是 $gx$．那么，能够通过某个操作作用在染色方案 $x$ 上的所有结果就是 $Gx=\{gx:g\in G\}$，它称为群 $G$ 作用下 $x$ 的轨道．同一轨道中的不同染色方案就是这类问题中所谓「本质相同」的．故而，所有本质不同的染色的数目，就等价于不同轨道的数目．

例子中的分析可以推广到一般的情形．

Burnside 引理

给定群 $G$ 在集合 $X$ 上的作用，则所有不同的轨道的数目

$$|X/G|=\frac{1}{|G|}\sum_{g\in G}|X^g|.$$

这里，$X^g=\{x\in X:gx=x\}$ 是 $g\in G$ 的作用下的不动点集合．

它的证明几乎就是照搬上面例子中的分析．但是，例子中用到了观察，即群 $G$ 在单个元素 $x$ 上的作用结果具有某种「周期性」，所以，这种周期重复的数目就等于能将 $x$ 变换到它自身的操作的数目．这个观察在一般的情形是正确的，但是因为群 $G$ 的结构可能很复杂，它的「周期性」未必是例子中呈现的那么直接．严格地表述这个观察，需要用到群论中的 轨道稳定子定理（orbit-stabilizer theorem）．

在应用的时候，只要能够列举出所有的对称操作，并且给出每个对称操作对应的不动点数目就可以解决对应的计数问题．下面是一个稍微复杂的应用．

立方体染色

用三种颜色给一个立方体染色，求本质不同的方案数（经过空间旋转后相同的两种方案视为同一种）．

解答

因为立方体有 $6$ 个面，每个面有 $3$ 中染色方法，所以，总共有 $3^6$ 种染色方案，即 $|X|=3^6$．记立方体的空间对称群为 $G$．

接下来我们需要对 $G$ 中的所有操作进行分析，它们可以分为以下几类（方便起见，将立方体的六个面分别称为前、后、上、下、左、右）：

• 不动：即恒等变换，因为所有直接染色方案经过恒等变换都不变，因此它对应的 $|X^g|=3^6$；
• 以两个相对面的中心连线为轴的 $90^\circ$ 旋转：相对面有 $3$ 种选择，旋转的方向有 $2$ 种选择，因此这类共有 $6$ 个置换．假设选择了前、后两个面中心的连线为轴，则必须要满足上、下、左、右四个面的颜色一样，才能使旋转后不变．此时，有 $3$ 个可以独立染色的区域，因此它对应的 $|X^g|=3^3$；
• 以两个相对面的中心连线为轴的 $180^\circ$ 旋转：相对面有 $3$ 种选择，旋转方向的选择没有影响，因此这类共有 $3$ 个置换．假设选择了前、后两个面中心的连线为轴，则必须要满足上、下两个面的颜色一样，左、右两个面的颜色一样，才能使旋转后不变．此时，有 $4$ 个可以独立染色的区域，因此它对应的 $|X^g|=3^4$；
• 以两条相对棱的中点连线为轴的 $180^\circ$ 旋转：相对棱有 $6$ 种选择，旋转方向对置换依然没有影响，因此这类共有 $6$ 个置换．假设选择了前、上两个面的边界和下、后两个面的边界作为相对棱，则必须要满足前、上两个面的颜色一样，下、后两个面的颜色一样，左、右两个面的颜色一样，才能使旋转后不变．此时，有 $3$ 个可以独立染色的区域，因此它对应的 $|X^g|=3^3$；
• 以两个相对顶点的连线为轴的 $120^\circ$ 旋转：相对顶点有 $4$ 种选择，旋转的方向有 $2$ 种选择，因此这类共有 $8$ 个置换．假设选择了前面的右上角和后面的左下角作为相对顶点，则必须满足前、上、右三个面的颜色一样，后、下、左三个面的颜色一样，才能使旋转后不变．此时，有 $2$ 个可以独立染色的区域，因此它对应的 $|X^g|=3^2$．

因此，所有本质不同的染色方案数为

$$\frac{1\times3^6+6\times3^3+3\times3^4+6\times3^3+8\times3^2}{1+6+3+6+8}=57.$$

Pólya 计数原理

在 Burnside 引理的叙述中，并没有用到集合 $X$ 是某结构上的全部染色方案这一性质．其实，Burnside 引理的应用范围并不局限于染色计数问题．对于染色计数问题，Pólya 计数原理则提供了更为准确的计算方法．它可以看作是一般性的 Burnside 引理在染色计数问题上的应用．

相较于 Burnside 引理，Pólya 计数原理的改进就是提供了不动点集合大小 $|X^g|$ 在染色计数问题中的具体计算方法．

这一点从上面的立方体染色的例子可以直观地看出来．对于正方体的各种对称操作，它的不动点集合的大小都是 $m^{c(g)}$ 的形式，这里 $m$ 是颜色的数目，$c(g)$ 是在操作 $g$ 下可以独立染色的区域数目．这个观察在一般的情形下也是成立的，不过需要进一步明晰如何对给定的 $g$ 计算 $c(g)$ 的取值．

给某个结构选择一种染色方案，用数学语言表示，就是选择一个从这个结构的可以染色的对象（比如项链中的珠子、立方体的面等）的集合 $X$ 到颜色集合 $C$ 的映射 $f:X\rightarrow C$．因此，染色方案的集合就是 $C^X$．该结构的空间对称群 $G$ 作用在结构上，自然也连带着作用在集合 $X$ 上．这种对称操作，总对应着集合 $X$ 上的双射，即 置换（permutation）．¹

现在分析不动点集合 $(C^X)^g$ 的结构．给定 $g$，看作 $X$ 上的置换，比照例子中的分析可以知道，如果 $X$ 中的位置 $x$ 在有限次重复操作 $g$ 之后可以移动到位置 $y$，那么，作为不动点 $f\in (C^X)^g$，必然需要满足 $f(x)=f(y)$．用上一节轨道的语言来说，因为位置 $x$ 和位置 $y$ 处于操作 $g$ 作用²的同一个轨道上，所以它们需要染相同的颜色．用置换的语言来说，在置换 $g$ 的 轮换分解 中，位置 $x$ 和位置 $y$ 处于同一轮换，故而需要染相同的颜色．轮换分解中不同的轮换的染色不必相同，可以独立染色，所以此时可以独立染色的区域数目就是 $c(g)$，即 $g$ 的轮换分解中的轮换数目．

由此，操作 $g$ 的不动点的数目就是 $|C|^{c(g)}$．将这个结论代入 Burnside 引理，就能得到无权重版本的 Pólya 计数原理（Pólya enumeration theorem）．

Pólya 计数原理（无权重版本）

给定群 $G$ 在集合 $X$ 上的作用和颜色集合 $C$，则不同的染色方案的数目

$$|C^X/G|=\frac{1}{|G|}\sum_{g\in G}m^{c(g)},$$

这里，$m$ 是颜色数目，$c(g)$ 是元素 $g\in G$ 的置换表示的轮换分解中的轮换数目．

关于群 $G$ 的含义

这里略微有些滥用记号．如果群 $G$ 作用在 $X$ 上，那么染色方案集合 $C^X$ 上的群作用是需要重新定义的，这里没有加以区分．

作为 Pólya 计数原理的简单应用，下面重新用 Pólya 计数原理计算前文的例子．

项链染色问题另解

将四个珠子标号 $1\sim 4$，则例子中的群 $G$ 中的元素分别有置换表示如下：（均写作轮换分解的形式）

• 旋转零次 $r_0=(1)$，共计 $4$ 个轮换（注意省略的 $1$‑轮换）；
• 旋转一次 $r_1=(1234)$，共计 $1$ 个轮换；
• 旋转二次 $r_2=(13)(24)$，共计 $2$ 个轮换；
• 旋转三次 $r_3=(1432)$，共计 $1$ 个轮换．

因此，本质不同染色的数目是

$$\frac{2^4+2^1+2^2+2^1}{4}=6.$$

立方体染色问题另解

由于前文的分析实质上已经给出了各类置换的轮换表示，只是没有用数字符号显式地书写出来，这里不再重复前文的分析．仅仅考虑以相对棱的中点连线为轴的 $180^\circ$ 旋转的情形，加以示例．将前、后、上、下、左、右六个面依次编号为 $1\sim6$，此时对应的置换是 $(13)(24)(56)$，因此 $c(g)=3$．其它类型的置换也可以类似分析，最后的计数的表达式也和上文完全一致．

带权重形式的推广

无权重版本的 Pólya 计数原理只能够给出所有的本质不同的染色问题的计数，但是在处理更为精细的问题时就无能为力了．比如说，如果在上述染色问题中，给定每种可以使用的颜色的数目，就不能套用上面的 Pólya 计数公式．在实际求解这类问题时，需要再次使用 Burnside 引理加以推导；而将这些结果总结为生成函数的形式，就是带权重版本的 Pólya 计数原理．

项链染色（带限制）

现在有一串共四个珠子的项链，每个珠子可以是红色或者蓝色，恰有两个红色珠子、两个蓝色珠子可以使用，计算共有几种本质不同的珠子．（如果两种染色的结果可以通过旋转项链重合，就认为是相同的．)

解答和分析

考虑使用 Burnside 引理．红色、蓝色珠子各两个，共计有 $\dbinom{4}{2}=6$ 种染色方案．空间对称群 $G=\{r_0,r_1,r_2,r_3\}$ 分别对应旋转 $0\sim3$ 次，则它们对应的不动点集合分析如下：

• 旋转零次 $r_0=(1)$，全部 $6$ 个染色方案都是不动点；
• 旋转一次 $r_1=(1234)$，不动点要求所有珠子染同样的颜色，没有不动点；
• 旋转两次 $r_2=(13)(24)$，有两个可独立染色的区域，大小都是 $2$，它们要分别染成红色和蓝色，则不动点集合的大小为 $2$；
• 旋转三次 $r_3=(1432)$，与旋转一次的情形相同，没有不动点．

所以，根据 Burnside 引理，本质不同的染色数目为

$$\frac{6+0+2+0}{4}=2.$$

从这个例子中可以总结出如下计算方法．对于限制不同颜色个数的问题，同样是要把空间对称群中各个置换的轮换分别染色，但是需要让染色用到的颜色数目恰好等于给定的颜色个数．这样的组合问题通常没有显式解，除了可以通过 排列组合方法 计算的特殊情形外，需要看做 背包问题 进行求解．

通过生成函数可以给出这类计数问题的答案．给定置换 $g$，如果它的 型 是 $1^{\alpha_1}2^{\alpha_2}\cdots n^{\alpha_n}$，即它有 $\alpha_k$ 个长度为 $k$ 的轮换，且对于每个轮换可以染成 $m$ 种颜色中的一种，那么生成函数

$$\prod_{k=1}^n\left(\sum_{i=1}^mx_i^k\right)^{\alpha_k}$$

中单项式 $x_1^{\beta_1}x_2^{\beta_2}\cdots x_m^{\beta_m}$ 的系数就是第 $i$ 种颜色用了 $\beta_i$ 次的计数．这里圆括号中的表达式 $\sum_{i=1}^mx_i^k$ 的组合意义是，对于长度为 $k$ 的轮换，用到 $k$ 次颜色 $i$ 的染色方法的计数是 $1$，对于其它情形，计数是 $0$；这正描述了同一轮换中各位置染色一致的要求．

给定置换 $g$ 下染色计数的生成函数，对各个单项式应用 Burnside 引理，就得到各种颜色组合下的本质不同的计数．因为生成函数对各个单项式是线性的，所以本质不同染色方案的计数的生成函数是

$$\frac1{|G|}\sum_{g\in G}\prod_{k=1}^n\left(\sum_{i=1}^mx_i^k\right)^{\alpha_k}.$$

展开这个式子，每个单项式的系数就给出了给定颜色组合下的本质不同染色的计数．

在上述过程中，对每个轮换进行染色的生成函数 $\sum_{i=1}^mx_i^k$ 并无特殊之处，可以替换成其它的生成函数．因而，有如下的一般版本的 Pólya 计数原理．

置换群的轮换指标

给定置换群 $G$，则群 $G$ 的 轮换指标（cycle index），定义为

$$Z_G(t_1,t_2,\cdots,t_n)=\frac{1}{|G|}\sum_{g\in G}t_1^{c_1(g)}t_2^{c_2(g)}\cdots t_n^{c_n(g)},$$

其中，$c_k(g)$ 是置换 $g$ 的轮换分解中长度为 $k$ 的轮换的个数，即 $1^{c_1(g)}2^{c_2(g)}\cdots n^{c_n(g)}$ 是置换 $g$ 的型．

Pólya 计数原理（带权重版本）

给定群 $G$ 在集合 $X$ 上的作用，对每个点的染色方法由它的染色方案的计数的生成函数 $f(x_1,x_2,\cdots,x_m)$ 给出，那么集合 $X$ 的本质不同染色方案的计数的生成函数是

$$Z_G(f(x_1^1,x_2^1,\cdots,x_m^1),f(x_1^2,x_2^2,\cdots,x_m^2),\cdots,f(x_1^n,x_2^n,\cdots,x_m^n)),$$

这里，$Z_G(t_1,t_2,\cdots,t_n)$ 是群 $G$ 的轮换指标．

这里，如果单个位置的染色的生成函数是 $f(x_1,x_2,\cdots,x_m)$，那么长度为 $k$ 的轮换的染色的生成函数就是 $f(x_1^k,x_2^k,\cdots,x_m^k)$．这反映了如果某一染色方案是给定置换的不动点，那么同一轮换中的所有位置必须染相同的颜色．如果将生成函数在 $x_i=1$ 处取值，就得到上文的无权重版本的 Pólya 计数原理．

定理的叙述用到了置换群的轮换指标的概念．它和具体的染色问题无关．它描述了置换群的结构．

带限制的项链染色问题另解

旋转对称群的轮换指标是 $\dfrac14\left(t_1^4+t_2^2+2t_4\right)$，单点染色的生成函数是 $r+b$，故而全体染色方案的生成函数是

$$\begin{aligned} F(r,b)&=\frac14\left((r+b)^4+(r^2+b^2)^2+2(r^4+b^4)\right)\\ &=r^4+r^3b+2r^2b^2+rb^3+b^4. \end{aligned}$$

所求计数就是 $r^2b^2$ 的系数，即共 $2$ 种本质不同染色．顺便，这个式子也给出了其他限制下的计数．

应用

带权重版本的 Pólya 计数原理在组合计数问题中起到重要的作用．这里简单讨论它的应用，而更一般的讨论可以参考 组合问题的形式化方法．

钻石项链

现在有一串共四个相同珠子的项链，每个珠子上可以镶若干颗钻石．如果有四枚钻石，总共有多少本质不同的镶钻方式．（如果两种镶钻的结果可以通过旋转项链重合，就认为是相同的．)

解答和分析

项链的空间对称群仍与前文所述相同．不考虑钻石总数的限制，则单个位置的镶钻方案的生成函数是

$$f(x)=1+x+x^2+\cdots=\sum_{i=1}^\infty x^i=\frac{1}{1-x}.$$

应用带权重版本的 Pólya 计数原理可知，所有镶钻方案的生成函数为

$$\begin{aligned} F(x)&=\frac14\left(f(x)^4+f(x^2)^2+2f(x^4)\right)\\ &=1+x+3x^2+5x^3+10x^4+\cdots. \end{aligned}$$

故而，所求镶钻方案的数目就是 $x^4$ 的系数，即共计 $10$ 种方案．作为验证，通过枚举可知，它们分别是

$$4000,3100,3010,3001,2200,2020,2110,2101,2011,1111.$$

这里，每组四个数字分别表示每个珠子上的镶钻数目．

这个例子说明，带权重版本的 Pólya 计数原理能够解决的问题远比染色计数问题要广泛．它提供了一种将单点的计数扩展到整个结构上本质不同的计数的方法．染色问题只是这类问题的特例．

常见空间对称群

Pólya 计数相关问题的难点之一在于分析置换群的结构．这里，简单讨论常见的空间对称群的结构，并用它们的轮换指标加以描述．应当注意，对于同一个结构的空间对称群，如果考虑的作用对象的集合不同，相应的 群作用 也就不同，因而它们的置换表示也就不同．比如说，正方体的空间对称群对于它的顶点、棱、面的作用就分别对应着正方体的顶点置换群、棱置换群和面置换群，顶点、棱、面的个数互不相同，故而这些置换群以及对应的轮换指标当然也各不相同．所以，在具体问题的求解中，不能忽视群作用的对象的指定．

空间对称群和置换群的关系

虽然两者概念上十分相似，但是它们绝不是同一个对象．用群论的语言说，给定空间对称群 $G$ 和它在集合 $X$ 上的群作用，群作用的置换表示实则提供了一个从群 $G$ 到对称群 $S_X$ 的同态 $\varphi$，而且这个置换表示在组合计数的语境下往往是忠实的，即 $\ker\varphi=\{e\}$，故而同态 $\varphi$ 实则是群 $G$ 到群 $S_X$ 内的一个嵌入．文中的置换群则是这个嵌入的像，即 $\varphi(G)$，它与本身的空间对称群 $G$ 同构．因此，对于同样的结构上的空间对称群 $G$，如果群作用的选取不一致，就会同构于不同的置换群 $\varphi(G)$，进而具有不同的轮换指标（同构的置换群的轮换指标未必相同）．

给定一个结构，它的空间对称群是所有能够将它变换到它自身的操作的集合．它必然满足如下条件：

• 对给定结构连续应用两个对称操作，可以视作应用另一个对称操作，即对称操作的集合对于复合是满足封闭性的；
• 对称操作的复合满足结合律；
• 存在恒等的对称操作，即给定结构保持不变本身也视作一个操作；
• 任何操作都存在它的逆操作，可以抵消给定操作的效果．

群 是对所有满足这些条件的概念的抽象．对于群的结构的讨论，就是 群论 的主要研究内容．这里的分析主要集中在空间对称群，对它的结构的讨论也主要应用几何观点．这里给出了常见的例子，读者应当从中获得分析这类问题的常见思路．

循环群

给定正 $n$ 边形，它的全体旋转操作构成的空间对称群称为循环群（cyclic group），记作 $C_n$．将逆时针旋转 $(360/n)^\circ$ 的操作记作 $r$，则群 $C_n$ 的元素可以写作

$$C_n=\{e,r,r^2,\cdots,r^{n-1}\}.$$

这里，$r^k$ 指对操作 $r$ 重复 $k$ 次的结果，即逆时针旋转 $(360k/n)^\circ$，而 $e=r^0$ 指恒等变换．

无论是考虑循环群对正 $n$ 边形的全体顶点还是全体边的集合的作用，它的置换表示都是一样的．以全体顶点的集合为例分析群作用的置换表示．它的轮换指标是

$$Z(C_n)=\frac1n\sum_{d\mid n}\varphi(d)t_{d}^{n/d}.$$

这里，$\varphi(\cdot)$ 是数论中的 欧拉函数．

只计旋转操作，长度为 $n$ 的项链的空间对称群就是 $C_n$．

分析

设顶点的集合按照逆时针顺序记为 $\{0,1,\cdots,n-1\}$，则 $r^k(i)=i+k\bmod n$．顶点 $i$ 所在的轮换中的顶点集合就是

$$\{i+\ell k\bmod n:\ell\in\mathbf Z\}.$$

显然，$i\equiv i+\ell k\pmod n$ 当且仅当

$$\frac{n}{\gcd(k,n)}\mid\ell.$$

这意味着，任何顶点 $i$ 所在的轮换长度都是 $\dfrac{n}{\gcd(k,n)}$．因此，置换 $r^k$ 有 $\gcd(k,n)$ 个等长的轮换．考虑在轮换指标的表达式中合并同类项，给定 $d\mid n$，则满足 $\gcd(k,n)=n/d$ 的 $k$ 共计 $\varphi(d)$ 个，它们对应的单项式都是 $t_d^{n/d}$ 的形式，所以可以得到上面的轮换指标表达式．

二面体群

给定正 $n$ 边形，它的全体旋转和关于对称轴翻转的操作也构成空间对称群，它称为二面体群（dihedral group），记作 $D_{2n}$．将逆时针旋转 $(360/n)^\circ$ 的操作记作 $r$，并将沿某个给定对称轴（比如中心与某个顶点的连线）翻转的操作记作 $s$，则群 $D_{2n}$ 的操作可以写作

$$D_{2n}=\{e,r,\cdots,r^{n-1},s,sr,\cdots,sr^{n-1}\}.$$

这里，$r^k$ 依然是旋转操作，而 $sr^k$ 虽然是先进行 $k$ 次旋转再沿给定对称轴翻转，但是可以等价地看作沿着另一个对称轴翻转．因此，群 $D_{2n}$ 中共计 $1$ 个恒等变换、$(n-1)$ 个旋转操作和 $n$ 个翻转操作．它对顶点集合和边集合的群作用也有着相同的置换表示．它的轮换指标是

$$Z(D_{2n})=\frac12Z(C_n)+ \begin{cases} \dfrac12t_1t_2^k,&n=2k+1,\\ \dfrac14\left(t_1^2t_2^{k-1}+t_2^k\right),&n=2k. \end{cases}$$

分析

群 $D_{2n}$ 中的旋转操作 $r^k$ 的集合（包括恒等变换）的分析和循环群 $C_n$ 如出一辙，关键在于剩下的翻转操作的分析．此时需要对顶点个数 $n$ 的奇偶性分类讨论．

当 $n=2k+1$ 时，所有的翻转操作的对称轴都是连结顶点和它对面的边的中点的，共计 $n$ 条这样的对称轴．每个翻转操作后，对称轴上的顶点保持不动，而其它顶点成对地交换，因此有 $1$ 个不动点（$1$‑轮换）和 $k$ 个 $2$‑轮换．

当 $n=2k$ 时，有两种对称轴．其中，一半的对称轴是连接相对的顶点的；沿着这样的对称轴翻转，将保持对称轴上的两个顶点不动，而将其余的顶点成对地交换，因此有 $2$ 个不动点（$1$‑轮换）和 $(k-1)$ 个 $2$‑轮换．另一半的对称轴是连接相对的边的中点的；沿着这样的对称轴翻转，将所有顶点都成对地交换，因此有 $k$ 个 $2$‑轮换．

根据这一分析，可以写出上面的轮换指标表达式．

对称群

给定 $n$ 个元素，它上面的全体置换构成群，称为 $n$ 次对称群（symmetric group），记作 $S_n$．它描述了这 $n$ 个顶点能拥有的全部对称性．它也是这些对称操作对顶点集合的作用的置换表示．

根据 置换与排列 一文的分析，它的轮换指标是

$$Z(S_n)=\sum_{a_1+2\alpha_2+\cdots+n\alpha_n=n}\frac{t_1^{\alpha_1}t_2^{\alpha_2}\cdots t_n^{\alpha_n}}{1^{\alpha_1}2^{\alpha_2}\cdots n^{\alpha_n}\alpha_1!\alpha_2!\cdots\alpha_n!}.$$

这里用到了型为 $1^{\alpha_1}2^{\alpha_2}\cdots n^{\alpha_n}$ 的置换的计数是

$$\frac{n!}{1^{\alpha_1}2^{\alpha_2}\cdots n^{\alpha_n}\alpha_1!\alpha_2!\cdots\alpha_n!}.$$

它满足递推关系

$$Z(S_n)=\frac1n\sum_{k=1}^nt_kZ(S_{n-k}),$$

而递推起点是 $Z(S_0)=1$．这一递推关系的组合意义是，要构造长度为 $n$ 的置换，可以首先选取点 $n$ 所在轮换的长度 $k$，再对剩下的 $(n-k)$ 个顶点的集合构造．

给定 $n$ 个顶点的完全图，则它的空间对称群正是 $S_n$．它对全体顶点的集合的作用的轮换指标就由上文的 $Z(S_n)$ 给出．但是，它对全体边的集合的作用的置换表示并不相同．比如说，集合的大小就不相同，全体边的数目是 $n(n-1)/2$．对于边的情形，需要额外的分析．这里给出简单的例子，一般的情形可参考习题．

无向简单图计数

计算同构意义下有 $4$ 个顶点的无向简单图的数目．

解答

这相当于在有 $4$ 个顶点的完全图上染两种颜色，要求本质不同的染色数目．空间对称群是 $S_4$，现在分析它的边置换群 $S_4^{(2)}$ 的轮换指标．

• 恒等变换（$1$ 种）：边也保持不动，故对应单项式为 $t_1^6$；
• 交换两顶点（$6$ 种）：假设交换 $a$ 和 $b$，则边 $1$ 和边 $3$ 保持不动，同时，边 $2$ 和边 $5$ 对换，边 $4$ 和边 $6$ 对换，故对应单项式为 $6t_1^2t_2^2$；
• 轮换三顶点（$8$ 种）：假设轮换是 $(abc)$，则它们之间的连边 $1,2,5$ 也相应轮换，它们和第四点 $d$ 的连边 $4,6,3$ 也相应轮换，故对应单项式为 $8t_3^2$；
• 交换两对顶点（$3$ 种）：假设点 $a$ 和点 $b$ 对换，点 $c$ 和点 $d$ 对换，则边 $1$ 和边 $3$ 保持不动，同时，边 $2$ 和边 $4$ 对换，边 $5$ 和边 $6$ 对换，故对应单项式为 $3t_1^2t_2^2$；
• 轮换四顶点（$6$ 种）：假设轮换是 $(abcd)$，则其中相邻顶点的连边 $1,2,3,4$ 也相应轮换，相对顶点的连边 $5,6$ 同时对换，故对应的单项式为 $6t_2t_4$．

所以，边置换群的轮换指标是

$$Z(S_4^{(2)})=\dfrac{1}{24}(t_1^6+9t_1^2t_2^2+8t_3^2+6t_2t_4).$$

根据 Pólya 计数原理，同构意义下有 $4$ 个顶点的无向简单图的数目是

$$\frac{2^6+9\times 2^4+8\times 2^2+6\times 2^2}{24} = 11.$$

多面体群

多面体群（polyhedral group）是正多面体的空间对称群．正多面体只有五种：正四面体、正方体、正八面体、正十二面体和正二十面体．如果保持点、棱、面之间的邻接关系，交换点和面，可以得到对偶的正多面体．其中，正四面体和它自身对偶，正方体和正八面体对偶，正十二面体和正二十面体对偶．利用对偶关系，可以简化它们的空间对称群的讨论．

只计三维空间中可以进行的旋转操作，它们的空间对称群只有三种．

• 四面体群（tetrahedral group），即正四面体的空间对称群：

  • 恒等变换；
  • 绕顶点和对面中心的连线旋转 $120^\circ$ 和 $240^\circ$；
  • 绕对边的中点的连线旋转 $180^\circ$．

  共计 $1+2\times4+1\times3=12$ 个对称操作．

  它对应的置换群的轮换指标如下．

  • 顶点置换群和面置换群：$\dfrac1{12}\left(t_1^4+8t_1t_3+3t_2^2\right)$；
  • 棱置换群：$\dfrac1{12}\left(t_1^6+8t_3^2+3t_1^2t_2^2\right)$．

• 八面体群（octahedral group），即正方体（和正八面体）的空间对称群：

  • 恒等变换；
  • 绕相对顶点的连线旋转 $120^\circ$ 和 $240^\circ$；
  • 绕相对的棱的中点的连线旋转 $180^\circ$；
  • 绕相对的面的中心的连线旋转 $90^\circ$，$180^\circ$ 和 $270^\circ$．

  共计 $1+2\times 4+1\times 6+3\times 3=24$ 个对称操作．

  它对应的正方体的置换群的轮换指标如下．

  • 顶点置换群：$\dfrac{1}{24}\left(t_1^8+8t_1^2t_3^2+9t_2^4+6t_4^2\right)$；
  • 棱置换群：$\dfrac{1}{24}\left(t_1^{12}+8t_3^4+6t_1^2t_2^5+6t_4^3+3t_2^6\right)$；
  • 面置换群：$\dfrac{1}{24}\left(t_1^6+8t_3^2+6t_2^3+6t_1^2t_4+3t_1^2t_2^2\right)$．

  正八面体的置换群类似，只是要将顶点和面的角色对换．

• 二十面体群（icosahedral group），即正十二面体（和正二十面体）的空间对称群：

  • 恒等变换；
  • 绕相对顶点的连线旋转 $120^\circ$ 和 $240^\circ$；
  • 绕相对的棱的中点的连线旋转 $180^\circ$；
  • 绕相对的面的中心的连线旋转 $72^\circ$，$144^\circ$，$216^\circ$ 和 $288^\circ$．

  共计 $1+2\times 10+1\times 15+6\times 4=60$ 个对称操作．

  它对应的正十二面体的置换群的轮换指标如下．

  • 顶点置换群：$\dfrac{1}{60}\left(t_1^{20}+20t_1^2t_3^6+15t_2^{10}+24t_5^4\right)$；
  • 棱置换群：$\dfrac{1}{60}\left(t_1^{30}+20t_3^{10}+15t_1^2t_2^{14}+24t_5^6\right)$；
  • 面置换群：$\dfrac{1}{60}\left(t_1^{12}+20t_3^4+15t_2^6+24t_1^2t_5^2\right)$．

  正二十面体的置换群类似，只是要将顶点和面的角色对换．

这里给出的都是对顶点、棱、面等单独的对象作用的置换群的轮换指标．如果要对不同的对象同时染色，需要写出联合的轮换指标．

习题

染色问题

这些题目只需要分析置换群的结构，并应用 Pólya 计数原理．

• Luogu P4980【模板】Polya 定理
• Luogu P2561 [AHOI2002] 黑白瓷砖
• TRANSP - Transposing is Fun
• TRANSP2 - Transposing is Even More Fun
• Luogu P3307 [SDOI2013] 项链

当可以使用的颜色组合受到限制时，需要通过背包 DP 或者组合方法求解对轮换染色的方法数目．

• Luogu P1446 [HNOI2008] Cards
• UVA10601 Cubes
• Luogu P4916 [MtOI2018] 魔力环

图论计数

Pólya 计数原理可以用于 图论计数 问题，这类问题难点在于图的边置换群的枚举．

• SGU 282. Isomorphism
• Luogu P4727 [HNOI2009] 图的同构计数
• Luogu P4128 [SHOI2006] 有色图

另一类可以应用 Pólya 计数原理的图论计数问题需要直接操纵生成函数．

• LOJ 6538 烷基计数 加强版 加强版
• LOJ 6512「雅礼集训 2018」烷烃计数
• Luogu P6597 烯烃计数
• Luogu P5818 [JSOI2011] 同分异构体计数

参考文献与注释

• Pólya enumeration theorem - Wikipedia
• Notes on Pólya's Enumeration Theorem
• Cycle index - Wikipedia

Footnotes

1. 因此，空间对称群 $G$ 可以表示是集合 $X$ 上的置换群，即对称群 $S_X$ 的子群． ↩

2. 严格来说，是子群 $\langle g\rangle\le G$ 的作用． ↩