对 Polya 计数定理的理解

DONG Yuxuan

用三种颜色给一串由 8 颗珠子构成的手链涂色,有几种不同的方案?手链可以任意旋转与翻转。

这类问题的实质是对于一个给定的集合,一个等价关系,求这个集合被分成了多少个等价类。

等价关系

对于集合 \(X\) ,其上的一个等价关系是指的满足如下定义的关系。

显然一个等价关系可以对集合中的元素做分类,把集合分为若干不相交的子集,且这些子集的并就是整个集合,也就是不遗漏也不重复,这样的分类叫做集合的一个划分,每个子集叫做一个等价类

变换群:等价关系的一种描述方法

如何描述一个具体的等价关系?容易想到我们可以用一组函数 \(G=\{f_1,f_2,...\}\) ,如果存在某个 \(f \in G\) 使得 \(b=f(a)\) ,那么就认为 \(a,b\) 等价。

并不是任何的 \(G\) 都能描述一个等价关系,而是需要一些条件。

要满足对称性,对于 \(f \in G\) 要求 \(f(a)=b\) 蕴含 存在 \(h \in G\) 使得 \(h(b)=a\) 。这就是说每个函数都是双射且它们的反函数也都在 \(G\) 中,这称为 \(G\) 的可逆性

要满足反自反性,我们只需要要求恒等函数 \(f(x)=x\) 在 \(G\) 中,我们把这个函数叫做 \(g\) 的单位元

要满足传递性,那么对于 \(a,b,c \in X\) ,如果有 \(f(a)=b,h(b)=c\) ,就一定要存在 \(p \in G\) 使得 \(p(a)=c=h(b)=h(f(a))\) ,也就是说,任意两个函数 \(f,h\) 的复合 \(f \cdot h\) 也要在 \(G\) 中,这叫 \(G\) 的封闭性

一个满足上述条件的函数集合,叫做 \(X\) 的一个变换群,本文里会简称为。群可以给出一个等价关系,把集合分为若干个等价类。

\(X\) 是一个集合, \(G\) 是 \(X\) 上的一个群,对于 \(x \in X\) ,称 \(O(x)=\{g(x) : g \in G\}\) 为 \(x\) 在 \(G\) 下的轨道,轨道里元素的个数称为轨道的长度。轨道是群论的术语,其实它就是 \(G\) 定义出的等价关系中 \(x\) 所属的等价类。

为什么叫轨道?我们把 \(X\) 中的元素看作点,如果有 \(g \in G\) 使得 \(g(x)=y\ \ (x,y \in X)\) ,那就在 \(x,y\) 之间连一条有向边,这就得到一个有向图。 \(x\) 所在的等价类就是 \(x\) 可以到达的所有点,所以叫 \(x\) 的轨道。

既然轨道就是等价类,那么显然集合会被分为若干根互不相交的轨道,且每个元素都会被某根轨道通过,形成一个划分。

用群论的术语重述等价类计数问题,就变成了:

给定集合 \(X\) 以及它的一个变换群 \(G\) ,求 \(X\) 在 \(G\) 下有几根轨道。全体轨道构成的集合称为 \(X\) 对 \(G\) 的商集,记作 \(X/G\) ,于是我们要求的就是 \(\vert X/G \vert\) 。

要回答这个问题,需要一些概念作为铺垫,主要涉及到:子群,陪集,指数,不动点,稳定子。

陪集与指数:用变换群对自身做分类

给定 \(X\) 的一个变换群 \(G\) ,其子集 \(H\) 叫做一个子群,如果其也满足变换群的条件的话。

取 \(G\) 中的元素 \(a\) ,以及一个子群 \(H\) ,定义 \(aH=\{a \cdot h:h \in H\}\) ,称作 \(H\) 的一个陪集

陪集可以看作子群作用在群自身形成的分类,只要我们用函数复合替换函数调用(程序语言里的运算符重载)就能看出这一点。 \(aH\) 就是 \(G\) 被 \(H\) 分类后 \(a\) 所在的轨道。那么显然 \(H\) 的所有陪集构成了 \(G\) 的一个划分。轨道的个数,也即是商集 \(G/H\) 的大小称为子群 \(H\) 的指数。与一般的划分不同,陪集形成的划分有一个独有的性质:每根轨道的长度都相同,也就是 \(H\) 的每个陪集都有相同的大小。这很好理解,因为显然每个陪集的大小都和子群 \(H\) 一样。这样我们就得到了所谓的拉格朗日定理

