10 08 2020

群论基础

一、基本定义

群:给定一个集合$G={a,b,c,...}$ 和集合上的二元运算“·”,要求满足下面四个条件:

  1. 封闭性:对于任意$a,b\in G$,一定存在$c \in G$,使得$a·b=c$
  2. 结合律:对于任意的$a,b,c\in G$ ,有$(a·b)·c=a·(b·c)$
  3. 单位元:存在$e \in G$,使得对于任意$a\in G$有$a·e=e·a=a$
  4. 逆元:对于任意$a\in G$,均存在$b \in G$,使得$a·b=e$,其中$b$是$a$的逆元,计作$a^{-1}=b$

若满足以上四种性质,则称集合$G$是在运算·下的一个群
若G是一个群,H是G的子集,且H在相同意义下满足群的性质,那么称H是G的一个子群

二、置换群

1.置换的定义

记一个序列${a_n={a_1,a_2,...,a_n}}$为1~n的一个排列
定义一个置换$p=$

$$ \begin{pmatrix} 1 & 2 & ... & n \\ a_1 & a_2 & ... &a_n \end{pmatrix} $$

其含义是将1变成$a_1$,2变成$a_2$,3变成$a_3$......
置换之间的运算如下
设$p_1=$

$$ \begin{pmatrix} 1 & 2 & ... & n\\ a_1 & a_2 & ... & a_n \end{pmatrix} $$

而$p_2=$

$$ \begin{pmatrix} 1 & 2 & ... & n\\ b_1 & b_2 & ... & b_n \end{pmatrix} $$

则$p_1p_2=$

$$ \begin{pmatrix} 1 & 2 & ... & n\\ b_{a_1} & b_{a_2} & ... & b_{a_n} \end{pmatrix} $$

2.置换群的定义

可以知道每个置换都可以与一个排列一一对应,那么$n!$个排列就对应了所有$n!$个置换,这些置换就可以构成一个群。

3.循环的定义

记$(a_1,a_2,...,a_m)$=

$$ \begin{pmatrix} a_1 & a_2 & ... & a_m \\ a_2 & a_3 & ... &a_1 \end{pmatrix} $$

这样我们可以用循环来写一个置换群,比如:$S_3=\{(1)(2)(3),(1)(23),(2)(13),(3)(12),(123),(132)\}$
若循环元素为$k$,则称这个元素为$k$阶循环

三、Burnside引理与polya定理

Burnside引理:设$G$是1~n上的一个置换群,则$G$在$n$上引出的等价类数量为所有置换不动点数量$c(p_i)$的平均值
polya定理:设$G$为$[1,n]$上的一个置换群,用$m$种颜色涂满$n$个对象,若两种涂色方法可以通过置换群的作用进行转化,则称这两种方案为统一方案,那么总方案的表达式是$\frac{\sum_{i=1}^{|G|}m^{c(p_i)}}{|G|}$

例题下篇文章再说吧呜呜呜呜呜菜死了

延伸阅读
  1. [LuoguP3834]主席树模板题 静态区间K大
  2. [LuoguP4551]最长异或路径
  3. [LuoguP2580]于是他错误的点名开始了
  4. [LuoguP3950] 部落冲突
  5. [HNOI2012] 永无乡
  6. [BJOI2016] 回转寿司
  7. [Codeforces 547B] Mike and Feet
  8. 午夜杂谈
更多阅读
  1. 上一篇:[LuoguP3834]主席树模板题 静态区间K大
  2. 下一篇:没有了
发表评论 抢沙发