学习笔记：从 0 到 Pólya 原理

· · 算法·理论

前言

军训的时候见缝插针读完了符文杰老师的《Pólya 原理及其应用》和陈瑜希老师的《Pólya 计数法的应用》，遂作此文。

本文将会是 Self-contained（自包含）的，将会从一些群论的基本概念开始写起，直到 Pólya 原理，并通过一些有关的例题讲解 Pólya 原理在 OI 题目的应用。

由于笔者自身能力的限制，本文可能存在一些纰漏和错误的地方，同时例题的难度可能也不会很大。希望您能谅解，如果发现问题欢迎各位大佬指出。

感谢审核老师的认真审核。

引言

Pólya 计数定理（Pólya Enumeration Theorem）是组合数学中计算染色问题“本质不同”的方案数的一个非常高效简便的工具，由匈牙利裔美国数学家、数学教育家 George Pólya(1887-1985) 在 1937 年提出。

理解 Pólya 计数定理需要一些群论的知识，下面将会从群的定义开始介绍。

从 0 到 Pólya 原理

群

群（Group）是数学中的一种代数结构，由一个集合 G 和一种运算 \times 组成，满足以下性质：

  1. 封闭性：对于 G 中的任意元素 a, b，a \times b \in G；
  2. 结合律：对于 G 中的任意元素 a, b, c，(a \times b) \times c = a \times (b \times c)；
  3. 单位元：存在一个元素 e \in G，使得对于 G 中的任意元素 a，e \times a = a \times e = a；
  4. 逆元：对于 G 中的任意元素 a，存在一个元素 a^{-1} \in G，使得 a \times a^{-1} = a^{-1} \times a = e。

如果一个集合 G 和一种运算 \times 满足上述性质，那么我们称 G 在运算 \times 下是一个群。

和字符串一样，我们使用 |G| 来表示一个群 G 的大小。

置换和置换群

置换（Permutation）是集合的一种操作，记作 \sigma，表示将集合 X 中的元素重新排列，记作 \sigma(X)。

例如，对于集合 X = \{1, 2, 3\}，置换 \sigma 可以表示为 \sigma(1) = 2, \sigma(2) = 3, \sigma(3) = 1。

置换可以写作类似矩阵的形式：

\begin{pmatrix} 1 & 2 & 3 & \cdots & n\\ \sigma(1) & \sigma(2) & \sigma(3) & \cdots & \sigma(n)\\ \end{pmatrix}.

置换群（Permutation Group）是若干置换在复合运算下构成的群，其基本运算为置换的复合，例如：

\begin{pmatrix} 1 & 2 & 3 & \cdots & n\\ a_1 & a_2 & a_3 & \cdots & a_n\\ \end{pmatrix} \begin{pmatrix} 1 & 2 & 3 & \cdots & n\\ b_1 & b_2 & b_3 & \cdots & b_n\\ \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 & \cdots & n\\ a_{b_1} & a_{b_2} & a_{b_3} & \cdots & a_{b_n}\\ \end{pmatrix}.

轨道稳定子定理

在正式介绍 Burnside 引理之前，我们需要先理解群在集合上的作用，以及与之密切相关的两个核心概念：轨道（Orbit）和稳定子（Stabilizer）。

群作用

设 G 是一个群，X 是一个非空集合。如果存在一个映射

G \times X \to X,\quad (g, x) \mapsto g \cdot x

满足以下两条性质：

  1. 恒等作用：对任意 x \in X，e \cdot x = x，其中 e 是群 G 的单位元；
  2. 相容性：对任意 g_1, g_2 \in G 和任意 x \in X，(g_1 g_2) \cdot x = g_1 \cdot (g_2 \cdot x)，

则称群 G 作用在集合 X 上。

在 Pólya 计数的语境中，X 通常代表所有染色方案的集合，而 G 是作用于这些方案上的置换群（例如旋转、翻转等）。群作用描述的就是：给定一个置换，它能将一种染色方案变成另一种“看起来不同但实际等价”的方案。

轨道

设群 G 作用于集合 X。对于 X 中的一个元素 x，定义

\operatorname{Orb}(x) = \{\, g \cdot x \mid g \in G \,\}.

