Pólya 定理

Pólya 定理的中文名是波利亚计数定理。

传送门：洛谷P4980 【模板】Polya 定理题解（在这篇文章里会讲解 Pólya 定理的运用）

置换

一个有限集合 \(S\) 到自身的双射称为 \(S\) 的一个置换。集合 \(S=\{a_1,a_2,\cdots,a_n\}\) 上的置换可以表示为 \[ \varphi=\left(\begin{array}{c} a_1, a_2, \ldots, a_n \\ a_{p_1}, a_{p_2}, \ldots, a_{p_n} \end{array}\right) \] 意为将 \(a_i\) 映射为 \(a_{p_i}\) ，其中 \(p_1,p_2,\cdots,p_n\) 是 \(1,2,\cdots,n\) 是一个排列。显然 \(S\) 上置换的总数为 \(n!\) 。

对于两个置换 \(f = \left(\begin{array}{c}a_1, a_2, \ldots, a_n \\a_{p_1}, a_{p_2}, \ldots, a_{p_n}\end{array}\right)\) 和 \(g=\left(\begin{array}{c}a_{p_1}, a_{p_2}, \ldots, a_{p_n} \\a_{q_1}, a_{q_2}, \ldots, a_{q_n}\end{array}\right)\) ，\(f\) 和 \(g\) 的乘积记为 \(f \circ g\) ，其值为 \[ f \circ g=\left(\begin{array}{c} a_1, a_2, \ldots, a_n \\ a_{q_1}, a_{q_2}, \ldots, a_{q_n} \end{array}\right) \] 简单来说就是先经过 \(f\) 的映射，再经过 \(g\) 的映射。

这里也有人用 \(g\circ f\) 来表示同样含义的，~~不愧是数学~~。

置换群

集合 \(S\) 上的所有置换关于置换的乘法满足封闭性、结合律、有单位元、有逆元，因此构成一个群。

这个群的任意一个子群即称为置换群。

循环置换

循环置换是一类特殊的置换，可表示为 \[ \left(a_1, a_2, \ldots, a_m\right)=\left(\begin{array}{c} a_1, a_2, \ldots, a_{m-1}, a_m \\ a_2, a_3, \ldots, a_m, a_1 \end{array}\right) \] 若两个循环置换不含有相同的元素，则称它们是不相交的。有如下定理：

任意一个置换都可以分解为若干不相交的循环置换的乘积，例如 \[ \left(\begin{array}{l} a_1, a_2, a_3, a_4, a_5 \\ a_3, a_1, a_2, a_5, a_4 \end{array}\right)=\left(a_1, a_3, a_2\right) \circ\left(a_4, a_5\right) \] 该定理的证明也非常简单。如果把元素视为图的节点，映射关系视为有向边，则每个节点的入度和出度都为 \(1\)，因此形成的图形必定是若干个环的集合，而一个环即可用一个循环置换表示。

Burnside 引理

定义

设 \(A,B\) 为有限集合，\(X\) 为一些从 \(A\) 到 \(B\) 的映射组成的集合。

\(G\) 是 \(A\) 上的置换群，且 \(X\) 中的映射在 \(G\) 中的置换作用下封闭。

\(X / G\) 表示 \(G\) 作用在 \(X\) 上产生的所有等价类的集合¹，则 \[ |X / G|=\frac{1}{|G|} \sum_{g \in G}\left|X^g\right| \] 其中 \(X^g=\{x \mid x \in X,~g(x)=x\}\) 。

证明

在这之前先引入轨道稳定子定理以及它的证明。

轨道稳定子定理：\(G\) 和 \(X\) 的定义同上，有 \[ \forall x \in X,~ G^x=\{g \mid g(x)=x, g \in G\}, ~G(x)=\{g(x) \mid g \in G\} \] 其中 \(G^x\) 称为 \(x\) 的稳定子，\(G(x)\) 称为 \(x\) 的轨道，则有 \[ |G| = |G^x| \times |G(x)| \]

轨道稳定子定理的证明：

首先可以证明 \(G^x\) 是 \(G\) 的子群，因为

封闭性：若 \(f,g \in G\) ，则 \(f \circ g(x) = f(g(x)) = f(x) = x\) ，所以 \(f \circ g \in G^x\)

结合律：显然置换的乘法满足结合律。

单位元：因为 \(I(x)=x\) ，所以 \(I \in G^x\) （\(I\) 为恒等置换）

逆元：若 \(g \in G^x\) ，则 \(g^{-1}(x) = g^{-1}(g(x)) = g^{-1}\circ g(x) = I(x) = x\) ，所以 \(g^{-1} \in G^x\)

则由群论中的拉格朗日定理可得 \[ |G| = |G^x|[G:G^x] \] 其中 \([G:G^x]\) 为 \(G^x\) 不同的左陪集个数。

接着仅需证明 \(|G(x)| = [G : G^x]\) 。

我们将其转化为：证明存在一个从 \(G(x)\) 到 \(G^x\) 所有不同左陪集的双射。

令 \(\varphi(g(x)) = gG^x\) ，下证 \(\varphi\) 为双射

