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 –
毒瘤吧:- (,看到从小学开始我才点进来的/kel