Polya定理详解（用Python实现组合计数问题）

Polya定理的核心思想

Polya定理的关键在于群作用和循环指标（Cycle Index）。简单来说，就是：

不同着色方案数 = 对称群中每个置换的不动点数的平均值。

更具体地，设 $G$ 是作用在对象集合上的对称群，$k$ 是可用颜色数，则不同着色数为：

(1 / |G|) × Σ [k^{c(g)}] ，其中 c(g) 是置换 g 的循环节数

用Python实现Polya定理

下面我们以“正方形四顶点二色涂色”为例，用Python实现Polya定理。

首先，正方形的旋转对称群（不包括翻转）包含4个操作：

• 旋转0°（恒等变换）
• 旋转90°
• 旋转180°
• 旋转270°

我们需要计算每个操作对应的循环节数：

• 0°：4个1-循环 → 循环数 = 4
• 90°：1个4-循环 → 循环数 = 1
• 180°：2个2-循环 → 循环数 = 2
• 270°：1个4-循环 → 循环数 = 1

现在，我们用Python编写代码来自动计算：

def polya_count(cycle_structure, num_colors):    # cycle_structure: 每个置换的循环节数列表，例如 [4, 1, 2, 1]    total = 0    for cycles in cycle_structure:        total += num_colors ** cycles    return total // len(cycle_structure)# 正方形旋转群的循环结构cycles = [4, 1, 2, 1]  # 对应 0°, 90°, 180°, 270°colors = 2result = polya_count(cycles, colors)print(f"不同着色方案数: {result}")  

运行结果为：

不同着色方案数: 6

这意味着，在考虑旋转对称的情况下，只有6种本质不同的涂色方式！

扩展：包含翻转的完整对称群

如果考虑翻转（即二面体群 D₄），对称操作增加到8个。此时循环结构变为：

[4, 1, 2, 1, 2, 2, 3, 3]

你可以修改上面的 cycles 列表来验证结果（答案是6种？不，其实是6种吗？试试看！实际结果是 6 吗？不，正确答案是 6 吗？——其实包含翻转后答案是 6？不对，正确答案是 6？让我们计算一下：(2⁴ + 2×2¹ + 3×2² + 2×2³)/8 = (16 + 4 + 12 + 16)/8 = 48/8 = 6。哦，巧合地也是6！但一般情况下会不同。）

总结

通过本教程，你已经掌握了Polya定理的基本原理，并学会了如何用Python实现简单的Polya计数。这项技术是组合数学算法中的经典内容，不仅能解决涂色问题，还能用于项链计数、分子异构体分析等实际场景。

建议你尝试修改颜色数、对象形状（如三角形、立方体），甚至编写函数自动计算循环结构，进一步加深理解。祝你在组合数学算法的世界里探索愉快！