置换群（本蒟蒻瞎BB的）（未完）
群的定义
给定一个集合(G={a, b, c...})和集合(G)上的二元运算*，并满足：
-
封闭性：(forall a, b in G, exists c in G, a*b=c)。也就是集合里的元素怎么乱搞都只能搞出来集合里的东西。
-
结合律：(forall a, b, c in G, (a*b)*c=a*(b*c))。注意不一定满足交换律哟。
-
单位元：(exists e in G, forall a in G, a*e=e*a=a)。也就是说存在一个元素e，任意一个元素和它运算得到它本身。其中e叫做单位元。
-
逆元：(forall a in G, exists b in G, a*b=b*a=e)，记(b=a^{-1})。也就是说对于任何一个元素，都有另一个元素和它运算得到单位元。由于不一定有交换律，所以还有左右逆元之分。然而在群中左逆元=右逆元。
证明：(forall x in G,exists a in G, ax=e)，即a是X的左逆元。
显然(exists b in G,ba=e)。也就是说b是a的左逆元。
那么(xa=(ba)(xa)=b(ax)a=ba=e)（结合律），也就是说a也是x的右逆元。
则称集合G在运算“*”上是一个群，简称G是群。一般a*b简写成ab，*可以是任意运算。若G中的元素个数是有限的，则称G为有限群，否则称为无限群。有限群的元素个数称为有限群的阶。
群的运算
对于(g in G)，对于G的子集H，定义(g*H={gh mid hin H})，即g对H中的每一个元素运算而生成的集合，简写为gH。同理，H*G简写为Hg，有毒。
对于G的子集A，B，定义(A*B={ab mid a in A,b in B})
对于G的子集H，记(H^{-1}={h^{-1} mid h in H})。也就是H的逆就是H中所有元素的逆组成的集合。
定理1：在具有封闭性，结合律，单位元和逆元的二元组(G，*)里，消去律存在
消去律的定义：对于群中的消去律来说，它的定义是x=y与xa=ya互为充要条件。也就是说等式两边可以同时消掉一个相同的量。
证明很简单，只需要在xa=ya两边同时乘以(a^{-1})即可。
定理2：若(G，*)满足封闭性，结合律，单位元和消去律，则对于任一(g in G)，gG=Gg=G
简单来说，这个定理的意思是，挑出集合中的一个元素，和集合内所有的元素都搞一遍，搞出来的还是原来那个集合。
证明：根据封闭性，(gG subseteq G)。并且根据定理1的消去律，在gG中不会出现类似于(xa=ya (x, yin gG))这样的情况（不然违背集合的不重复性），所以(|gG|=|G|)。因此，(gG=G)。同理可证得(Gg=G)。
定理3：在具有封闭性，结合律，单位元和消去律的二元组(G，*)里，逆元存在
证明：任意取一个G中的元素g，由于gG=G，所以gG中一定含有单位元e。这表明，G中有一个元素，和g运算得到e。所以G中任意元素的逆元都存在。
定理4：若(G, *)是群，H是G的非空子集，并且(H, *)也是群，那么称H为G的子群。
根据定理4可以判断子集是否为一个子群：
- (HH=H)。如果这个条件满足，说明满足了封闭性。
- (H^{-1}=H)，即H中的每一个元素都有逆元，并且H中有单位元，因为只有单位元的逆元是单位元。
同时，因为H是G的子集，结合律也是满足的，所以H也是群，称为G的子群。
置换
置换的定义
设M是一个非空的有限集合，元素个数为n，M的一个一对一变换称为一个n元置换。如果把M的元素从1到n编号，那么置换(sigma)可以看作一个1到n的排列。
设(M={a_1, a_2, ..., a_n})，则M的置换(sigma)可简记为：(sigma = egin{pmatrix} a_1 & a_2...a_n\b_1 & b_2...b_n end{pmatrix})，(b_i=sigma(a_i))。考虑一下重排列的个数，易得M的置换有(n!)个。若(sigma(a_i)=a_i)，则(sigma)为n元恒等置换。(S_n)表示所有n元置换的集合。
举个栗子：(egin{pmatrix} 1,2,3,4 \ 3,1,2,4 \ end{pmatrix})，意思是原来在第一位上的元素要跑到第三位去，第二位上的元素要跑到第一位去……以此类推。在这个置换下，1234经过置换就变成了3124，再置换就变成了2314。容易发现置换的列随意调动，置换本身的含义并不变（第i号元素该跑到哪还是跑到哪），所以一般第一行就是123……n。
如果把(a_i)写成数列，画上(a_i)向(b_i)的箭头，那么置换就成了一个图。n元置换(sigma)对应的图形表达式是(G_sigma=sum^n_{i=1}a_iz_i)。(z_i)表示长度为i的圈，(a_i)表示如此的(z_i)的个数。显然有这样的等式：(a_1+2a_2+...+ra_n=n)。
当n相等时，置换是可以运算的，称为置换的连接。规则如下：(egin{pmatrix} 1,2,3,...,n \ a_1,a_2,a_3,...,a_n \ end{pmatrix} egin{pmatrix} a_1,a_2,a_3,...,a_n \ b_1,b_2,b_3,...,b_n \ end{pmatrix} =egin{pmatrix} 1,2,3,...,n \ b_1,b_2,b_3,...,b_n \ end{pmatrix})
无论置换怎样搞来搞去，一定都在(S_n)，这是封闭性中。显然置换的运算是满足结合律（置换同属(S_n)）的（试着从单个元素的变化去考虑），然而不满足交换律。同时，(S_n)中有单位元，也就是n元恒等置换。任意一个置换在(S_n)中都有逆元素，这个逆元素就是原置换两行调换后的置换。
所以在(S_n)中，置换的运算满足封闭性，结合律，同时单位元和逆元存在。那它，它就是个群啊！
置换群
n元置换的群体作成的集合(S_n)对置换的连接作成一个群，称为n次对称群（任意子群称作n次置换群）。
轮换
设(sigma)是M的置换，若可取到M的元素(a_1,a_2...,a_r)，使得(sigma (a_1)=a2,sigma (a_2)=a_3...sigma (a_{r-1})=a_r, sigma (a_r)=a_1)，而M的其余元素不变，则称(sigma)为一个轮换，记为((a_1 a_2 ... a_r))。相当于(egin{pmatrix} a_1 & a_2 ...a_{n-1} & a_n \ a_2 & a_3 ... a_n & a_1end{pmatrix})。可以把轮换的任意元素(a_i)排在头一位而改写成((a_i a_{i+1} ... a_r a_1 ... a_{i-1} ))。说白了就是每个元素跑到下一个元素代表的位置去。
有结论：((a_1 a_2 ... a_r)^{-1}=(a_r ... a_2 a_1))。结合置换去想就容易得出了。
不相杂轮换
两个轮换不相杂，意思是两个轮换中的元素没有相同的，也就是说互不干扰。由于互不干扰，不相杂轮换的运算显然是有结合律的。
有一个很重要的定理：任意置换(sigma)可以写成不相杂轮换的连接。如果不考虑乘积的顺序，则写法是唯一的。例如：(egin{pmatrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \ 3 & 1 & 5 & 4 & 2 & 8 & 7 & 6 end{pmatrix}=(1 3 5 2)(4)(6 8)(7)=(3 5 2 1)(7)(8 6)(4))。去掉单轮换也就是轮换表法的省略形式：((1 3 5 2)(6 8))。
为什么置换一定能写成轮换的连接呢？随便挑一个没有被选过的元素(a_1),找到它的置换(sigma(a_1)=a_2)，再找到(sigma(a_2)=a_3)……以此类推。由于n是有限的，总会回到(a_1)。因此这就是一个轮换。同理，再选择新的元素，要么属于原来的轮换。要么和原来的轮换没有交集。所以置换能写成多个轮换的连接。同时这个连接只有一种（显然法）。
对换
轮换的长度，表示轮换的元素集合中所含的元素个数。对换即是长度为2的轮换。由于((a_1 a_2...a_r)=(a_1 a_r)(a_1 a_{r-1})...(a_1 a_3)(a_1 a_2))。任何轮换都可以表示成n-1个对换的连接（未必只有一种）。
置换的奇偶性
设(sigma)表示为k个不相杂轮换的乘积（包括长度为1的轮换），每个轮换长度为(r_i)因为每个长度为r的轮换都可以写成r-1个对换的乘积。于是(sigma)可写成(sum^k_{j=1}(r_j-1)=n-k)个对换的乘积。如果n-k是奇数，称为奇对换，否则称为偶对换。因此n-k称为(sigma)的定性数。奇置换可表为奇数个对换之积，偶置换可表为偶数个对换之积。显然，奇偶对换的运算性质和奇偶数的加法运算是一样的。
设M的元数为n，若(n>1)，则奇置换的个数和偶置换的个数相等，都为(frac{n!}{2})。这可以用群的封闭性和消去律证明。
陪集
设H是群G的子群，对于G中的元素a，({ah mid h in H})表示H的一个左陪集，记作aH。({ha mid h in H})表示H的一个右陪集，记作Ha。简单来说，H中所有元素和a运算组成H的陪集。注意a不一定要在H中，在G中即可！下面是一些关于陪集的定理。不需要用到关于置换的内容。
定理1：H的任意陪集的大小相等，等于|H|。
这个定理的证明很简单，由于消去律和集合的不可重性可证。
定理2：(a in aH)且(a in Ha)
由于H是群，其中必有单位元e，(ae=e)。
定理3：(a in H)和(aH=H)，(Ha=H)互为充要条件
(a in H)是(aH=H)的充分条件，由群的运算中的定理二可得。
(aH=H)是(a in H)的充分条件，由陪集中的定理二即可得。右陪集同理。
定理4：(b in aH)和(bH=aH)互为充要条件（证明需要紧抓H是群的条件）（右陪集同理）
(bH=aH)是(b in aH)的充分条件，由性质二，即(b in bH)可得。右陪集同理
(b in aH)是(bH=aH)的充分条件，原因是b可以被写成(ax (x in H))的形式。由于H是群，(bH=axH=aH)。右陪集同理。
定理5：(aH cap bH e emptyset)能推出(aH=bH)（右陪集同理）
设(c in aH cap bH)，由定理4得(cH=aH=bH)。通过这个可以得出结论：对于G得子群H，H的两个同向陪集要么相等，要么不相交。
定理6：(cup_{x in G}xH=G)（右陪集同理）
因为(e in H)，所以枚举所有的(x in G)，得出的陪集并起来一定包含于G。同时由于封闭性等于G。
拉格朗日定理
若H是有限群G的子群，那么(|X|)整除(|G|)。
由定理5可知，H的陪集之间要么相等要么不相交。由性质6可知，H所有陪集的并等于G。由于H的陪集大小等于H，我们把H的不重合的陪集，想象成若干条不相交的线段，覆盖在G上。因此，G就被划分为了大小相等的若干段。因此这个定理就得证了。
插一句，考虑有限群G，(ain G)，元素的幂表示为(a^k=eprod_{i=1}^ka)。使得(a^d=e)的最小正整数d称为a的阶，记作(d=ord(a))。由于G为有限群，ord(a)一定存在。考虑由a的幂生成的集合：(S={a^k|kin Z})，显然S为G的子群。那么根据拉格朗日定理，我们可以证出一个神奇的东西——(|S|=ord(a)mid |G|)。它对关于原根的证明是有用的。
轨道-稳定集定理
轨道与等价类
集合(k)对置换群G中的所有元素运算构成的集合叫做(k)的轨道，记作(E_k)。我们也称(E_k)为包括(k)的等价类。说白了，一个集合和一个置换群搞出来的东西组成的集合，就叫做那个集合的轨道，也叫做包括原来集合的等价类。
稳定集
k是有限集X中m个元素构成的子集，置换群G中可以使k中元素不变的置换集合叫做k的一个稳定集，记为(Z_k)，说白了，使一个集合不变的（置换的简写轮换表示法中没有集合中元素）置换集合叫做稳定集。在m=1时，稳定集也称k中元素a的稳定化子。
由于(Z_k)中的置换(sigma)与k运算仍是k，(sigma_1 sigma_2)得到的结果一定也使k不变（从双射的角度去考虑）。这满足了封闭性。由于(ek=k)，所以单位元e存在。显然逆元和结合律也存在。所以(Z_k)是G的一个子群。
轨道-稳定集定理
|(E_k)|*|(Z_k)|=|G|，即集合k在G上的轨道数目，乘上k在G上的稳定集数目，等于G中的置换数目。
首先，(|E_k|)是(Z_k)的不重复陪集个数（待证）。所以——由于(Z_k)的陪集大小等于(Z_k)，并且(Z_k)的不重复陪集铺满了G，所以(Z_k)的陪集个数×(Z_k)的陪集大小=G，(|E_k|*|Z_k|=|G|)。哈哈快看，这是最新的美国大片，陪集的性质和拉格朗日定理的思想用上了。
着色
如果要用红蓝两色给一个正方形的四个顶点着色，若允许正方形转动和从边的中点翻转，有多少种着色方法？如果用从左上角开始，顺时针旋转得到的颜色序列表示正方形的着色，如RBRR，那么它和BRRR，RRRB，RRBR是一种着色，因为它们都可以通过旋转或翻转得到，所以它们组成了等价类。
Burnside引理
Burnside引理可以导出在置换群G的作用下，集合X的非等价着色数。