从小学开始的数数

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) 二元运算的置换的集合 , 并满足群的四个性质:

1. \text{封闭性:\ }\forall a\in G,b\in G,a\cdot b\in G
2. \text{结合律:\ }\left( a\cdot b \right) \cdot c=a\cdot \left( b\cdot c \right)
3. \text{幺元}\left( \text{单位元} \right) :\ \exists e\in G,\ \text{s.t}.\forall a\in G,\ e\cdot a=a\cdot e=a
4. \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 –