这个集合称为 x 的轨道。它包含了 x 在群 G 的所有置换作用下能到达的所有元素。

直观理解：如果两种染色方案处于同一个轨道中，那么它们可以通过某个群操作互相转化，因此它们是“本质相同”的。所以，我们想要计数的“本质不同”的方案数，实际上就是轨道的个数。

稳定子

对于 x \in X，定义

\operatorname{Stab}(x) = \{\, g \in G \mid g \cdot x = x \,\}.

这个集合称为 x 的稳定子群（简称稳定子）。它由所有不改变 x 的群元素组成。

不难验证，\operatorname{Stab}(x) 确实是 G 的一个子群（封闭性、结合律、单位元、逆元都自然满足）。

轨道稳定子定理

定理（Orbit-Stabilizer Theorem）：设有限群 G 作用于有限集合 X，则对于任意 x \in X，有

|\operatorname{Orb}(x)| \cdot |\operatorname{Stab}(x)| = |G|.

这个定理告诉我们：轨道的大小乘以稳定子的大小，恰好等于整个群的大小。

证明：

固定一个元素 x \in X。考虑从群 G 到轨道 \operatorname{Orb}(x) 的映射

\varphi: G \to \operatorname{Orb}(x),\quad g \mapsto g \cdot x.

由轨道的定义，这个映射显然是满射。我们想知道有多少个不同的群元素映射到轨道中的同一个元素。

取轨道中的任意一个元素 y \in \operatorname{Orb}(x)，设 y = g_0 \cdot x（g_0 \in G）。

我们发现

g \cdot x = g_0 \cdot x \iff (g_0^{-1} g) \cdot x = x \iff g_0^{-1} g \in \operatorname{Stab}(x) \iff g \in g_0 \operatorname{Stab}(x).

那么所有满足 g \cdot x = y 的群元素 g 恰好是左陪集 g_0 \operatorname{Stab}(x)。

而一个左陪集的大小正好等于 |\operatorname{Stab}(x)|。因此，在映射 \varphi 下，轨道中的每一个元素都恰好有 |\operatorname{Stab}(x)| 个原像。

于是

|G| = |\operatorname{Orb}(x)| \cdot |\operatorname{Stab}(x)|,

故得证。

Burnside 引理

定义 D(a_i) 表示在置换 a_i 下不动点的数量，那么有 Burnside 引理：

设有限群 G=\{a_1,a_2,\dots,a_s\} 作用于有限集合 X，令 L 为 X 在 G 作用下的轨道（等价类）个数，则

L = \frac{1}{|G|} \sum_{i=1}^{s} D(a_i),

其中 D(a_i) = |\{x \in X \mid a_i \cdot x = x\}|。

证明：
考虑集合

S = \{(a, x) \in G \times X \mid a \cdot x = x\}.

一方面，按群元素 a 统计，对于每个 a_i，满足条件的 x 的个数正是 D(a_i)，因此

|S| = \sum_{i=1}^{s} D(a_i).

另一方面，按元素 x 统计，对于每个 x，满足条件的 a 的个数正是其稳定子 \operatorname{Stab}(x) 的大小。由轨道稳定子定理，|\operatorname{Stab}(x)| = \frac{|G|}{|\operatorname{Orb}(x)|}，于是

|S| = \sum_{x \in X} |\operatorname{Stab}(x)| = \sum_{x \in X} \frac{|G|}{|\operatorname{Orb}(x)|}.

将 X 按轨道划分，设轨道为 O_1, O_2, \dots, O_L，同一轨道中的元素具有相同的轨道大小，则

\sum_{x \in X} \frac{|G|}{|\operatorname{Orb}(x)|} = \sum_{j=1}^{L} \sum_{x \in O_j} \frac{|G|}{|O_j|} = \sum_{j=1}^{L} |O_j| \cdot \frac{|G|}{|O_j|} = L \cdot |G|.

综上可得

\sum_{i=1}^{s} D(a_i) = L \cdot |G|,

即

L = \frac{1}{|G|} \sum_{i=1}^{s} D(a_i).

证毕。

循环和 Pólya 原理

我们发现 Burnside 引理中 D(a_i) 的值不是很好计算，因此我们希望找到一个更方便计算的方法。

