0、置换群相关概念

n元置换：集合B,|B|=n上的一元运算、集合B到B的双射、集合B元素的重新排列。
n次置换群：集合B上的若干置换组成的群。
n次对称群$$S_n$$:集合B上的所有置换组成的群。(阶为n!)
n次交错群$$A_n$$:集合B上的所有偶置换组成的群；S的平方。(阶为n!/2)

1、置换群相关表示

n元置换的表示：
$$\pi: \alpha_1 \mapsto \alpha_2,\ \alpha_2 \mapsto \alpha_3,\ \alpha_3 \mapsto \alpha_1$$
$$\left( \begin{matrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{matrix} \right) $$
轮换表示：（按由小到大则唯一）
$$\left( \begin{matrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 3 & 1 & 4 & 5\end{matrix} \right) $$ = (2 3 1) = (3 1 2) = (1 2 3)、
特别的恒等变换$$\left( \begin{matrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{matrix} \right) $$记为(1)
轮换分解
$$\left( \begin{matrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 3 & 1 & 5 & 4\end{matrix} \right) $$ = $$\left( \begin{matrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 3 & 1 & 4 & 5\end{matrix} \right) $$ $$\left( \begin{matrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 2 & 3 & 5 & 4\end{matrix} \right) $$ =(1 2 3)(4 5)
不相交的轮换可以交换：
(1 2 3)(4 5)=(4 5)(1 2 3)
(1 3 2)(1 2 3)=(1 2 3)(1 3 2)
对换表示：（不唯一，但奇偶性确定=阶数减1）
(1 2 5 6)(3 4 7)= (1 2)(1 5)(1 6)*(1 3)(1 4)(1 7)(1 3)
(1 2 5 6)(3 4 7)= (5 6)(2 5)(1 2)*(4 7)(3 4)

2、置换的一般格式

$$S_n$$中相同格式的所有置换p组成共轭类.
对于置换p,设其中k阶循环出现的次数为$$c_k$$,k=1,2,…,n。
$$p=(1)^{c_1}(2)^{c_2} \cdots (n)^{c_n} ,\ \sum\limits_{k=1}^{n}kc_k=n$$
p共轭类元素个数：$$\frac{n!}{c_1!c_2!\cdots c_n!1^{c_1}2^{c_2}\cdots n^{c_n}}$$

分子$$n!$$
n个位置，按照$$(.)_1(.)_2\cdots(.)_{c_1}(..)_1(..)_2\cdots(..)_{c_2} \cdots $$排列，n个元素放入。
分母$$c_1!c_2!\cdots c_n!$$
$$c_k!$$个k阶循环，重复次数为全排列
分母$$1^{c_1}2^{c_2}\cdots n^{c_n}$$
$$k^{c_k}$$底数k表示k阶循环有k种表示方法,如(123)=(231)=(312)
$$c_k$$次方表示出现了$$c_k$$次k阶循环

3、群在集合上的作用（稳定子群、轨道划分）

X={1,2,…,n}, G是X上的一个置换群。
任取g∈G和x∈X,称g(x)为群G的元素g对x的作用，并称群G作用在集合X上，X为目标集.

X={1,2,3,4}
G={(1),(1 2),(3 4),(1 2)(3 4)}

x的稳定子不动置换类群 $$G_k$$:
使g(x)=x的所有g组成一个G的子群。
通俗理解：所有让某元素不变的函数集合（同时是G一个子群）。

G2={(1),(3,4)}

x的轨道等价类集合 G(k):是G的一个划分）
x在G所有置换后的结果g(x)组成的集合。
通俗理解：集合中某个元素在群中所有函数组成的值域。

G(2)={2,1}=G(1)
G(3)=G(4)={3,4}

若G(1)=X, 则称G为传递置换群（G只有一个轨道）
$$S_n,\ A_n $$都是传递置换群
拉格朗日定理推广：
对任一x: |G|=|G(x)|*|Gx|

G={(1),(1 2),(3 4),(1 2)(3 4)}
G2={(1),(3,4)}
G(2)={2,1}=G(1)
|G| = 4; |G(2)| = 2; |G2| = 2
验证：4 = 2 * 2

4、Burnside引理

$$G=\{g_1,g_2,\cdots,g_k\},\qquad c_1(g_k)$$是在置换$$g_k$$的作用下不动点的个数.
则G的轨道数（等价类数、划分个数）$$L = \frac{1}{\left | G \right | } [c_1(g_1)+c_1(g_2)+\cdots +c_1(g_k)]$$

G={(1),(1 2),(3 4),(1 2)(3 4)}
轨道{1,2}{3,4}, L=2
c1(g1)=4,c1(g2)=2,c1(g3)=2,c1(g4)=0
验证：L=(4+2+2+0)/4=2

例题1 有4个相同格子，用白蓝两种颜色着色，有多少种不同的方案？经过旋转90°或180°后相同的方案算同一种。
图片1.png
显然有16种涂色方案,我们设每种为一个元素，而每一种旋转就是一个置换：

不动：
```
a1=(1)(2)…(16)
```

逆90度：

a2=(1)(2)(3 4 5 6)(7 8 9 10)(11 12)(13 14 15 16)

顺90度：

 a3=(1)(2)(6 5 4 3)(10 9 8 7)(11 12)(16 15 14 13)

180度：
```
 a4=(1)(2)(3 5)(4 6)(7 9)(8 10)(11)(12)(13 15)(14 16)
```
这样原问题就转化成了求置换群G={a1,a2,a3,a4}的等价类个数了。

因此不同的方案数为： (16+2+2+4)/4=6。

5、Polya定理

$$L = \frac{1}{\left | G' \right | }[m^{c(a_1')}+m^{c(a_2')}+ \cdots +m^{c(a_k')}]$$

其中$$G'=\{a_1',\cdots,a_k'\},c(ai')$$表示置换$$a_i'$$的循环节数.

例1转换图

例2 等边三角形的三个顶点用红绿蓝三种颜色来着色，有多少种不同的方案？
保持不变的变换群包括：
1）沿中心旋转0，120，240度；
2）沿三条中线的翻转。
图片2.png
$$G=\{(1)(2)(3),(123),(321),(1)(23),(2)(13),(3)(12)\}$$
因此由Polya定理可知不同的方案数为：
$$L=\frac{1}{6}(3^3+3^1+3^1+3^2+3^2+3^2)=10$$
图片3.png
图片4.png
图片5.png
群作用于集合的各种证明演示图
(G(k)和Gk符号换一下)

其他例子：

子群
{(1),(12)(34),(13)(24),(14)(23)}
{(1),(12),(345),(354),(12)(345),(12)(354)}
{(1),(12),(365),(356),(12)(365),(12)(356)}

发表新评论

【置换群】基本概念