\[\vert G/H \vert = \vert G \vert / \vert H \vert\]

我们知道如果 \(f(x)=x\) 那么 \(x\) 叫做 \(f\) 的不动点。反过来,对于 \(x \in X\) , \(G\) 中所有以 \(x\) 为不动点的函数构成的集合叫做 \(x\) 的稳定子 \(S(x)=\{g:g(x)=x, g \in G\}\) 。 \(S(x)\) 一定是 \(G\) 的一个子群。首先,单位元必定在其中。其次,一个函数和它的反函数必然有相同的不动点。最后,如果两个函数有同一个不动点,它们的复合函数也会有这个不动点。

既然稳定子 \(S(x)\) 是子群,那么就可以用它的陪集对 \(G\) 做划分。对于 \(g \in G\) ,我们得到一个陪集 \(gS(x)=\{ g \cdot s: s(x)=x \}\) ,这个陪集里的每个函数,都把 \(x\) 映射到 \(g(x)\) 。也就是说,稳定子的陪集对 \(G\) 中函数按对 \(x\) 的象做了一个分类,同一类里的函数,都把 \(x\) 映射到同一个值。

轨道-稳定子定理

现在我们可以回答一些组合数学上的问题了,对于 \(x \in X\) , \(x\) 的轨道 \(O(x)\) 有多长?

轨道长度就是 \(O(x)=\{g(x):g \in G\}\) 这个集合的大小,由于集合中相同的元素会被排除掉,所以它取决于 \(G\) 中的函数会把 \(x\) 映射到多少个不同的值。这恰是 \(x\) 的稳定子的指数。

轨道-稳定子定理 某元素的轨道长度等于其稳定子的指数

\[\vert O(x) \vert = \vert G \vert / \vert S(x) \vert\]

Burnside 引理

现在可以回答如何计算轨道数的问题了。

Burnside 引理 轨道的个数等于群中各函数不动点个数的平均值

\[\vert X/G \vert =\frac{1}{ \vert G \vert }\sum_{g \in G} \vert X^g \vert\]

其中 \(X^g\) 是 \(g\) 的不动点集合。

我的水平有限,不能直观地解释这个结论,需要借助一点简单的代数变换。

我们尝试计算平均不动点数:

\[\frac{1}{ \vert G \vert }\sum_{g \in G}{ \vert X^g \vert }\]

注意到,计算 \(G\) 中各函数不动点个数的和,与计算 \(X\) 中各元素的稳定子大小的和,其结果是一样的。这很好理解,我们把 \(X\) 中的元素画作排成一列的点, \(G\) 中的函数画作另一列点,如果 \(x\) 是 \(g\) 的一个不动点,就在两个点之间连一条边。不管是不动点数之和,还是稳定子大小之和,都是去数图里有几条边,所以他们结果一样。于是有:

\[\begin{align} &\frac{1}{ \vert G \vert }\sum_{g \in G}{ \vert X^g \vert } \\ &= \frac{1}{ \vert G \vert }\sum_{x \in X}{ \vert S(x) \vert } \\ &= \frac{1}{ \vert G \vert }\sum_{x \in X}{ \vert G \vert / \vert O(x) \vert } \\ &= \sum_{x \in X}{\frac{1}{ \vert O(x) \vert }} \end{align}\]

注意到这里用了轨道-稳定子定理,得到的结论是平均不动点数等于各元素所在轨道的长度倒数和。

如何计算这个倒数和呢?因为 \(X\) 被分成了若干根轨道,所以我们可以计算每一根轨道上的元素的轨道长度倒数和,再加起来。而对于一根轨道而言,其上元素的轨道长度倒数和固定为1,所以所有元素的轨道长度倒数和恰为轨道的数量 \(\vert X/G \vert\) 。Burnside引理得证。

置换及其轮换分解

