群论 学习笔记

置换群

一个群，满足：

• 封：封闭性

• 结：结合律

• 幺：幺元（单位元）

• 逆：逆元

• 交：交换律

---

Burnside 引理

$$|S/T|=\frac1{|T|}\sum_{P\in T}\sum_{a\in S}[P\circ a=a]$$

其中 $|S/T|$ 表示 $S$ 对 $T$ 的商群，即同构的重复元素只算一次。

---

Polya 引理（Pólya）

针对 $S$ 集合为一类固定格子个数 $n$、固定颜色个数 $m$、每个格子独立选择一种颜色填上的问题（$T$ 为任意置换群）。有：

$$|S/T|=\frac1{|T|}\sum_{P\in T}m^{c(P)}$$

其中 $c(P)$ 表示 $P$ 的环个数。

应用：大多数时候会按 $c(P)$ 分类。

---

容斥算 Burnside

下面 $\text{ans}(x)$ 表示 $n$ 个格子 $m$ 个颜色的所有染色方案中被 $m^n$ 算了 $x$ 次的方案数（循环同构算同一种方案）。

$$\text{ans}(x)=\frac{m^x-\sum_{d|x\land d\ne x}d\cdot\text{ans}(d)}x$$

扩展：

• 上面的 $m^x$ 可以在具体题目中被替换为任何一个可以用组合数学算出的式子。
• 反演一下就可以使得 $\text{ans}(x)=\sum_d ?\cdot m^d$ 之类的东西。某些题目中会优化复杂度。

---

立体几何的对偶

棱连接两个面也连接两个顶点，所以一个正多面体一定存在一个正多面体与之对偶。

常见的有：

• 正四面体 正四面体

• 正六面体 正八面体

• 正十二面体 正二十面体

  

  足球有 $12$ 个五边形，$20$ 个六边形。