群
我现在已经不认识群这个字了
定义
群( ext{G})是定义在二元组((S,cdot))上的代数结构，其中(S)是一个集合,(Largecdot)是一个二元运算符。
定义( ext{G})中元素个数为( ext{G})的阶，记为(|G|)。
一般的，我们定义(|G|)为(+infin)的群为无限群，否则称之为有限群。
在群( ext{G})中,(forall ain G),若存在最小的(kin N^*),满足(a^k=e),则称(k)是(a)的阶，记做(|a|)或( ext{ord(a)})。
若( exists kin N^*)满足(a^k=e)，即(forall kin N^*,a^k e e)，定义( ext{ord(a)}=+infin)。
判定与性质
满足以下条件的二元组(G=(S,cdot))可以称作群。
1.封闭性:(large forall x,yin S,xcdot yin S)
2.结合律:(large forall x,y,zin S,xcdot(ycdot z)=(xcdot y)cdot z)
3.存在单位元:(largeexists ein S ,forall xin S,ecdot x=xcdot e=x)
4.存在逆元:(largeforall x in S,exists y in S,xcdot y=ycdot x=e)，一般记作(x^{-1})。
在(xcdot y=e)这个式子中，我们定义(x)为左逆元，(y)为右逆元。
则我们有结论:在群中，左逆元等于右逆元
证明：令(x)为( ext{G})中任意一元素，(exists ain G,acdot x=e)，即(a)为(x)的左逆元。
上式左乘(x)有(xcdot acdot x=xcdot e)，即(xcdot a=x^{-1}cdot e cdot x=e)，故(a)也为(x)的右逆元。
5.消去律:(large forall x,y,ain G,x=yiff xcdot a=ycdot a)
当(S)为有限集时，在满足封闭性，结合律，存在单位元的二元组((S,cdot))中，存在逆元(iff)满足消去律
充分性显然，下证必要性。
(forall a in S,)构造新二元组((S'={xcdot a|xin S},cdot))。根据封闭性，(S'subseteq S,)
考虑到存在消去律，(S')之间的元素必定不相同，否则(xcdot a=ycdot a ightarrow x=y)，与(S)集合的互异性矛盾。
故(|S|=|S'|)，即(S'=S)
( herefore ein S')
即(exists tcdot a=e)，得证。
在(S)为无限集时，存在逆元能推出满足消去律，反过来则不成立。
置换群
置换，轮换，对换
定义
有限集到自身的双射称之为置换,记做置换(f=egin{pmatrix}a_1,a_n,ldots,a_n\b_1,b_2,ldots,b_nend{pmatrix}),其中(a,b)是长为(n)的排列,意义代表逐个将(a_i)映射到(b_i)。
置换的不动点是元素(x)满足(f(x)=x)。
当(n)相等时，置换可以相互运算，并称之为置换的连接，定义为置换间的乘法。
显然置换乘法满足结合律，但不满足交换律。
称(I=f^0)为全等置换（即(a_i=b_i=i)的置换)，将置换(f)上下倒置可以得到(f^{-1})。
因此置换在置换乘法运算下构成置换群。
记一个(n)阶循环((a_1,a_2,ldots,a_n)=egin{pmatrix}a_1,a_2,ldots,a_n\a_2,a_3,ldots,a_1end{pmatrix})，循环也被称为轮换。
两个循环不相交指两个循环中没有相同的元素。
对换是长度为(2)的轮换,记做((a_x,a_y))。
我们称可以表述成偶数个对换的乘积的置换为偶置换，否则称之为奇置换。
性质
1.任意一个置换可以表示成若干个不相交循环的乘积。
2.(f^{-1})和(f)中各循环的元素和循环的个数相同。
3.( ext{ord}(f)=operatorname{lcm}(a_1,a_2,ldots,a_n))，其中(a_i)代表第(i)个轮换的长度（循环节大小）。
4.容易验证置换在置换乘法下，有通常的奇偶性质。(即奇奇得偶之类的性质)
轨道，稳定子集，稳定化子
定义
原集合元素(k)，在置换群( ext{G})中所有置换作用下像的集合叫做(k)的轨道(orbit)，也称(k)等价类，记作(k^G)（或( ext{orbit}(k)),(k)等价类(E_k)）。
置换群( ext{G})中使(S)的某个子集(A)中所有元素不动的置换构成的子集叫做(A)的一个稳定子集或稳定集(stable set)。
特别的,当(|A|=1)时，使(S)的某个元素(k)不动的置换构成的子集叫做(k)的稳定化子(stabilizer),记作(G_k)（或( ext{stab(k)})，(k)不动置换(Z_k)）
陪集
定义
设( ext{H})是( ext{G})的一个子群，对于(ain G,{acdot x,x in H})表示( ext{H})的一个左陪集，记作(aH);(ain G,{xcdot a,x in H})表示( ext H)的一个右陪集，记作(Ha)
性质
由于左右陪集证明方法相似，故除特殊说明，下面证明仅讨论都仅考虑左陪集的情况。
1.(forall ain G,|aH|=|H|)
根据( ext G)中的消去律,( ext H)是( ext G)的一个子群,因此，(forall ain G, exists x,yin Hsubseteq G,acdot x=acdot y)。
2.(ain aH)
(ecause ein H, herefore a=acdot ein aH)
3.(ain Hiff aH=H)
必要性
(ecause aH=H, herefore ain aH=H)
充分性
(ecause ain H)
( herefore forall bin H,a^{-1}bin H ightarrow bin aH)
( herefore aHsupseteq H)
结合性质1可知(aH=H)
4.(bin aHiff bH=aH)
(bH=aHiff a^{-1}bH=Hiff a^{-1}bin H(性质3)iff bin aH)
5.(aHcap bH eqemptysetiff aH=bH)
( herefore cin aHcap bH)，则(cin aH,cin bH, herefore cH=aH=bH)
6.(cup_{ain G}aH=G)
考虑到(ain aH)，显然成立
群论的基础定理
拉格朗日定理
设( ext H)是有限群( ext G)的子群,则H的阶整除G的阶。
即(frac {|G|}{|H|}=H)不同的陪集数。
证明
考虑由性质五，不同的陪集无交，大小均为(| ext H|)，而陪集并为( ext G)，故成立。
轨道-稳定化子定理(( ext{orbit-stabilizer theorem}))
对于一个置换群( ext G)和元素(k)有(|k^G|*|G_k|=|G|)
证明
(ecause f_1,f_2in G_k,(f_1cdot f_2)(k)=k)
所以(G_k)满足封闭性
(e(k)=k ightarrow ein G_k)
所以(G_k)存在单位元
我们已知置换乘法满足封闭性和消去律,而(G_k)是有限群。
所以(G_k)在置换乘法下构成群，(G_kin G)。
考虑所有置换(fin G),因为(forall sin G_k,s(k)=k),所以(forall sin fG_k,s(k)=f(k))，即，对于所有(G_k)的左陪集(fG_k)中的置换，作用于(k)的像和(f)对(k)的像相同。
所以(G_k)不同的左陪集(fG_k)的数量即为不同的(k)的像数量(|k^G|)
由拉格朗日定理，证毕。
( ext{Burnside})引理
令( ext G)是目标集([1,n])上的置换群，(c(f))表示在置换(f)下不动点的个数。
设( ext G)将([1,n])划分为(L)个等价类,则
证明
每个轨道对答案贡献为(1),所以每个点对答案的贡献是(frac 1{orbit(k)})。
由轨道-稳定化子定理，
考虑到，令(d_{i,j})表示点(i)在置换(j)下是否不变，(k)不动置换其实是横着对点(k)这一行求和，那么我们现在对列求和，那就是枚举(f)，我们自然得到(c(f)),于是有
( ext{P}acute{ ext{o}} ext{lya})定理
令( ext G)是目标集([1,n])上的置换群，(m(f))表示在置换(f)中轮换的个数，设(x)是目标集的排列为元素形成的集合，如果将([1,n])用(k)种颜色分别染色。
设(G)将(x)划分为(L)个等价类，则
证明
如果在置换(f)作用下方案不变，那么必须在同一个轮换上使用一种颜色，此时的不动点个数为(k^{m(f)})，由( ext{Burnside})引理，证毕。