Burnside 引理已经在理论上解决了等价类计数问题,但是在实践上它用起来比较麻烦。拿最开始的珠子染色问题来说,我们要构造 \(X\) 和 \(G\) 。 \(G\) 还好,就是所有的旋转函数加一个翻转函数,加一个单位元。但 \(X\) 就麻烦了,因为要使用Burnside引理,我们需要把 \(X\) 构造为不考虑等价关系情况下的所有的着色方案,是一个大小为 \(3^8\) 的集合,随着数据规模的提高,这个集合会急速膨胀,而暴力计算一个函数的不动点要遍历一次整个集合,这在效率上是不可接受的。

Burnside引理描述的是计算所有等价类计数问题的抽象方法。Polya 定理是 Burnside 引理在着色这个具体问题下的应用。

理解 Polya 定理需要先了解置换和轮换分解的概念。

一个置换是对一组物品的重排列,例如

\[p = \left( \begin{matrix} 1 && 2 && 3 \\ 2 && 3 && 1 \\ \end{matrix} \right)\]

置换 \(p\) 把物体 \(1,2,3\) 重新排列为 \(2,3,1\) 。

我们可以把置换看作是排列的函数。因为置换不会有任何信息损失,所以它肯定是双射。置换和置换之间可以做复合运算,就像是普通的函数一样。

\[p = \left( \begin{matrix} 1 && 2 && 3 \\ 2 && 3 && 1 \\ \end{matrix} \right) \\\] \[q = \left( \begin{matrix} 1 && 2 && 3 \\ 2 && 1 && 3 \\ \end{matrix} \right) \\\] \[q \cdot p =\left( \begin{matrix} 1 && 2 && 3 \\ 1 && 3 && 2 \\ \end{matrix} \right) \\\]

某些特殊的置换叫做轮换,他们把一些元素依次挪动,而保持其他元素不变,例如:

\[p = \left( \begin{matrix} 1 && 2 && 3 && 4 && 5\\ 3 && 2 && 4 && 1 && 5 \\ \end{matrix} \right) \\\]

物品1,3,4被依次挪动,1变成3,3变成4,4变成1,剩下的物品2,5不变。

对于轮换我们只需要关注被挪动的元素,所以可以采用如下的简写法便能表达所有的信息。

\[p = \left( \begin{matrix} 1 && 3 && 4 \end{matrix} \right) \\\]

轮换分解定理 每一个置换都可以被分解为若干置换的复合。且如果不考虑置换的顺序,这种分解是唯一的。

轮换分解定理是显然成立的。我们只需要把物体看作图上的点,如果一个物体被置换映射到另一物体(或它自身),则增加一条指向被映射物体的点的有向边。由于置换是双射,这个图只能是由一个或多个互不相交的环组成,每个环就是一个轮换。

Polya 计数定理

考虑对 \(n\) 个物体用 \(m\) 中颜色着色,着色方案可以用 \((c_1, c_2, \ldots, c_n) : c_i \in [1, m]\) 来表示,所有这些着色方案组成集合 \(X\) 。我们用 \(X\) 上的一个群 \(G\) 来定义着色方案上的一个等价关系。 \(G\) 中的元素是置换,每个置换都会对着色方案做重排列。这对应于旋转,翻转等操作。

我们知道着色方案的等价类个数等于群中各置换不动点数的平均值,对于置换 \(g\) ,我们有计算不动点数 \(\vert X^g \vert\) 的快速方法。

我们对 \(g\) 做轮换分解,记其分解后的轮换数为 \(c(g)\) 。

Polya 定理 形式一

\[\vert X^g \vert =m^{c(g)}\]

这个还是比较好理解。对于一个着色方案,如果其在 \(g\) 的重排列下不变,那么轮换分解中每个轮换内的位置都必须是同一种颜色。而轮换之间互相独立,每个轮换又可以有 \(m\) 种可能的颜色,那么在 \(g\) 重排列下不变的着色方案必然有 \(m^{c(g)}\) 个。

Polya 定理 形式二

\[\vert X/G \vert =\frac{1}{ \vert G \vert }\sum_{g \in G}m^{c(g)}\]

这只是将形式一代入 Burnside 引理得到的直接推论而已。