那么这就需要进一步介绍 Pólya 原理了，在此之前，我认为还需要介绍循环的概念。

记

(a_1 a_2 \dots a_n) = \begin{pmatrix} a_1 & a_2 & a_3 & \cdots & a_n\\ a_2 & a_3 & a_4 & \cdots & a_1\\ \end{pmatrix}.

读者一定可以看出这个置换的循环性质，如上述的置换我们称之为一个 n 阶循环。

我们称两个循环 a,b 不相交，当且仅当对于任意 i,j 都有 a_i\ne b_j。

任何一个置换都是若干个不相交的循环的积，例如

\begin{pmatrix} 1 & 2 & 3 & 4 & 5\\ 3 & 5 & 1 & 4 & 2\\ \end{pmatrix} = (1\ 3)(2\ 5)(4).

我们称这个置换的循环节数为 3。

记 c(g_i) 为置换 g_i 的循环节数，涂色数（下文会介绍）为 m，那么因为在一个置换 g_i 的循环分解中，同一个循环内的所有位置在 g_i 的作用下彼此到达，若染色方案要成为 g_i 的不动点，则该循环内的所有位置必须染同一种颜色；不同循环之间互不影响，因此总方案数为 m^{c(g_i)}。

所以有：

m^{c(g_i)} = D(g_i).

那么我们就可以将 D(g_i) 转化为 m^{c(g_i)} 来计算了，即有

\sum_{i=1}^{s} D(g_i) = \sum_{i=1}^{s} m^{c(g_i)}. L = \frac{1}{|G|} \sum_{i=1}^{s} m^{c(g_i)}.

这就是 Pólya 原理。

一个例子

这里引用符文杰老师在《Pólya 原理及其应用》使用的例子来帮助理解 Pólya 原理：

给定一个 2\times 2 的方阵，用黑白两色涂色，问有多少种本质不同的涂色方案。定义本质不同为不能通过旋转使得两个方案相同。

:::align{center}

符文杰老师在《Pólya 原理及其应用》的附图

通过枚举我们可以知道有且只有上图 16 种情况，其中C3、C4、C5、C6 是本质相同的；C7、C8、C9、C10是本质相同的；C11、C12 是本质相同的；C13、C14、C15、C16 也是是本质相同的。故共有 6 种本质不同的方案。

通过 Burnside 引理求解

通过观察我们可以发现本例中共有 4 种置换，分别是（顺时针）旋转 0^{\circ},90^{\circ},180^{\circ},270^{\circ}，我们分别使用 g_1,g_2,g_3,g_4 来表示这四种置换，观察可得在 g_1 下，16 种方案均不发生改变，即 D(g_1)=16。同理有 D(g_2)=2,D(g_3)=4,D(g_4)=2。套用 Burnside 引理，有

L = \frac{1}{|G|}\sum_{i=1}^{s} D(g_i) = \frac{1}{4}\times(16 + 2 + 4 + 2) = 6.

通过 Pólya 原理求解

我们将 2\times 2 的方阵的左上记为 1，右上为 2，左下为 3，右下为 4，则 4 种置换 g_1,g_2,g_3,g_4 分别可以表示为：

g_1= \begin{pmatrix} 1 & 2 & 3 & 4\\ 1 & 2 & 3 & 4\\ \end{pmatrix} =(1)(2)(3)(4), g_2= \begin{pmatrix} 1 & 2 & 3 & 4\\ 2 & 4 & 1 & 3\\ \end{pmatrix} =(1\ 2\ 4\ 3), g_3= \begin{pmatrix} 1 & 2 & 3 & 4\\ 4 & 3 & 2 & 1\\ \end{pmatrix} =(1\ 4)(2\ 3), g_4= \begin{pmatrix} 1 & 2 & 3 & 4\\ 3 & 1 & 4 & 2\\ \end{pmatrix} =(1\ 3\ 4\ 2).

由此可得各置换的循环节数为 c(g_1)=4，c(g_2)=1，c(g_3)=2，c(g_4)=1。涂色数 m=2，代入 Pólya 公式：

