引言
群论（Group Theory）是现代数学的基石之一，也是组合计数中解决”在等价关系下计数”问题的利器。当我们需要计算在旋转、翻转等对称操作下本质不同的方案数时，直接枚举往往会因对称性而导致大量重复计数。Burnside引理和Pólya计数定理正是解决这类问题的经典工具。本文将用Java实现置换群的基本操作与Burnside引理，以项链染色问题为例，展示群论在算法竞赛与工程实践中的应用。
群与置换群的基本概念
群是一个集合 G 配上一个二元运算 ·，满足四个性质：
1. 封闭性：∀a,b∈G, a·b ∈ G
2. 结合律：(a·b)·c = a·(b·c)
3. 单位元：∃e∈G, ∀a∈G, e·a = a·e = a
4. 逆元：∀a∈G, ∃a⁻¹∈G, a·a⁻¹ = e
置换群是由一组置换（即双射函数）构成的群。在组合计数中，置换通常表示为对称操作（如旋转、翻转）。一个 n 元置换可表示为：
σ = ( 1 2 3 ... n )
( σ(1) σ(2) σ(3) ... σ(n) )
Burnside引理
Burnside引理是计算在群作用下不同轨道（等价类）数量的核心定理：
轨道数 = (1/|G|) · Σ_{g∈G} |Fix(g)|
其中：
– G 是作用在集合 X 上的置换群
– |G| 是群的阶（元素个数）
– Fix(g) 是在置换 g 作用下保持不变的元素的集合
– |Fix(g)| 是被 g 固定的元素个数
直观理解：把所有置换的”不动点”数求平均，就得到了不等价的方案数。
Pólya计数定理
Pólya定理是Burnside引理在染色问题上的具体化。设用 m 种颜色对 n 个位置染色，置换 g 可分解为 c(g) 个不相交的轮换。则：
|Fix(g)| = m^{c(g)}
即每个轮换内的位置必须染同色，才能在该置换下保持不变。最终：
不等价染色方案数 = (1/|G|) · Σ_{g∈G} m^{c(g)}
经典问题：项链染色计数
问题描述：用 m 种颜色给 n 颗珠子的项链染色，考虑旋转等价（圆排列），求不等价的染色方案数。
置换群分析：旋转群 G = {旋转0格, 旋转1格, ..., 旋转(n-1)格}，共 n 个元素。
对于旋转 k 格，置换可分解为 gcd(n, k) 个长度为 n/gcd(n,k) 的轮换。
因此 c(旋转k格) = gcd(n, k)，代入Pólya定理：
ans = (1/n) · Σ_{k=0}^{n-1} m^{gcd(n,k)}
Java实现
以下实现包含置换表示、轮换分解、Burnside引理与Pólya定理的完整求解：
import java.util.*;
/**
* 群论基础：置换群、Burnside引理与Pólya计数定理
* 以项链染色问题为例
*/
public class GroupTheory {
// ============ 置换类 ============
static class Permutation {
int[] p; // p[i] 表示位置i映射到p[i]
int n;
Permutation(int[] p) {
this.p = p.clone();
this.n = p.length;
}
// 单位置换
static Permutation identity(int n) {
int[] id = new int[n];
for (int i = 0; i < n; i++) id[i] = i;
return new Permutation(id);
}
// 旋转移置：循环左移k位
static Permutation rotation(int n, int k) {
int[] r = new int[n];
for (int i = 0; i < n; i++) {
r[i] = (i + k) % n;
}
return new Permutation(r);
}
// 翻转移置：以轴axis翻转 (axis=0为垂直轴)
static Permutation reflection(int n, int axis) {
int[] ref = new int[n];
for (int i = 0; i < n; i++) {
ref[i] = (2 * axis - i + n) % n;
}
return new Permutation(ref);
}
// 复合置换：先应用other，再应用this
Permutation compose(Permutation other) {
int[] result = new int[n];
for (int i = 0; i < n; i++) {
result[i] = this.p[other.p[i]];
}
return new Permutation(result);
}
// 分解为不相交轮换，返回轮换个数
int countCycles() {
boolean[] visited = new boolean[n];
int cycles = 0;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
cycles++;
int cur = i;
while (!visited[cur]) {
visited[cur] = true;
cur = p[cur];
}
}
}
return cycles;
}
// 打印轮换分解
List<List<Integer>> getCycles() {
boolean[] visited = new boolean[n];
List<List<Integer>> cycles = new ArrayList<>();
for (int i = 0; i < n; i++) {
if (!visited[i]) {
List<Integer> cycle = new ArrayList<>();
int cur = i;
while (!visited[cur]) {
visited[cur] = true;
cycle.add(cur);
cur = p[cur];
}
cycles.add(cycle);
}
}
return cycles;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder("(");
for (int i = 0; i < n; i++) {
sb.append(i).append("->").append(p[i]);
if (i < n - 1) sb.append(", ");
}
return sb.append(")").toString();
}
}
// ============ 快速幂 ============
static long modPow(long base, long exp, long mod) {
long result = 1 % mod;
base %= mod;
while (exp > 0) {
if ((exp & 1) == 1) result = (result * base) % mod;
base = (base * base) % mod;
exp >>= 1;
}
return result;
}
// ============ GCD ============
static int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
// ============ Burnside引理求解器 ============
static class BurnsideSolver {
/**
* Pólya计数定理：项链染色（仅考虑旋转）
* n: 珠子数, m: 颜色数
*/
static long necklaceRotationOnly(int n, int m, long mod) {
long sum = 0;
for (int k = 0; k < n; k++) {
int cycles = gcd(n, k); // 旋转k格的轮换数 = gcd(n,k)
sum = (sum + modPow(m, cycles, mod)) % mod;
}
// 除以n：使用n的模逆元（若mod为质数且n与mod互质）
// 这里直接做整数除法，因为Burnside引理保证结果是整数
return sum / n;
}
/**
* 完整二面体群（旋转+翻转）的项链染色
* 二面体群D_n有2n个元素：n个旋转 + n个翻转
*/
static long necklaceDihedral(int n, int m, long mod) {
long sum = 0;
// n个旋转
for (int k = 0; k < n; k++) {
Permutation rot = Permutation.rotation(n, k);
sum = (sum + modPow(m, rot.countCycles(), mod)) % mod;
}
// n个翻转
for (int axis = 0; axis < n; axis++) {
Permutation ref = Permutation.reflection(n, axis);
sum = (sum + modPow(m, ref.countCycles(), mod)) % mod;
}
return sum / (2L * n);
}
/**
* 通用Burnside引理：给定置换群，计算不等价染色数
*/
static long genericBurnside(List<Permutation> group, int m, long mod) {
long sum = 0;
for (Permutation g : group) {
sum = (sum + modPow(m, g.countCycles(), mod)) % mod;
}
// 结果必为整数，但模意义下需用逆元
return sum / group.size(); // 实际应用中若不能整除需用模逆元
}
}
// ============ 生成二面体群 D_n ============
static List<Permutation> generateDihedralGroup(int n) {
List<Permutation> group = new ArrayList<>();
// 旋转
for (int k = 0; k < n; k++) {
group.add(Permutation.rotation(n, k));
}
// 翻转
for (int axis = 0; axis < n; axis++) {
group.add(Permutation.reflection(n, axis));
}
return group;
}
// ============ 验证与演示 ============
public static void main(String[] args) {
System.out.println("=== 群论：置换群与Burnside引理演示 ===\n");
// 示例1：置换的轮换分解
System.out.println("--- 置换与轮换分解 ---");
Permutation rot3 = Permutation.rotation(6, 2);
System.out.println("旋转2格 (n=6): " + rot3);
System.out.println("轮换分解: " + rot3.getCycles());
System.out.println("轮换数: " + rot3.countCycles());
Permutation ref0 = Permutation.reflection(6, 0);
System.out.println("\n垂直翻转 (n=6): " + ref0);
System.out.println("轮换分解: " + ref0.getCycles());
System.out.println("轮换数: " + ref0.countCycles());
// 示例2：项链染色（仅旋转）
System.out.println("\n--- 项链染色计数（仅旋转等价） ---");
int[] testN = {3, 4, 5, 6};
int[] testM = {2, 3, 2, 3};
long MOD = 1_000_000_007L;
for (int i = 0; i < testN.length; i++) {
int n = testN[i], m = testM[i];
long ans = BurnsideSolver.necklaceRotationOnly(n, m, MOD);
System.out.printf("n=%d, m=%d -> 不等价方案数 = %d%n", n, m, ans);
}
// 示例3：项链染色（旋转+翻转）
System.out.println("\n--- 项链染色计数（旋转+翻转等价） ---");
for (int i = 0; i < testN.length; i++) {
int n = testN[i], m = testM[i];
long ans = BurnsideSolver.necklaceDihedral(n, m, MOD);
System.out.printf("n=%d, m=%d -> 不等价方案数 = %d%n", n, m, ans);
}
// 示例4：生成完整二面体群并验证
System.out.println("\n--- 二面体群 D_4 ---");
List<Permutation> d4 = generateDihedralGroup(4);
System.out.println("群阶 |D_4| = " + d4.size());
for (Permutation g : d4) {
System.out.printf(" %s -> 轮换数=%d%n", g, g.countCycles());
}
// 示例5：验证Burnside引理（3色染4珠项链）
System.out.println("\n--- 验证：3色染4珠项链 ---");
long ansRot = BurnsideSolver.necklaceRotationOnly(4, 3, MOD);
long ansDih = BurnsideSolver.necklaceDihedral(4, 3, MOD);
System.out.printf("仅旋转等价: %d%n", ansRot);
System.out.printf("旋转+翻转等价: %d%n", ansDih);
}
}
关键设计要点解析
置换的复合运算：置换 σ 和 τ 的复合 στ 表示”先执行 τ，再执行 σ“。代码中通过 result[i] = this.p[other.p[i]] 实现。注意置换群的乘法一般不满足交换律。
轮换分解算法：从每个未访问的位置出发，沿着置换的映射关系追踪，直到回到起点，形成一个轮换。该算法时间复杂度为 O(n)，因为每个位置恰好被访问一次。
Burnside引理的整数性：定理保证最终结果 (1/|G|) · Σ|Fix(g)| 必为整数。但在模意义下计算时，需要计算 |G| 的模逆元。当模数为质数且与 |G| 互质时，可用费马小定理求逆元。
复杂度分析
- 轮换分解：
O(n)，每个位置访问一次 - Pólya定理（项链旋转）：
O(n log m)，需计算n次快速幂 - Pólya定理（二面体群）：
O(n · (n + log m))，共2n个置换，每个置换分解O(n) - 空间复杂度：
O(n)，存储置换数组
扩展方向
- 着色多项式：图着色问题中，Pólya定理可推广为计算图的自同构群作用下的不等价着色数。
- Burnside引理在数据结构中的应用：在计算循环同构字符串的不同个数时，Burnside引理提供
O(n)解法，优于O(n²)的朴素比较。 - 抽象代数视角：当置换群进一步推广到矩阵群、线性变换群时，Burnside引理可应用于编码理论中不等价码字的计数。
