群论

等价类

对于集合$X$，它的一个关系是集合$X\times X$的一个子集$R$，如果对于$x,y\in X$有$(x,y)\in R$，则称$x,y$有关系$R$，记作$xRy$。
设关系$R$是集合$X$上的一个等价关系，对于$x\in X$，令$x_R=\{y\in X|xRy\}$，则称$x_R$为代表元为$x$的一个$R$等价类，所有$R$等价类构成集合$X$的一个分划。

置换群

群的定义

若集合$S\not=\varnothing$和$S$上的运算$\circ$构成的代数结构$(S,\circ)$满足：

• 封闭性:$S\times S\to S$
• 结合律:$\forall a,b,c\in S.(a\circ b)\circ c=a\circ(b\circ c)$
• 单位元:$\exists e\in S.\forall a\in S.a\circ e=e\circ a=a$
• 逆元:$\forall a\in S.\exists b\in S.a\circ b=b\circ a=e$，记作$a^{-1}$

则称$(S,\circ)$是一个群，若一个群满足交换律则称为阿贝尔群，否则称为非阿贝尔群。
若$T\subseteq S$且$(T,\circ)$也是群，则称$(T,\circ)$是$(S,\circ)$的子群。

置换

置换的定义

有限集合到自身的双射$f:A\leftrightarrow A$称为置换，集合$S=\{a_1,a_1,…,a_n\}$上的置换可表示为

$$f= \begin{pmatrix} a_1 & a_2 & ... & a_n\\ a_{p_1} & a_{p_2} & ... & a_{p_n} \end{pmatrix}$$

表示将$a_i$映射为$a_{p_i}$。

• $n$元集合上的置换有$n!$个
• 将置换$f$的每个$i$指向$p_i$，得到一个环的森林

置换的复合

对于两个置换$f=\begin{pmatrix}a_1&a_2&…&a_n\\a_{p_1}&a_{p_2}&…&a_{p_n}\end{pmatrix}$和$g=\begin{pmatrix}a_{p_1}&a_{p_2}&…&a_{p_n}\\a_{q_1}&a_{q_2}&…&a_{q_n}\end{pmatrix}$，有其复合

$$f\circ g= \begin{pmatrix} a_1 & a_2 & ... & a_n\\ a_{q_1} & a_{q_2} & ... & a_{q_n} \end{pmatrix}$$

置换群

显然集合$S$上的所有置换关于置换的复合满足群的条件，因此$(f的全集,\circ)$构成一个群，这个群的任意一个子群称为置换群。

循环置换

循环置换是一类特殊的置换，可表示为

$$(a_1\;a_2\;...\;a_m)= \begin{pmatrix} a_1 & a_2 & ... & a_{m - 1} & a_m\\ a_2 & a_3 & ... & a_m & a_1 \end{pmatrix}$$

若两个循环置换不含有相同的元素，称他们是不相交的，有：
任意一个置换都可以分解为若干个不相交的循环置换的复合，如

$$\begin{pmatrix} a_1 & a_2 & a_3 & a_4 & a_5\\ a_3 & a_1 & a_2 & a_5 & a_4 \end{pmatrix}= (a_1\;a_3\;a_2)\circ(a_4\;a_5)$$

设$g_i=(a_i,a_{i+1},…,a_m,a_1,a_2,…,a_{i-1})$，定义$G=\{g_0,g_1,…,g_{n-1}\}$称为正$n$边形的旋转群。

群对集合的作用

设$(G,\circ)$是一个群，其单位元为$e$，$X$是一个集合，群$G$对集合$X$的一个作用是一个$G\times X$到$X$的映射$f$，满足：

• $\forall x\in X.f(e,x)=x$
• $\forall g,h\in G.f(h\circ g,x)=f(h,f(g,x))$

简记$f(g,x)$为$g_f(x)$。
$X$上的$G$关系：$R_G=\{(x,y)|x,y\in X\land(\exists g\in G.y=g(x))\}$
$R_G$是等价关系，它将$X$划分为若干个等价类，每个等价类称为$X$上的一个$G$-轨道。

Burnside引理

设有限群$(G,\circ)$作用在有限集$X$上，则$X$上的$G$-轨道数量为

$$N=\dfrac{1}{\left|G\right|}\sum\limits_{g\in G}\Psi(g)\\ \Psi(g)=\sum\limits_{x\in X}[g(x)=x]$$

例如对于正$n$边形的旋转群$g$，有

$$\Psi(g_i)=m^{g_i环数量}=m^{(n,i)}$$

一个经典问题是给一个$n$元环的节点涂上颜色，有$m$种颜色，通过旋转相同的涂色方案为同一个方案，求方案数。

$$N=\dfrac{1}{n}\sum\limits_{i=0}^{n-1}m^{(n,i)}=\dfrac{1}{n}\sum\limits_{d|n}\phi(d)m^{\frac{n}{d}}$$

置换群的轮换指标

轮换的形式：把置换中每个环上的节点按顺序记录下来，它是置换的另一种形式，比如$g=[3,4,5,6,1,2]=(135)(246)$
置换型：如果$n$元置换$g$中有$b_i$个长度为$i$的轮换（其实就是环，$1\le i\le n$），则称这个置换$g$型为$1^{b_1}2^{b_2}…n^{b_n}$

设$(G,\circ)$是一个$n$元置换的置换群，它的轮换指标为

$$P_G(x_1,x_2,...,x_n)=\dfrac{1}{\left|G\right|}\sum\limits_{g\in G}x_1^{b_1}x_2^{b_2}...x_n^{b_n}$$

正$n$边形的旋转群的轮换指标：

$$P_G=\dfrac{1}{n}\sum\limits_{d|n}\phi(d)x_d^{n/d}$$

正$n$边形的二面体群的轮换指标：

$$P_G=\dfrac{1}{2n}\phi(d)x_d^{n/d}+\begin{cases} \dfrac{1}{2}x_1x_2^{\frac{n-1}{2}}&n为奇数\\ \dfrac{1}{4}(x_2^{\frac{n}{2}}+x_1^2x_2^{\frac{n-2}{2}})&n为偶数 \end{cases}$$

关于正方体的置换群：

• 顶点置换群：$P_G=\dfrac{1}{24}(x_1^8+8x_1^2x_3^2+9x_2^4+6x_4^4)$
• 边置换群：$P_G=\dfrac{1}{24}(x_1^{12}+8x_3^4+6x_1x_2^5+3x_2^6+6x_4^3)$
• 面置换群：$P_G=\dfrac{1}{24}(x_1^6+8x_3^2+6x_2^3+3x_1^2x_2^2+6x_1^2x_4)$