# 伯恩赛德引理与波利亚定理：从“数珠子”到“染色”的通俗大白话讲义

---

## 零、 为什么要学这个？（一个痛点引入）

想象一下，你手里有 **4颗珠子**（2红2蓝），你想用它们串成一个**手链**。
* 如果排成一排（直线），不同的排列有 $\frac{4!}{2!2!} = 6$ 种。
* 但是，**手链是可以拿起来旋转、甚至翻转的**！
  * 比如红红蓝蓝排成的一串，把手链转个圈，或者翻个面，可能就跟另一串完全一样了。

如果你用笨办法去画、去一个一个去重，很容易漏掉或者数错。**波利亚定理**（Pólya's Theorem）和它的基础**伯恩赛德引理**（Burnside's Lemma）就是数学家专门发明的“去重神器”。它能让你闭着眼睛，秒算所有**对称情况下本质不同的方案数**。

---

## 一、 最通俗的理解：伯恩赛德引理

别去背那些晦涩的群论定义，我们用一句话记住伯恩赛德引理的核心思想：

> **“本质不同的方案数” = 所有“对称动作”下，一动不动（保持原样）的方案总数 的 平均值。**

公式长这样：
$$\text{本质不同的方案数} = \frac{1}{\text{总动作数}} \sum \left( \text{每个动作下保持不变的方案数} \right)$$

### 💡 经典小例子：2颗珠子涂2种颜色
假设有 2 个位置（左右各一个），你可以涂**红（R）**或**蓝（B）**。如果不考虑手链能翻转，总共有 $2 \times 2 = 4$ 种涂法：
1. (红, 红)
2. (蓝, 蓝)
3. (红, 蓝)
4. (蓝, 红)

现在，我们把这两个位置做成一个**手链**，它能做透视翻转（左右对调）。我们来看看“对称动作”有哪些：
1. **什么都不做（恒等变换）**：
   * 动作：不动。
   * 刚才列出的 4 种涂法，全都可以保持原样。
   * **保持不变的方案数 = 4**
2. **左右翻转（180度对调）**：
   * 动作：左边和右边互换位置。
   * 哪些涂法翻转后跟原来一模一样？只有 (红, 红) 和 (蓝, 蓝)。(红, 蓝) 翻转后会变成 (蓝, 红)，变了。
   * **保持不变的方案数 = 2**

根据伯恩赛德引理，套入公式：
$$\text{本质不同的手链数} = \frac{1}{2} \times (4 + 2) = 3$$
这 3 种本质不同的手链分别是：
1. 全红：(红, 红)
2. 全蓝：(蓝, 蓝)
3. 一红一蓝：(红, 蓝) 和 (蓝, 红) 本质上是一样的，算 1 种。

---

## 二、 波利亚定理：进阶的“数圈圈”法

伯恩赛德引理好是好，但如果要算“每个动作下保持不变的方案数”，当格子很多、颜色很多时，依然很头疼。

**波利亚**站出来说：别数方案了，我们去**数循环（圈圈）**！

### 核心公式
$$\text{方案数} = \frac{1}{\text{总动作数}} \sum \left( \text{颜色数}^{\text{该动作的循环节数 } c(g)} \right)$$

* **什么是循环节数 $c(g)$？**
  当你做一个旋转或翻转动作时，那些位置会互相串门？几个位置串成一个闭环，这个闭环就叫一个“循环”。**这个动作一共有几个闭环，循环节数就是几。**

---

## 三、 超经典例子：正方形 4 个顶点染 2 种颜色

### 【题目】
有一个正方形的 4 个顶点，每个顶点可以染**红色**或**蓝色**（$m=2$）。如果通过**旋转**可以重合的算同一种方案，一共有多少种不同的着色方案？

---

### 【手把手拆解步骤】

正方形绕中心旋转，总共有 **4 种旋转动作**（总动作数 $|G| = 4$）：
1. **旋转 $0^\circ$（不动）**
2. **旋转 $90^\circ$**
3. **旋转 $180^\circ$**
4. **旋转 $270^\circ$**

我们分别来看看这 4 个动作的**循环节数（$c(g)$）**是多少：

#### 1. 旋转 $0^\circ$（不动）：
* 4 个顶点谁也不动，各自在一个小圈里：$(1)(2)(3)(4)$
* 一共有 **4 个循环**。
* 贡献的方案数：$2^4 = 16$

#### 2. 旋转 $90^\circ$：
* 顶点 1 跑到 2，2 跑到 3，3 跑到 4，4 跑到 1。
* 它们四个串成了一个大圈：$(1 \to 2 \to 3 \to 4 \to 1)$
* 一共只有 **1 个大循环**。
* 贡献的方案数：$2^1 = 2$
  *(想一想：要让这个动作旋转后颜色不变，必须 4 个顶点颜色完全一样，即全红或全蓝，正好 $2^1=2$ 种)*

#### 3. 旋转 $180^\circ$：
* 顶点 1 跑到 3（3跑回1），顶点 2 跑到 4（4跑回2）。
* 形成了两个对角线互换的小圈：$(1\ 3)(2\ 4)$
* 一共有 **2 个循环**。
* 贡献的方案数：$2^2 = 4$

#### 4. 旋转 $270^\circ$：
* 跟旋转 $90^\circ$ 类似，4 个顶点也是串成一个大圈：$(1 \to 4 \to 3 \to 2 \to 1)$
* 一共只有 **1 个大循环**。
* 贡献的方案数：$2^1 = 2$

---

### 【最后结算】
把这 4 种动作贡献的数字加起来，除以总动作数 4：
$$\text{本质不同的正方形着色数} = \frac{1}{4} \times (16 + 2 + 4 + 2) = \frac{24}{4} = 6$$

