群
群的定义
一个群就是有一个集合\(G\)。定义一个二元运算 \("*"\)。 他们满足：
1.封闭性：\(a\)和\(b\)是群里的元素，那么\(a*b\)也是。
2.存在单位元\(e\)（其实就是类比乘法里的1）。\(a*e=e*a=a\)
3.每个元素a 都有唯一逆元\(a^{-1}\), \(a*a^{-1}=a^{-1}*a=e\)
4.结合律 \((a*b)*c=a*(b*c)\)
注意一般的群是不满足交换律的,如果满足交换律,我们称它为交换群(Abel群).
子群
如果\(G\)是群,\(H\)是\(G\)的子集,若H在G原来的定义下也成群,则称\(H\)为\(G\)的子群.
置换群
置换群可以表示一切有限群.
置换的概念很好理解,就是一个置换\(P=\left(\begin{matrix} 1&2&3&...&n\\a_1&a_2&a_3&...&a_n \end{matrix}\right)\)表示元素1被\(a_1\)取代,元素n被\(a_n\)取代.置换的乘法就是先做第一个置换再做第二个置换.
由很多置换构成的群就是置换群.
对称群
n个元素置换\(\left(\begin{matrix} 1&2&3&...&n\\a_1&a_2&a_3&...&a_n \end{matrix}\right)\),\(a_1,a_2,a_3...a_n\)为n!个不同的n的排列,这样构成的群就是n个文字的对称群,记为\(S_n\).
奇循环和偶循环
一种简单的表示置换的方法.
这个就叫m阶循环.
2阶循环\((i,j)\)称为i,j的对换或者换位.
任何一个置换都可以写成若干个对换之积.
若一个置换可以分解成奇数个对换之积,称为奇循环,反之称为偶循环.
奇循环不可能用偶循环之积表示,因为奇数次换位是不可能通过偶数次换位得到的.
\(S_n\)中偶置换全体构成一个\(\frac 1 2(n!)\)的子群,记为\(A_n\),称为交代群.偶循环形成的群显然满足封闭性了.
Burnside引理
共轭类
\(S_n\)具有相同格式的置换全体叫做该格式的共轭类.
这里的相同格式表示把一个置换\(p\)表示成不相交循环的乘积.下面的(k)表示k阶循环.
如果n个k对应的话就是形式相同.
容易得到\(S_n\)中的\((1)^{k_1}(2)^{k_2}...(n)^{k_n}\)形式的,共轭元素个数为
k不动置换类
置换群G中,使k保持不动的置换全体,称为G的k不动置换类,记为\(Z_k\).
等价类
若存在元素k可以置换为l,则k和l为相同等价类,元素 k所属的等价类记为\(E_k\)
重要定理
由于k可以通过\(|Z_k|\)种方式置换成自己,然后在通过某个置换p变为它等价类的任意一个元素,设\(G_j=Z_kp_j\),则\(G_1+G_2+...G_{E_k}\subseteq G\),\(G_j\)显然是不相交的.
又\(pp_j^{-1}\in Z_k\),所以\(p\in Z_kp_j\)因为p是G的任意元素,所以\(G\subseteq G_1+G_2+...G_{E_k}\)
Burnside
l表示不同的等价类个数.c(i)表示i置换下 一阶循环的个数.
i表示在i置换下不动点的个数,\(U_i\)表示第i个等价类的元素集合.
Polya
Polya定理主要用来解决染色问题计数问题.m表示颜色数,\(w(i)\)表示置换i的表示成不相交循环的循环数.这里的G是表示的n个对象m种染色的置换群,而是作用在n个对象上的置换群.这就省去了burnside大量的列举.
证明不会