群论基础群论基础符号：记|G|为G的阶 ,即元素个数若H≤G ,记G/H为G中所有H的左陪集若H≤G ,记[G:H]为H对G的指数 ,即H在G中的不同的左陪集的数量群定义：若集合G≠∅ ,在G上的⼆元运算 ⋅ ,其共同构成的代数结构(G,⋅) ,满 ⾜：1.封闭性：∀a,b∈G,a⋅b∈G2.结合律：∀a,b,c∈G,(a⋅b)⋅c=a⋅(b⋅c)3.单位元：∃e∈G,∀a∈G,e⋅a=a⋅e=a4.逆元 ：∀a∈G,∃I∈G,a⋅I=I⋅a=e则(G,⋅)称为⼀个群性质：1.单位元唯⼀:若∃e1,e2,e1≠e2 ,有e1=e1⋅e2=e2 ,⽭盾2.逆元唯⼀ ：若∃I1,I2,I1≠I2 ,有I1=I1⋅e=I1⋅a⋅I2=I2 ,⽭盾⼦群定义：若H为G的⾮空⼦集 ,且(H,⋅)构成群 ,则称H是G的⼦群 ,记为H⩽商集定义：集合A为集合B关于等价关系\sim的商集合 ,记为A=B/\sim陪集定义：若G是⼀个群 ,H是G的⼀个⼦群 ,g是G的⼀个元素 ,则：gH=\{g \cdot h|h \in H\} ,则称gH为H在G内关于g的左陪集Hg=\{h \cdot g|h \in H\} ,则称Hg为H在G内关于g的右陪集性质(以左陪集为例)：1.\forall g \in G,|H|=|gH|显然运算前后阶不变2.\forall g \in G,g\in gHH必然包含e ,故必然有g \in gH3.gH=H \Longleftrightarrow g \in H由封闭性可知4.aH=bH \Longleftrightarrow a \cdot b^{-1} \in H有a \cdot b^{-1} \in H ,故由(3)可知命题成⽴5.aH \cap bH \neq \varnothing \Longleftrightarrow aH=bH设c \in aH,c \in bH ,于是\exists p_1,p_2 \in H, 使得p_1 \cdot a=c,p_2 \cdot b=c ,故 a \cdot b^{-1}=p_1^{-1} \cdot p_2 \in H ,由(4)可得命题成⽴6.H全体左陪集的并为G因为e \in H ,故得证正规⼦群定义：对于\forall g \in G，\exists gH=Hg ,则称H是G的正规⼦群Loading [MathJax]/jax/element/mml/optable/SuppMathOperators.js商群定义：对于群G和G的⼀个正规⼦群N ,构筑G在N上的商群 ,记为G/N ,即N 在G中所有的左陪集的集合 ,G/N=\{gN,g \in G\}拉格朗⽇定理若H为有限群G的⼦群 ,则|H|整除|G| ,|G|=|H|[G:H]证明：因为H在G中的每⼀个左陪集都是⼀个等价类 ,把G做左陪集分解 ,由于 每⼀个左陪集的元素个数都为|H| ,故|H|整除|G| ,商为[G:H]置换定义：⼀个集合到⾃⾝的双射表⽰：\sigma=\begin{pmatrix}a_1,a_2,\cdots,a_n\\a_{i1},a_{i2},\cdots,a_{in}\end{pmatrix}轮换定义:\sigma是\Omega上⼀个置换 ,若\Omega中⼀些点a_1,a_2,\cdots,a_s , 使得a^\sigma_1=a_2,a^\sigma_2=a_3,\cdots,a^\sigma_{n-1}=a_n,a^\sigma_n=a_1 ,⽽\sigma保持\Omega中其余点保持不 动 ,那么\sigma称作⼀个轮换 ,记作(a_1,a_2,\cdots,a_n) ,若两个轮换没有公共的变 动点 ,则称两个轮换不相交 ,每⼀个置换都能表⽰为不相交轮换的乘积 ，且表⽰⽅法唯⼀ ,⼀个长度为n的置换的k次⽅可分解成的轮换数是 (n,k)置换群定义：⼀个n元集合的全体n元置换构成的群性质：1.封闭性：\begin{pmatrix}a_1,a_2,\cdots,a_n\\b_1,b_2,\cdots,b_n\end{pmatrix}\begin{pmatrix}b_1,b_2,\cdots,b_n\\c_1,c_2,\cdots,c_n\end{pmatrix}=\begin{pmatrix}a_ 1,a_2,\cdots,a_n\\c_1,c_2,\cdots,c_n\end{pmatrix}2.结合性：(\begin{pmatrix}a_1,a_2,\cdots,a_n\\b_1,b_2,\cdots,b_n\end{pmatrix}\begin{pmatrix}b_1,b_2,\cdots,b_n\\c_1,c_2,\cdots,c_n\end{pmatrix})\begin{pmatrix}d_ 1,d_2,\cdots,d_n\\e_1,e_2,\cdots,e_n\end{pmatrix}\\=\begin{pmatrix}a_1,a_2,\cdots,a_n\\b_1,b_2,\cdots,b_n\end{pmatrix}(\begin{pmatrix}b_1,b_2,\cdots,b_n\\c_1,c_2,\cdots,c_n\end{pmatrix}\begin{pmatrix}d_1,d_2,\cdots,d_n\\e_1,e_2,\cdots,e_n\end{pmatrix})3.单位元：\begin{pmatrix}1,2,\cdots,n\\1,2,\cdots,n\end{pmatrix}4.逆元 ：\begin{pmatrix}a_1,a_2,\cdots,a_n\\b_1,b_2,\cdots,b_n\end{pmatrix}^{-1}=\begin{pmatrix}b_1,b_2,\cdots,b_n\\a_1,a_2,\cdots,a_n\end{pmatrix}作⽤：G是⼀个群 ,\Omega为⼀个⾮空集合 ,G中每⼀个元素g都对应\Omega的⼀个映射 ,x \rightarrow x_g,x \in \Omega ,若满⾜：1.x^{g_1g_2}=(x^{g_1})^{g_2}2.x^e=x则称G作⽤于\Omega上轨道-稳定⼦定理轨道：H=\{g \cdot x,x \in \Omega,g \in G\} ,则称H为\Omega在G作⽤下的⼀个轨道 ,代表元为 x ,记作G \cdot x稳定⼦：H=\{g \in G,g \cdot x=x\} ,则称H为\Omega的稳定⼦群 ,记作G_x有：|G|=|G \cdot x||G_x|证明：考虑⼀个映射f:G \rightarrow \Omega,\forall g \in G,f(g)=g \cdot x ,则可以在G_x的左陪集集合和 轨道G \cdot x间建⽴⼀个双射 ,gG_x唯⼀对应g \cdot x ,因为gG_x中的元素作⽤在x 上的结果均为g \cdot x ,根据拉格朗⽇定理 ,G_x在G中左陪集个数为[G:G_x] , 故|G \cdot x|=[G:G_x] \rightarrow |G|=|O_x||G_x|Burnside引理内容：G是⼀个有限群 ,G \rightarrow \Omega ,对每⼀个g \in G令\Omega^g表⽰\Omega在g作⽤下的不动 点 ,则有|\Omega/G|=\frac{1}{|G|}\sum\limits_{g \inG}|\Omega^g|证明：对\sum\limits_{g \in G}|\Omega^g|改变求和⽅式 ,\sum\limits_{g \in G}|\Omega^g|=|\{(g,x) \in G \cdot \Omega|g \cdot x=x\}|=\sum\limits_{x \in \Omega}|G_x|根据轨道-稳定⼦定理\sum\limits_{x \in \Omega}|G_x|=\sum\limits_{x \in \Omega}\frac{|G|}{|G \cdot x|}=|G|\sum\limits_{x \in \Omega}\frac{1}{|G \cdot x|}将x按照等价类划分 ,G \cdot x就是x所在等价类\sum\limits_{x \in \Omega}\frac{1}{|G \cdot x|}=\sum\limits_{A \in \Omega/G}\sum\limits_{x \in A}\frac{1}{|A|}=\sum\limits_{A \in \Omega/G}1=|\Omega/G|故：|\Omega/G|=\frac{1}{|G|}\sum\limits_{g \in G}|\Omega^g| ,得证Polya定理对于有m种颜⾊的染⾊问题 ,|\Omega^g|=m^{c(g)}考虑组合意义 ,|\Omega^g|表⽰在置换g作⽤下 ,保持不变的⽅案数 ,把g分解为不相 交的c(g)个轮换的乘积 ,若要其染⾊⽅案不变 ,则此染⾊⽅案中g分解成的每⼀ 个不相交轮换都要染相同的颜⾊ ,故|\Omega^g|=m^{c(g)}代⼊Burnside引理可得 ,|\Omega/G|=\frac{1}{|G|}\sum\limits_{g \in G}m^{c(g)}。