所以，答案是 **6 种**。你看，用波利亚定理，我们完全不需要去画图穷举，只需要数清楚每个旋转动作把几个点连成了“闭环”即可！

伯恩赛德引理与波利亚定理：从“数珠子”到“染色”的通俗大白话讲义

零、为什么要学这个？（一个痛点引入）

想象一下，你手里有 4颗珠子（2红2蓝），你想用它们串成一个手链。 * 如果排成一排（直线），不同的排列有 $\frac{4!}{2!2!} = 6$ 种。 * 但是，手链是可以拿起来旋转、甚至翻转的！ * 比如红红蓝蓝排成的一串，把手链转个圈，或者翻个面，可能就跟另一串完全一样了。

如果你用笨办法去画、去一个一个去重，很容易漏掉或者数错。波利亚定理（Pólya's Theorem）和它的基础伯恩赛德引理（Burnside's Lemma）就是数学家专门发明的“去重神器”。它能让你闭着眼睛，秒算所有对称情况下本质不同的方案数。

一、最通俗的理解：伯恩赛德引理

别去背那些晦涩的群论定义，我们用一句话记住伯恩赛德引理的核心思想：

“本质不同的方案数” = 所有“对称动作”下，一动不动（保持原样）的方案总数的平均值。

公式长这样： $$\text{本质不同的方案数} = \frac{1}{\text{总动作数}} \sum \left( \text{每个动作下保持不变的方案数} \right)$$

💡 经典小例子：2颗珠子涂2种颜色

假设有 2 个位置（左右各一个），你可以涂红（R）或蓝（B）。如果不考虑手链能翻转，总共有 $2 \times 2 = 4$ 种涂法： 1. (红, 红) 2. (蓝, 蓝) 3. (红, 蓝) 4. (蓝, 红)

现在，我们把这两个位置做成一个手链，它能做透视翻转（左右对调）。我们来看看“对称动作”有哪些： 1. 什么都不做（恒等变换）： * 动作：不动。 * 刚才列出的 4 种涂法，全都可以保持原样。 * 保持不变的方案数 = 4 2. 左右翻转（180度对调）： * 动作：左边和右边互换位置。 * 哪些涂法翻转后跟原来一模一样？只有 (红, 红) 和 (蓝, 蓝)。(红, 蓝) 翻转后会变成 (蓝, 红)，变了。 * 保持不变的方案数 = 2

根据伯恩赛德引理，套入公式： $$\text{本质不同的手链数} = \frac{1}{2} \times (4 + 2) = 3$$ 这 3 种本质不同的手链分别是： 1. 全红：(红, 红) 2. 全蓝：(蓝, 蓝) 3. 一红一蓝：(红, 蓝) 和 (蓝, 红) 本质上是一样的，算 1 种。

二、波利亚定理：进阶的“数圈圈”法

伯恩赛德引理好是好，但如果要算“每个动作下保持不变的方案数”，当格子很多、颜色很多时，依然很头疼。

波利亚站出来说：别数方案了，我们去数循环（圈圈）！

核心公式

$$\text{方案数} = \frac{1}{\text{总动作数}} \sum \left( \text{颜色数}^{\text{该动作的循环节数 } c(g)} \right)$$

什么是循环节数 $c(g)$？ 当你做一个旋转或翻转动作时，那些位置会互相串门？几个位置串成一个闭环，这个闭环就叫一个“循环”。这个动作一共有几个闭环，循环节数就是几。

三、超经典例子：正方形 4 个顶点染 2 种颜色

【题目】

有一个正方形的 4 个顶点，每个顶点可以染红色或蓝色（$m=2$）。如果通过旋转可以重合的算同一种方案，一共有多少种不同的着色方案？

【手把手拆解步骤】

正方形绕中心旋转，总共有 4 种旋转动作（总动作数 $|G| = 4$）： 1. 旋转 $0^\circ$（不动） 2. 旋转 $90^\circ$ 3. 旋转 $180^\circ$ 4. 旋转 $270^\circ$

我们分别来看看这 4 个动作的循环节数（$c(g)$）是多少：

1. 旋转 $0^\circ$（不动）：

4 个顶点谁也不动，各自在一个小圈里：$(1)(2)(3)(4)$
一共有 4 个循环。
贡献的方案数：$2^4 = 16$

2. 旋转 $90^\circ$：

顶点 1 跑到 2，2 跑到 3，3 跑到 4，4 跑到 1。
它们四个串成了一个大圈：$(1 \to 2 \to 3 \to 4 \to 1)$
一共只有 1 个大循环。
贡献的方案数：$2^1 = 2$ (想一想：要让这个动作旋转后颜色不变，必须 4 个顶点颜色完全一样，即全红或全蓝，正好 $2^1=2$ 种)

3. 旋转 $180^\circ$：

顶点 1 跑到 3（3跑回1），顶点 2 跑到 4（4跑回2）。
形成了两个对角线互换的小圈：$(1\ 3)(2\ 4)$
一共有 2 个循环。
贡献的方案数：$2^2 = 4$

4. 旋转 $270^\circ$：

跟旋转 $90^\circ$ 类似，4 个顶点也是串成一个大圈：$(1 \to 4 \to 3 \to 2 \to 1)$
一共只有 1 个大循环。
贡献的方案数：$2^1 = 2$

【最后结算】

把这 4 种动作贡献的数字加起来，除以总动作数 4： $$\text{本质不同的正方形着色数} = \frac{1}{4} \times (16 + 2 + 4 + 2) = \frac{24}{4} = 6$$

所以，答案是 6 种。你看，用波利亚定理，我们完全不需要去画图穷举，只需要数清楚每个旋转动作把几个点连成了“闭环”即可！

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com