Định lý đếm 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\)．

Phân tích

Gọi các đỉnh theo chiều ngược kim đồng hồ là \(\{0,1,\cdots,n-1\}\), thì \(r^k(i)=i+k\bmod n\). Tập đỉnh trong cùng vòng của \(i\):

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

Rõ ràng \(i\equiv i+\ell k\pmod n\) khi và chỉ khi

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

Vậy độ dài vòng là \(\dfrac{n}{\gcd(k,n)}\), nên \(r^k\) có \(\gcd(k,n)\) vòng. Gộp các hạng giống nhau, với mỗi \(d\mid n\), số \(k\) sao cho \(\gcd(k,n)=n/d\) là \(\varphi(d)\), cho đơn thức \(t_d^{n/d}\), suy ra công thức.

Nhóm dihedral

Với đa giác đều \(n\) cạnh, tập các phép quay và phản xạ tạo nhóm dihedral \(D_{2n}\). Gọi \(r\) là quay \((360/n)^\circ\), và \(s\) là phản xạ qua trục đối xứng nào đó, thì

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

\(r^k\) là quay, \(sr^k\) là phản xạ qua một trục khác. Có \(1\) phép đồng nhất, \((n-1)\) phép quay và \(n\) phép phản xạ. Tác động lên đỉnh và cạnh có biểu diễn giống nhau. Chỉ số vòng:

\[ 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} \]

Phân tích

Phần quay giống \(C_n\), cần phân tích phản xạ theo chẵn/lẻ.

Nếu \(n=2k+1\): các trục phản xạ nối một đỉnh với trung điểm cạnh đối diện, có \(n\) trục. Mỗi phản xạ giữ nguyên đỉnh trên trục, các đỉnh còn lại đổi cặp, nên có \(1\) vòng độ dài 1 và \(k\) vòng độ dài 2.

Nếu \(n=2k\): có hai loại trục. Một nửa đi qua hai đỉnh đối diện, giữ nguyên hai đỉnh trên trục, còn lại đổi cặp, nên có \(2\) vòng độ dài 1 và \((k-1)\) vòng độ dài 2. Nửa còn lại đi qua trung điểm hai cạnh đối diện, tất cả đỉnh đổi cặp, nên có \(k\) vòng độ dài 2.

Suy ra công thức.

Nhóm đối xứng

Với \(n\) phần tử, tập mọi hoán vị tạo nhóm đối xứng \(S_n\). Nó mô tả toàn bộ đối xứng có thể của \(n\) đỉnh, cũng là biểu diễn hoán vị trên tập đỉnh.

Theo hoán vị và sắp xếp, chỉ số vòng:

\[ 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!}. \]

Số hoán vị kiểu \(1^{\alpha_1}2^{\alpha_2}\cdots n^{\alpha_n}\) là

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

Thỏa truy hồi:

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

với \(Z(S_0)=1\). Ý nghĩa: xây hoán vị độ dài \(n\) bằng cách chọn độ dài vòng chứa điểm \(n\) là \(k\), còn lại \((n-k)\) điểm.

Với đồ thị đầy đủ \(n\) đỉnh, nhóm đối xứng là \(S_n\); tác động lên đỉnh có chỉ số vòng trên. Nhưng tác động lên cạnh khác (số cạnh \(n(n-1)/2\)), cần phân tích riêng. Dưới đây là ví dụ.

Đếm đồ thị vô hướng đơn

Đếm số đồ thị vô hướng đơn không đẳng cấu với 4 đỉnh.

Giải

Đây là bài tô 2 màu cạnh của đồ thị đầy đủ 4 đỉnh. Nhóm đối xứng là \(S_4\), xét nhóm hoán vị trên tập cạnh \(S_4^{(2)}\):

Đồng nhất (1 cách): giữ nguyên các cạnh, đơn thức \(t_1^6\);
Đổi chỗ hai đỉnh (6 cách): giả sử đổi \(a,b\), thì hai cạnh giữ nguyên, hai cặp cạnh đổi chỗ, đơn thức \(6t_1^2t_2^2\);
Chu trình 3 đỉnh (8 cách): nếu \((abc)\) thì các cạnh tương ứng tạo hai chu trình 3, đơn thức \(8t_3^2\);
Đổi hai cặp đỉnh (3 cách): được \(3t_1^2t_2^2\);
Chu trình 4 đỉnh (6 cách): đơn thức \(6t_2t_4\).

Do đó chỉ số vòng:

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

Số đồ thị không đẳng cấu:

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

Nhóm đa diện

Nhóm đa diện là nhóm đối xứng của các đa diện đều. Có 5 đa diện đều: tứ diện, lập phương, bát diện, thập nhị diện, nhị thập diện. Đổi chỗ đỉnh và mặt (giữ quan hệ kề) được đa diện đối ngẫu: tứ diện tự đối ngẫu, lập phương đối ngẫu bát diện, thập nhị diện đối ngẫu nhị thập diện. Dùng đối ngẫu để đơn giản hóa phân tích.