若 \(g(x) = f(x)\) ，两边同乘 \(f^{-1}\) 可得 \(f^{-1} \circ g(x)=I(x)=x\) ，所以 \(f^{-1} \circ g \in G^x\) ，由陪集的性质可得 \((f^{-1}\circ g)G^x = G^x\) ，即 \(gG^x = fG^x\)

反之可证，若 \(gG^x = fG^x\) ，则有 \(g(x) = f(x)\)

以上两点说明对于一个 \(g(x)\) ，只有一个左陪集与其对应，即 \(\varphi\) 是一个从 \(G(x)\) 到左陪集的映射

又显然 \(\varphi\) 有逆映射，因此 \(\varphi\) 是一个双射。

于是我们可以利用轨道稳定子定理来证明 Burnside 引理了 \[ \begin{aligned} \sum_{g \in G}\left|X^g\right| & =|\{(g, x) \mid(g, x) \in G \times X, g(x)=x\}| \\ & =\sum_{x \in X}\left|G^x\right| \\ & =\sum_{x \in X} \frac{|G|}{|G(x)|}\\ & =|G| \sum_{x \in X} \frac{1}{|G(x)|} \\ & =|G| \sum_{Y \in X / G} \sum_{x \in Y} \frac{1}{|G(x)|} \\ & =|G| \sum_{Y \in X / G} \sum_{x \in Y} \frac{1}{|Y|} \\ & =|G| \sum_{Y \in X / G} 1 \\ & =|G||X / G| \end{aligned} \] 即 \[ |X / G|=\frac{1}{|G|} \sum_{g \in G}\left|X^g\right| \]

解释

讲了半天这个定理到底有什么用呢？

我们以给立方体染色为例，来解释这个定理的用法。

\(A\) ：立方体 \(6\) 个面的集合。
\(B\) ：\(3\) 种颜色的集合。
\(X\) ：直接给每个面染色，不考虑本质不同的方案数的集合，共有 \(3^6\) 种
\(G\) ：各种翻转操作构成的置换群
\(X/G\) ：本质不同的染色方案的集合
\(X^g\) ：对于翻转操作 \(g\) ，所有直接染色方案中，经过 \(g\) 这种翻转后保持不变的染色方案的集合。

接着我们需要对 \(G\) 中的所有置换进行分析，它们可以分为以下几类：

不动：即恒等变换，显然有 \(|X^g| = 3^6\) 。
以两个相对面的中心连线为轴旋转 \(90^{\circ}\) ：相对面有 \(3\) 种选择，旋转的方向有 \(2\) 种选择，因此有 \(6\) 个置换。

假设选择了前后两个面的中心连线为轴，则必须要满足上下左右 \(4\) 个面的颜色一样，因此有 \(|X^g|=3^3\) 。
以两个相对面的中心连线为轴旋转 \(180^{\circ}\) ：相对面有 \(3\) 种选择，旋转无影响，因此有 \(3\) 个置换。

假设选择了前后两个面的中心连线为轴，则必须要满足上下相同，左右相同，因此有 \(|X^g| = 3^4\) 。
以两条相对棱的中点连线为轴旋转 \(180^{\circ}\) ：相对棱有 \(6\) 种选择，旋转无影响，因此有 \(6\) 个置换。

假设选择了前面与上面的交和下面与后面的交作为相对棱，

则必须要满足前、上两个面相同，下、后两个面相同，左右两个面相同，因此有 \(|X^g|=3^3\) 。
以两个相对顶点的连线为轴旋转 \(120^{\circ}\) ：相对顶点为 \(4\) 种选择，旋转的方向有 \(2\) 种选择，因此有 \(8\) 个置换。
假设选择了前面的右上角和后面的左下角为相对顶点，

则必须满足前、上、右相同且后、下、左相同，因此有 \(|X^g| = 3^2\) 。

因此，所有本质不同的方案数为 \[ \frac{1}{1+6+3+6+8}\left(3^6+6 \times 3^3+3 \times 3^4+6 \times 3^3+8 \times 3^2\right)=57 \]

Pólya 定理

定义

在与 Burnside 引理相同的前置条件下，若 \(X\) 为所有从 \(A\) 到 \(B\) 的映射，则 \[ |X / G|=\frac{1}{|G|} \sum_{g \in G}|B|^{c(g)} \] 其中 \(c(g)\) 表示置换 \(g\) 能拆分成的不相交的循环置换的数量。

证明

在 Burnside 引理中，显然 \(g(x)=x\) 的充要条件是 \(x\) 将 \(g\) 中每个循环置换的元素都映射到了 \(B\) 中的同一元素

所以 \(|X^g| = |B|^{c(g)}\) ，即可得 Pólya 定理。

解释

依然考虑立方体染色问题。

分析刚才提到的以相对棱的中点连线为轴旋转 \(180^{\circ}\) 的情况。

如果将前后上下左右 \(6\) 个面编号 \(1\) 到 \(6\) ，则该置换可以表示为 \[ \left(\begin{array}{l} 1,3,2,4,5,6 \\ 3,1,4,2,6,5 \end{array}\right)=(1,3) \circ(2,4) \circ(5,6) \] 因此 \(c(g)=3,|B|^{c(g)}=3^3\) ，与 Burnside 引理中的分析结果相同

参考文献：

[1] https://oi-wiki.org/math/permutation-group/