L=\frac{1}{|G|}\sum_{i=1}^{s} m^{c(g_i)} =\frac{1}{4}\left(2^4+2^1+2^2+2^1\right) =\frac{1}{4}(16+2+4+2)=6.

希望这个例子能帮助读者更好地理解 Burnside 引理和 Pólya 原理。

Pólya 原理在 OI 中的应用（一些例题）

正如作者在前言中所说，受限于作者的能力限制，本节选取的题目难度可能较小，笔者希望通过一些比较经典的题目帮助读者来更好的理解 Pólya 原理，选取的例题考察的主要是 Pólya 原理的基本应用，而不涉及更高难度的优化，在此笔者表示歉意。

在 OI 竞赛中，单独考察 Burnside 引理和 Pólya 原理的题目较少，一般要进行一些优化，希望读者可以通过下文获得一些启发。

{\color{#9D3DCF} \text{P2561}} [AHOI2002] 黑白瓷砖

题意：求一个由 \frac{n(n+1)}{2} 个正三角形组成的二面体群（即群 D_3）的 2 色等价类数量。n\le 20。

分析：

之所以将本题放在模板前面是因为笔者认为本题没有任何转换，难度要小于模板。

我们记瓷砖数为 T=\frac{n(n+1)}{2}。

由题可知本题共包含 6 个变换，分别是恒等变换，120^{\circ},240^{\circ} 旋转和三个反转，我们分别计算循环节数：

带入 Pólya 公式即可，答案为

ans = \frac{1}{6} \times (2^T + 2 \times 2^{c_1} + 3 \times 2^{c_2})=\frac{2^T + 2 \times 2^{c_1} + 3 \times 2^{c_2}}{6}.

实现：注意到本题的 n 达到了 20，因而 2^T 会较大，需要写高精度，值得庆幸的是，本题只需要用到简单的，不加优化高精度乘法，而非高精度快速幂和 FFT。

这里笔者选择了使用 Python 实现，因而忽略了高精度乘法的实现，因为笔者认为高精度运算与本文关系不大，因此不在此赘述。

n = int(input())
T = n * (n + 1) // 2
if T % 3 == 0:
    c1 = T // 3
else:
    c1 = (T + 2) // 3
F = (n + 1) // 2
c2 = (T + F) // 2
ans = ((1 << T) + 2 * (1 << c1) + 3 * (1 << c2)) // 6
print(ans)
#其实就是笔者太懒了，还找理由。
#强烈谴责！

{\color{#9D3DCF} \text{P4980}} 【模板】Pólya 定理

题意：给定一个 n 个点，n 条边的环，有 n 种颜色，给每个顶点染色，问有多少种本质不同的染色方案，答案对 10^9+7 取模。若两个染色方案可以通过旋转相互得到，则认为它们本质相同。n \leq 10^9,t \leq 10^3。

分析：

本题的置换群为 n 阶循环群 C_n，共包含 n 个置换，分别为旋转 0,1,\dots,n-1 个位置。对于旋转 k 个位置（0 \leq k < n），其循环节数为 \gcd(n,k)（读者可自行验证：该置换的循环分解中每个循环的长度均为 \frac{n}{\gcd(n,k)}，故循环节数为 \gcd(n,k)）。

由 Pólya 定理，本质不同的染色方案数为

L = \frac{1}{n} \sum_{k=0}^{n-1} n^{\gcd(n,k)}.

直接枚举 k 显然不可行。注意到 \gcd(n,k) 的取值只能是 n 的因子，我们按因子 d = \gcd(n,k) 分类统计。若 d \mid n，则满足 \gcd(n,k) = d 的 k 的个数为 \varphi\!\left(\frac{n}{d}\right)（因为令 k = d \cdot t，则 \gcd\!\left(\frac{n}{d}, t\right) = 1，t 在 \left[1, \frac{n}{d}\right] 中与 \frac{n}{d} 互质）。于是

L = \frac{1}{n} \sum_{d \mid n} n^d \cdot \varphi\!\left(\frac{n}{d}\right).

令 m = \frac{n}{d}，等价地有

L = \frac{1}{n} \sum_{m \mid n} n^{\frac{n}{m}} \cdot \varphi(m).

我们知道当 n \leq 10^9 时，n 的因子个数不超过约 1344，我们可以通过质因数分解 n，枚举其所有因子 m，计算 \varphi(m) 和 n^{\frac{n}{m}}，累加后乘以 n 在模 10^9+7 下的逆元即可。

实现：

#include<bits/stdc++.h>
#define P 1000000007
using namespace std;
typedef long long LL;
//十年OI一场空，不开long long见祖宗
LL qp(LL a , LL b){
    LL res = 1;
    while(b){
        if(b & 1)
            res = res * a % P;
        a = a * a % P;
        b >>= 1;
    }
    return res;
}
LL n , sum;
int T , cnt;
LL p[64] , e[64];
inline void fac(LL n){
    LL x = n;
    cnt = 0;
    for(LL p_ = 2 ; p_ * p_ <= x ; ++p_){
        if(x % p_ == 0){
            int e_ = 0;
            while(x % p_ == 0)
                x /= p_ , e_ += 1;
            p[++cnt] = p_,
            e[cnt] = e_;
        }
    }
    if(x > 1)
        p[++cnt] = x , e[cnt] = 1;
}
inline void dfs(int idx , LL d , LL phi){
    if(idx == cnt + 1){
        sum = (sum + (phi % P) * qp(n , n / d) % P) % P;
        return;
    }
    LL p_ = p[idx];
    int e_ = e[idx];
    dfs(idx + 1 , d , phi);
    LL d_ = 1; //p ^ i
    LL phi_ = 1;
    for(int i = 1 ; i <= e_ ; ++i){
        d_ *= p_;
        if(i == 1)
            phi_ *= (p_ - 1);
        else
            phi_ *= p_;
        dfs(idx + 1 , d * d_ , phi * phi_);
    }
}
int main(){
    //freopen(".in" , "r" , stdin);
    //freopen(".out" , "w" , stdout);
    scanf("%d" , &T);
    while(T--){
        scanf("%lld" , &n);
        fac(n);
        sum = 0;
        dfs(1 , 1 , 1);
        LL ans = sum % P * qp(n % P , P - 2) % P;
        printf("%lld\n" , ans);
    }
    return 0;
}

//我常常追忆过去
//我该在哪停留，我问我自己。

{\color{#0E1D69} \text{P4128}} [SHOI2006] 有色图

题意：给定 n 个顶点的无向完全图 K_n，每条边染 m 种颜色之一，求两两不同构的有色图数量，答案对质数 p 取模。n \leq 53，m \leq 1000，n < p \leq 10^9。

分析：

本题的置换群为所有 n 个顶点的置换构成的对称群 S_n，其大小为 n!，直接枚举显然不可行。我们需要按照置换的循环结构进行分类统计。

设一个顶点置换 \sigma 的循环分解包含长度为 l_1,l_2,\dots,l_k 的循环，满足 \sum_{i=1}^{k} l_i=n。我们需要计算 \sigma 作用在边集上的循环节数 c(\sigma)，从而得到不动点染色方案数为 m^{c(\sigma)}。

这里与前面的题目有一点不同：本题染色的对象是边，而 \sigma 最初作用在的是顶点，因此我们需要考虑 \sigma 在边集上诱导出的置换。

我们发现对于一个长度为 l 的顶点循环，其内部共有 \binom{l}{2} 条边。考虑其中一条边 (u,v)，在 \sigma 的作用下，它的两个端点会同时向前移动一步，因此两个端点在这个循环上的距离保持不变。

设两个端点之间较小的环上距离为 d，显然有 1\le d\le\left\lfloor\frac l2\right\rfloor。对于固定的 d，所有距离为 d 的边会在 \sigma 的作用下互相转换，并且最终回到原来的边，因此它们恰好构成一个边循环。

因此，一个长度为 l 的顶点循环内部的边会形成 \left\lfloor\frac l2\right\rfloor 个边循环。

同理，对于两个长度分别为 a 和 b 的不同顶点循环，连接它们之间共有 ab 条边。设其中一条边为 (u,v)，其中 u 属于长度为 a 的循环，v 属于长度为 b 的循环。

经过 t 次 \sigma 后，这条边回到原来的位置，当且仅当两个端点同时回到原来的位置，即 a \mid t 且 b\mid t。

因此最小的 t 为 \operatorname{lcm}(a,b)。也就是说，每一个边循环中恰好有 \operatorname{lcm}(a,b) 条边。

于是这 ab 条边一共形成

\frac{ab}{\operatorname{lcm}(a,b)} =\gcd(a,b)

个边循环。

因此，对于循环长度序列 l_1,\dots,l_k，对应的边循环节数为

c(\sigma) = \sum_{i=1}^{k}\left\lfloor\frac{l_i}{2}\right\rfloor + \sum_{1\le i<j\le k}\gcd(l_i,l_j).

设长度为 i 的循环有 cnt_i 个，满足该循环结构的置换个数为

\frac{n!}{\prod_{i=1}^{n} i^{cnt_i}\cdot cnt_i!}.

于是，本质不同的染色方案数为

L= \sum_{\sum i\cdot cnt_i=n} \frac{m^{c(\sigma)}} {\prod_{i=1}^{n} i^{cnt_i}\cdot cnt_i!}.

式中 \sum i\cdot cnt_i=n 表示遍历 n 的所有整数分拆（partition）。

对于分母的处理，我们注意到题目保证 p>n 且 p 是质数，所以有 p 和所有的 i 互质，使用费马小定理计算逆元即可。

实现：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
//十年OI一场空，不开long long见祖宗
LL qp(LL a , LL b , LL mod){
    LL res = 1;
    while(b){
        if(b & 1)
            res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
int n;
LL m , p;
LL ans;
int a[60] , gcd_[60][60];
LL inv[60] , fac[60];
inline void dfs(int x , int x_ , LL cnt , LL inv_){
    if(x_ == 0){
        ans = (ans + qp(m , cnt , p) * inv_) % p;
        return;
    }
    if(x == n + 1)
        return;
    int k = x_ / x;
    for(int i = 0 ; i <= k ; ++i){
        a[x] = i;
        LL cnt_ = cnt;
        if(i > 0){
            cnt_ = cnt_ + i * (x / 2) + 1LL * i * (i - 1) / 2 * x;
            for(int j = 1 ; j < x ; ++j)
                cnt_ += 1LL * a[j] * i * gcd_[j][x];
        }
        LL _inv_ = inv_;
        if(i > 0){
            _inv_ = _inv_ * qp(inv[x] , i , p) % p;
            _inv_ = _inv_ * fac[i] % p;
        }
        dfs(x + 1 , x_ - i * x , cnt_ , _inv_);
    }
}
int main(){
    //freopen(".in" , "r" , stdin);
    //freopen(".out" , "w" , stdout);
    scanf("%d%lld%lld" , &n , &m , &p);
    m %= p;
    for(int i = 1 ; i <= n ; ++i)
        inv[i] = qp(i , p - 2 , p);
    LL tmp[60];
    tmp[0] = 1;
    for(int i = 1 ; i <= n ; ++i)
        tmp[i] = tmp[i - 1] * i % p;
    fac[n] = qp(tmp[n] , p - 2 , p);
    for(int i = n ; i >= 1 ; --i)
        fac[i - 1] = fac[i] * i % p;
    for(int i = 1 ; i <= n ; ++i)
        for(int j = 1 ; j <= n ; ++j)
            gcd_[i][j] = __gcd(i , j);
    ans = 0;
    dfs(1 , n , 0 , 1);
    printf("%lld\n" , ans);
    return 0;
}
//星图铺就的，未必是归途。
//但有人循着它，便不算迷路。

//所以色图在哪里。

总结

本文从群论的一些基本概念出发，介绍了 Pólya 定理和其在 OI 比赛中的简单应用，受笔者个人能力所限，本文的例题难度有限，希望读者谅解。读者也可以自行寻找更多例题进行练习，多思考 Pólya 定理的本质和相关优化，相信读者会有自己更多的感悟和理解。

最后，由衷地感谢您的阅读。

参考文献

[1] Pólya 定理

[2] 符文杰《Pólya 原理及其应用》

[3] 陈瑜希《Pólya 计数法的应用》

AI 使用说明：本文部分章节曾使用 DeepSeek 进行润色和检查，保证笔者贡献严格大于 AI。