群论学习笔记
MCAdam
·
·
个人记录
置换群
设X是有限集，一般可以取X为前n个正整数组成的集合\{1,2,...,n\}。X的置换i_1,i_2,...,i_n可以看成是X到其自身的一对一函数，其定义为：
f:X\to X
一对一的函数f:X\to X是满射，用一个2\times n阵列表示
\binom{1\quad 2\quad ...\quad n}{i_1\quad i_2\quad ...\quad i_n}
把\{1,2,...,n\}的所有n!个置换构成的集合称为S_n
g\circ f=\binom{1\quad 2\quad ...\quad n}{j_1\quad j_2\quad ...\quad j_n}\circ \binom{1\quad 2\quad ...\quad n}{i_1\quad i_2\quad ...\quad i_n}=\binom{1\quad 2\quad ...\quad n}{j_{i_1}\quad j_{i_2}\quad ...j_{i_n}}
它们的合成按照先f后g的顺序合成：\displaystyle (g\circ f)(k)=g(f(k))=j_{i_k}
置换的合成满足结合律，但不满足交换律
置换与本身的合成可以写成幂的形式
恒等置换
\iota(k)=k
显然有
f\circ\iota=\iota\circ f=f
定义f^0=\iota
定义转置的逆f^{-1}满足：
\text{如果}f(s)=k\text{，那么}f^{-1}(k)=s
反映到阵列上就是交换上下两行，然后重新排序得到
如果S_n中的置换的非空子集G满足如下三条性质，则定义它为X的置换群
\text{(1)合成运算的封闭性：}\forall f,g\in G,\quad h=f\circ g\in G
\text{(2)单位元：}S_n$中的恒等置换$\iota\in G
\text{(3)逆元的封闭性：}\forall f\in G,\quad f^{-1}\in G
同时每个置换群满足消去律（两边同时乘上逆就可以了）：
f\circ g=f\circ h\to g=h
设\Omega是一个几何图形，\Omega到它自身的一个运动或者全等称为\Omega的一个对称。每个堆成可看作顶点、边及三位情况下的面的一个置换
对于一个正方形，它有8种置换：作用于角点上的旋转和作用于角点上的反射
\rho^0=\iota=\binom{1\quad 2\quad 3\quad 4}{1\quad 2\quad 3\quad 4}\quad \rho^1=\binom{1\quad 2\quad 3\quad 4}{2\quad 3\quad 4\quad 1}
\rho^2=\binom{1\quad 2\quad 3\quad 4}{3\quad 4\quad 1\quad 2}\quad \rho^3=\binom{1\quad 2\quad 3\quad 4}{4\quad 1\quad 2\quad 3}
\tau_1=\binom{1\quad 2\quad 3\quad 4}{1\quad 4\quad 3\quad 2}\quad \tau_2=\binom{1\quad 2\quad 3\quad 4}{3\quad 2\quad 1\quad 4}
\tau_3=\binom{1\quad 2\quad 3\quad 4}{2\quad 1\quad 4\quad3}\quad \tau_4=\binom{1\quad 2\quad 3\quad 4}{4\quad 3\quad 2\quad 1}
其中\rho^k表示把正方形旋转k\times \dfrac{2\pi }{4}，这四个旋转置换已经可以构成一个置换群了
# 着色
- 着色
$X$的一种着色是给$X$的每个元素指定一种颜色的分配方案
设$c$是$X$的一种着色，$1,2,...,n$的颜色分别记为$c(1),c(2),...,c(n)$，令$f$为$G$中的一个置换
$$f=\binom{1\quad 2\quad ...\quad n}{i_1\quad i_2\quad ...\quad i_n}$$
定义$f*c$为使得$i_k$具有$c(k)$的颜色，即：
$$(f*c)(i_k)=c(k)$$
还可以写成：
$$(f*c)(k)=c(f^{-1}(k))$$
着色集$C$需要具备这个性质：$\forall f\in G,\forall c\in C:f*c\in C
有以下基本关系成立：
(g\circ f)*c=g*(f*c)
左边就是把c(k)的颜色送到g(f(k))去
右边就是先把c(k)的颜色送到f(k)，再把f(k)的颜色送到g(f(k))
如果存在G中的置换f，使得：
f*c_1=c_2
则称c_1等价于c_2，可记作c_1\sim c_2
对于着色的等价，有如下几条性质：
\text{(1)自反性：}c\sim c
\text{(2)对称性：}c_1\sim c_2\iff c_2\sim c_1
\text{(3)传递性：}c_1\sim c_2,c_2\sim c_3\to c_1\sim c_3
Burnside定理
记使着色c保持不变的G中所有置换的集合：
G(c)=\{f:f\in G,f*c=c\}
记在f作用下使着色c保持不变的C中所有着色的集合：
C(f)=\{c:c\in C,f*c=c\}
我们把G(c)称作c的稳定核
定理：对于每一种着色c，c的稳定核G(c)是置换群，而且对于G中的任意置换f,g，f*c=g*c当且仅当f^{-1}\circ g\in G(c)
证明：
如果f和g都不会使得c改变，那么先f后g也不会使得c改变，合成运算满足封闭性
单位元使得所有着色不变，所以\iota \in G(c)
如果f使c不变，那么f^{-1}使c不变，逆元满足封闭性
不妨假设f*c=g*c
\displaystyle (f^{-1}\circ g)*c=f^{-1}*(g*c)=f^{-1}*(f*c)=(f^{-1}\circ f)*c=c
所以f^{-1}\circ g\in G(c)，通过类似的计算可证明必要性
定理：对于着色c，和c等价的着色数个数为：\dfrac{|G|}{|G(c)|}
证明：
考虑两个置换作用在c有同样的效果，即f*c=g*c
根据上面的定理可知：f^{-1}\circ g=h\in G(c)\iff g=f\circ h(h\in G(c))
所以对于每个置换f，一共有G(c)个置换作用在c上f有同样的效果
如果在c作用的每个置换的效果都不同（注意有恒等置换），那么和c等价的着色个数就是置换的个数
现在一种效果的置换有G(c)个，所以除掉就得到等价的着色个数
$$N(G,C)=\frac{1}{|G|}\sum_{f\in G}|C(f)|$$
证明：
考虑计数使$f*c=c$的对偶$(f,c)$的个数，显然可以得到：
$$\sum_{c\in C}|G(c)|=\sum_{f\in G}|C(f)|$$
由上面可知：$G(c)=\dfrac{|G|}{\text{与c等价的着色数}}
所以：\displaystyle \sum_{f\in G}|C(f)|=|G|\sum_{c\in C}\frac{1}{\text{与c等价的着色数}}
考虑等价的着色数整体，对求和式右边的分数贡献为1
所以\displaystyle \sum_{f\in G}|C(f)|=|G|\times N(G,C)，即Burnside定理
有了这个定理，计算非等价的着色数关键就是计算，每个置换会使多少个着色不变，较为一般的只需要基础的计数技巧就能得到
Polya公式
一个置换显然可以分解成若干个环的并，例如：
\binom{1\quad 2\quad 3\quad 4\quad 5\quad 6}{3\quad 5\quad 2\quad 4\quad 1\quad 6}=[1,3,2,5]\circ [4]\circ [6]
那么作用于着色上的置换，对每个环都是独立的，作用相当于把环上的颜色旋转一下
所以对于给定f，要计算|C(f)|，因为要求着色不变，那么一个环上的着色都应该是一样的
换句话说，设\#(f)表示f的循环分解后环的个数，并且着色用k种颜色构成
|C(f)|=k^{\#(f)}
如果对每种颜色并没有数量限制，那么这已经是非常简单的计算方法了
P4980 【模板】Pólya 定理
置换：旋转k\times\dfrac{2\pi}{n}(k\in [0,n-1]\cap\mathbb{Z})下
考虑旋转k下会形成多少个环，显然在这样的置换下每个环的大小都是相同发的。如果从1出发，要找到最小的t满足：
n|t\times k\to t=\dfrac{lcm(k,n)}{k}
那么形成的环的个数即：\dfrac{n}{t}=\dfrac{nk}{lcm(k,n)}=\gcd(k,n)
所以答案就是\displaystyle \frac{1}{n}\sum_{k=0}^{n-1}n^{\gcd(k,n)}，剩下随便搞搞就好了（为了方便可以使k的范围为[1,n]，反正都是一样的）