群论

群论

什么是群?
元素和建立在元素上的二元运算构成的代数系统
如何判定是否是一个群?
要求满足四条群公理
为群满足如下公理

  • 封闭性
  • 结合率
  • 单位元
  • 逆元
    群中逆元分左右 但是左逆元=右逆元
    证明:
    规定这里a是x的左逆元


    a是x的右逆元

G中所含元素的个数称为群G的阶记为|G|
分有限无限群多种概念
群中元素的阶

在群G中,a∈G。如果有整数k,使,那么使这个等式成立的最小正整数k叫做a的阶,记为k=|a|
(表示连续k个a进行G中规定的运算,不是传统意义上的k个a相乘)
如果这样的k不存在,则称a的阶是无限的,记为a=+∞

消去律

逆元存在与消去律等价
逆元存在消去率存在
两边同时即可
消去率存在逆元存在
建立一个新的二元组
根据封闭性
因为消去率所以
即S’=S 因为所以
又因为定义了新的运算 故

拉格朗日定理

有限群(S,+)有子群(S’,+)
有|S|是|S’|的倍数
证明:
设一个子群
就有陪集



因为

使得



因为这时候a,b,x,y都是钦定好的 那么遍历z的时候都会有唯一的与之对应 所以恰好遍历G’ 所以得证
于是我们可以知道两个陪集要么相等要么不相交
然而我所有的并是所以 假设
那么一定是x的倍数 所以得证

欧拉定理用拉格朗日定理的证明

设集合
其中则S与模乘法形成的是群 证明 简单想象即可
那么设
那么可知的子群
因群中元素互相做运算仍然是群中的元素

轨道-稳定化子定理

考虑置换群G 其中每个元素是1~n的置换
G中使得元素x不变的置换构成一个子群
稳定
x通过G中变换到的位置叫做称为轨道

实际是stab(x)的陪集数
因为考虑每个可以变换到的位置 使得
造出的陪集是 |orbit(x)|个即orbit(x)是不重复的陪集的个数
根据拉格朗日定理

置换 置换群

例如
是一个置换但不是群 置换仅仅和每列相对应字符有关与自身列顺序无关


经过如下置换

成为


置换群将置换作为元素且满足群的性质

Burnside引理

该引理用于计算集合M关于置换群G的轨道数
定义两个元素是否本质质相同设两个元素x,y
使得那么x,y即是本质相同的
M的轨道数即 M中本质不同的元素个数
感觉本质不同的元素个数就是循环的个数
M中的轨道数可以记为
因为可以考虑每个轨道中都有个元素 然而每个元素对答案的贡献都会是
直接带入轨道-稳定化子定理
原式

那么我们计算的时候只需要得到的个数即可
总结起来 集合M关于置换群G的轨道数等于G中每个置换下不动点的个数的平均数
但是这个似乎自己只会搜索 复杂度不够优秀
需要对每个置换计算这个置换下不变的方案个数
于是有polya计数法

Polya

公式:对一个置换p设c(p) 表示p中循环节个数
G是定义在X上的置换群 即项链或棋盘如果用m种颜色来染色 那么本质不同的方案数


分类: polya

elijahqi

辣鸡蒟蒻一枚qwq 欢迎加qq qwq 2922945330

发表评论