从小学开始的数数

Introduction

设 $\sigma$ 是一个从集合 $\mathbb{A}=\{ 1,2,\cdots,n \}$ 到自身的一一映射 , 那么可以称 $\sigma$ 为置换 , 形如

$\sigma =\left( \begin{matrix} 1& 2& 3& \cdots& n \\ a_1& a_2& a_3& \cdots& a_n \end{matrix} \right)$

（其中 $\{a_i\}$ 是一个排列）

P.S. 置换可以做乘法，比如 $\left( \begin{array}{c} a \\ b \end{array} \right) \cdot \left( \begin{array}{c} b \\ c \end{array} \right) =\left( \begin{array}{c} a \\ c \end{array} \right)$

置换+群论

置换群 ?

置换群 $(G,\cdot)$ (我就直接记作 $G$ 了…) 是一个置换的群. 也即一个带有 (其实严格说叫做装备 equip) 二元运算的置换的集合 , 并满足群的四个性质:

$\text{封闭性:\ }\forall a\in G,b\in G,a\cdot b\in G$
$\text{结合律:\ }\left( a\cdot b \right) \cdot c=a\cdot \left( b\cdot c \right)$
$\text{幺元}\left( \text{单位元} \right) :\ \exists e\in G,\ \text{s.t}.\forall a\in G,\ e\cdot a=a\cdot e=a$
$\text{逆元:\ }\forall a\in G,\ \exists b\in G,\ \text{s.t.\ }a\cdot b=b\cdot a=e$

（所有的群存在唯一逆元和唯一幺元 , 具体的证明在一个叫做 “OI实用群论” 的文里）

染色问题与等价

定义在一个群上 , $x$ 为对集合 $\mathbb{A}$ 元素的着色方案 , $\mathbb{C}$ 为所有着色方案的集合 ;

定义如果 $\exists g_i \in G$ 使得 $g_i \cdot x = y$ , 称作 $x,y$ 等价.

Burnside Lemma

要解决的问题就是在给定置换群 $G$ 和着色方案集合 $\mathbb{C}$ 的情况下, 求出有多少种本质不同的着色方案 (也就是两两不等价).

定义 $\mathbb{C}(f)$ 为在置换 $g_i \in G$ 的作用下不变的染色方案的集合. 集合中的元素(这里的元素是染色方案)又称该置换下的不动点.

$N(G,\mathbb{A})= \frac{1}{|G|}\sum_{ g \in G } |\mathbb{C}(g)|$

(等价类数目为各集合不动点数目的均值)

Pólya Theorem

设 $G$ 为对 $n$ 个对象的置换群 , 每个对象可以用 $m$ 种颜色染色 , 等价类数目是 :

$N(G,\mathbb{C}) = \frac{1}{|G|} \sum_{ i = 1 }^{|G|} m^{c(g_i)}$

其中 $c(g_i)$ 为 $g_i \in G$ 的轮换 (循环节) 的个数 .

(说到轮换 , 突然想到曾经写过一个挺好玩的文)

这就意味着如果染色 $x \in \mathbb{C}$ 在 $g_i \in G$ 的作用下不变 , 那么每个轮换中的元素必须染同种颜色 .

Important conclusions

第一个结论是循环移位的。

通过（循环）移位形成的置换，假设一个 $n$ 个对象的置换，循环移位 $k$ 位，轮换数为 $\gcd(n,k)$ 。

第二个结论是图上置换群的。

对于 $n$ 个点的无向有色完全图，点的置换有 $n$ 个元素，对于每一个大小设为 $a$ 的轮换，这个轮换对应的完全子图的边的轮换有 $\frac{a}{2}$ 个，对于两个大小为 $a,b$ 的轮换， $a$ 和 $b$ 之间的边所形成的置换，它的轮换有 $\gcd(a,b)$ 个。

证明的话我们先证后面那条，考虑一条边的颜色 $c(x,y)$ 其中 $x$ 和 $y$ 属于不同的轮换 ( 轮换大小分别为 $n,m$ ) ，考虑边的轮换都要同色，这样我们保证的是 $\forall k , c(x,y) = c(x+k \mathrm{ mod } n , y+k \mathrm { mod } m)$ 。

那么每个点其实都一样了。用类似结论 [1] 的证法可以发现是 $\gcd(n,m)$ 。

而且你会发现因为一共 $ab$ 条边，所以说每个循环节大小是 $\mathrm{lcm}(n,m)$ 的。

然后前面那条是类似的。。（不负责任）

前面那条的话，一个不好理解的证法是枚举一个点，发现这个点所在的对称轴把轮换这个环分成两半了。然后对于对称的一半，这些点与 $1$ 的边会转会来，然后只需要考虑一半的点就好了-0-

– END –