Chỉ xét các phép quay trong không gian 3D, có 3 nhóm:

Nhóm tứ diện (tetrahedral group), đối xứng của tứ diện đều:
- Đồng nhất;
- Quay \(120^\circ\) và \(240^\circ\) quanh trục nối đỉnh với tâm mặt đối diện;
- Quay \(180^\circ\) quanh trục nối trung điểm hai cạnh đối.
Tổng \(1+2\times4+1\times3=12\) phép.

Chỉ số vòng:
- Nhóm hoán vị đỉnh và mặt: \(\dfrac1{12}\left(t_1^4+8t_1t_3+3t_2^2\right)\);
- Nhóm hoán vị cạnh: \(\dfrac1{12}\left(t_1^6+8t_3^2+3t_1^2t_2^2\right)\).
Nhóm bát diện (octahedral group), đối xứng của lập phương (và bát diện):
- Đồng nhất;
- Quay \(120^\circ\) và \(240^\circ\) quanh trục nối hai đỉnh đối;
- Quay \(180^\circ\) quanh trục nối trung điểm hai cạnh đối;
- Quay \(90^\circ\),\(180^\circ\),\(270^\circ\) quanh trục nối tâm hai mặt đối.
Tổng \(1+2\times 4+1\times 6+3\times 3=24\) phép.

Chỉ số vòng cho lập phương:
- Đỉnh: \(\dfrac{1}{24}\left(t_1^8+8t_1^2t_3^2+9t_2^4+6t_4^2\right)\);
- Cạnh: \(\dfrac{1}{24}\left(t_1^{12}+8t_3^4+6t_1^2t_2^5+6t_4^3+3t_2^6\right)\);
- Mặt: \(\dfrac{1}{24}\left(t_1^6+8t_3^2+6t_2^3+6t_1^2t_4+3t_1^2t_2^2\right)\).
Với bát diện, đổi vai trò đỉnh và mặt.
Nhóm nhị thập diện (icosahedral group), đối xứng của thập nhị diện (và nhị thập diện):
- Đồng nhất;
- Quay \(120^\circ\) và \(240^\circ\) quanh trục nối hai đỉnh đối;
- Quay \(180^\circ\) quanh trục nối trung điểm hai cạnh đối;
- Quay \(72^\circ\),\(144^\circ\),\(216^\circ\),\(288^\circ\) quanh trục nối tâm hai mặt đối.
Tổng \(1+2\times 10+1\times 15+6\times 4=60\) phép.

Chỉ số vòng cho thập nhị diện:
- Đỉnh: \(\dfrac{1}{60}\left(t_1^{20}+20t_1^2t_3^6+15t_2^{10}+24t_5^4\right)\);
- Cạnh: \(\dfrac{1}{60}\left(t_1^{30}+20t_3^{10}+15t_1^2t_2^{14}+24t_5^6\right)\);
- Mặt: \(\dfrac{1}{60}\left(t_1^{12}+20t_3^4+15t_2^6+24t_1^2t_5^2\right)\).
Với nhị thập diện, đổi vai trò đỉnh và mặt.

Các chỉ số vòng trên chỉ xét tác động lên từng loại đối tượng riêng. Nếu tô đồng thời nhiều loại đối tượng, cần chỉ số vòng liên hợp.

Bài tập

Bài toán tô màu

Các bài này chỉ cần phân tích nhóm hoán vị và áp dụng Pólya.

Khi tổ hợp màu bị ràng buộc, cần dùng DP balo hoặc tổ hợp để đếm cách tô theo vòng.

Đếm đồ thị

Pólya có thể dùng cho đếm đồ thị, khó ở việc liệt kê nhóm hoán vị trên cạnh.

Một nhóm khác cần thao tác trực tiếp trên hàm sinh.

Tài liệu tham khảo và chú thích

Do đó nhóm đối xứng không gian \(G\) có thể biểu diễn như nhóm hoán vị trên tập \(X\), tức là một nhóm con của nhóm đối xứng \(S_X\). ↩
Nghiêm ngặt mà nói, là tác động của nhóm con \(\langle g\rangle\le G\). ↩

Last updated on this page:, Update history
Found an error? Want to help improve? Edit this page on GitHub!
Contributors to this page:Wajov, Early0v0, Enter-tainer, Great-designer, iamtwz, Ir1d, MegaOwIer, mgt, StudyingFather, Tiphereth-A, warzone-oier, Xeonacid, c-forrest
All content on this page is provided under the terms of the CC BY-SA 4.0 and SATA license, additional terms may apply