浅谈群论 - kid_magic

浅谈群论 - kid_magic - 博客园

若HH是GG的子集且<H,op><H,op>为群,则<H,op><H,op>为<G,op><G,op>的子群

则HH既满足封闭性且求逆封闭,∀a,b∈H,ab∈H,a−1∈H∀a,b∈H,ab∈H,a−1∈H

等价于∀a,b∈H,ab−1∈H∀a,b∈H,ab−1∈H

一些特殊特殊的子群:

生成子群:a∈Ga∈G,则<{ai,i∈Z},op><{ai,i∈Z},op>称为生成子群

正规化子:a∈Ga∈G,则<{x|ax=xa,x∈G><{x|ax=xa,x∈G>称为正规化子,记为N(a)N(a)

共轭子群:a∈G,Ha∈G,H为GG的子群,则xHx−1xHx−1称为HH的共轭子群

等价关系:满足自反性a=aa=a,对称性a=b⇔b=aa=b⇔b=a,传递性a=b,b=c⇔a=ca=b,b=c⇔a=c(==代表的是等价关系)

等价类:xx的等价类[x]R={y|<x,y>∈R}[x]R={y|<x,y>∈R},RR是满足某种等价关系两个元素所有集合

可以认为是把等价关系看作边,[x]R[x]R是xx所在联通块的大小

商集:[A/R][A/R]指在以RR为等价关系时等价类的集合

陪集分为右陪集与左陪集,两个没区别

对于a∈Ga∈G,HH是GG的子群,称Ha={ha|h∈H}Ha={ha|h∈H}为HH的右陪集

如果HH为有限集,则|Ha|=|H||Ha|=|H|(不会证)

Lagrange定理

设HH为GG的子群,则|G||G|为|H||H|的倍数

考虑用陪集分解群

首先有个结论,∀a,b∈G,H∀a,b∈G,H为GG的子群,a∈Hb⇔Ha=Hb⇔ab−1∈Ha∈Hb⇔Ha=Hb⇔ab−1∈H

若已知a∈Hba∈Hb,则a=h1b,h1∈Ha=h1b,h1∈H,∀h2∈H∀h2∈H,h2a=h2h1bh2a=h2h1b,且h2h1∈Hh2h1∈H

则Ha⊆HbHa⊆Hb,反过来同理的Hb⊆HaHb⊆Ha,即Ha=HbHa=Hb

若已知Ha=HbHa=Hb,则∃h1,h2∈H,h1a=h2b∃h1,h2∈H,h1a=h2b,ab−1=h−11h2∈Hab−1=h1−1h2∈H

若已知ab−1∈Hab−1∈H,则ab−1=h∈Hab−1=h∈H,则a=hb∈Hba=hb∈Hb

如果将Ha=HbHa=Hb视为一种等价关系,HH一定单独是一个等价类

若a∉Ha∉H,则Ha≠HeHa≠He,即aa一定不与ee在同一等价类

又|Ha|=|H||Ha|=|H|,所以所有等价类大小相同

即|G||H|=|[G/R]|,R={<a,b>,Ha=Hb}|G||H|=|[G/R]|,R={<a,b>,Ha=Hb}

由此还可以得到共轭类分解

共轭关系也是一种等价关系,将a∈Ga∈G,所有与aa共轭的bb形成的集合称为共轭类

aa所在的共轭类大小为|G||N(a)||G||N(a)|

令x,y∈G,xax−1=yay−1x,y∈G,xax−1=yay−1

xa=yay−1x⇒y−1xa=ay−1x⇒y−1x∈N(a)⇒xN(a)=yN(a)xa=yay−1x⇒y−1xa=ay−1x⇒y−1x∈N(a)⇒xN(a)=yN(a)

如果沿用陪集分解的思路,因为xN(a)=yN(a)xN(a)=yN(a)则x,yx,y属于同一个等价类

用N(a)N(a)陪集分解,对于其中的一个等价类中所有的元素xx,xax−1xax−1确定aa的一个共轭

则共轭类的大小即为N(a)N(a)陪集分解后的等价类个数

置换群相关定理

置换群即为一个nn元排列PP组成的集合,定义运算PG=(GPi)PG=(GPi)

可证满足封闭性与求逆封闭

如果将ii和PiPi连有向边,则图为若干个不相交的环(nn条边nn个点)

当然,有时置换群不一定是一个排列的集合,但一定是置换的集合

轨道-稳定子群定理

定义一个集合AA,GG为一个作用于AA的置换群,a∈Aa∈A

定义Ga={g|g(a)=a,g∈G}Ga={g|g(a)=a,g∈G},称为稳定子群

G(a)={g(a),g∈G}G(a)={g(a),g∈G},称为轨道

|G|=|G(a)|×|Ga||G|=|G(a)|×|Ga|,证明如下

设x,y∈Gx,y∈G,且x(a)=y(a)x(a)=y(a),则⇔a=x−1(y(a))⇔x−1y∈Ga⇔xGa=yGa⇔a=x−1(y(a))⇔x−1y∈Ga⇔xGa=yGa

将GG以GaGa陪集分解,则当x(a)=y(a)x(a)=y(a)时x,yx,y属于同一等价类

考虑等价类的个数即为有多少个不同的x(a)x(a)即为|G(a)||G(a)|

Burnside 引理

[A/G]=1|G|∑g∈G[Ag][A/G]=1|G|∑g∈G[Ag],AgAg的定义与GaGa类似,就是Ag={a|g(a)=a,a∈A}Ag={a|g(a)=a,a∈A}

|Ga|=|G||G(a)||Ga|=|G||G(a)|，两边同时求和

∑a∈A|Ga|=∑a∈A|G||G(a)|=|G|∑a∈A1|G(a)|∑a∈A|Ga|=∑a∈A|G||G(a)|=|G|∑a∈A1|G(a)|

观察∑a∈A1|G(a)|∑a∈A1|G(a)|，本质为轨道个数(每一个aa所在的等价类大小分之11求和就是等价类的个数)=[A/G][A/G]

∑a∈A|Ga|=∑g∈G[Ag]=|G|×|[A/G]|∑a∈A|Ga|=∑g∈G[Ag]=|G|×|[A/G]|

即[A/G]=1|G|∑g∈G[Ag][A/G]=1|G|∑g∈G[Ag]

在这里我们给问题赋予一个实际意义

考虑AA表示问题的所有方案,GG为问题视为重复方案的置换

[A/G][A/G]即为将GG看作一个等价关系的集合后划分出的等价类集合

GaGa即为满足对aa置换作用后依旧不变的置换,AgAg差不多

G(a)G(a)为与aa一起视为一种方案的方案集合,也可一看作是aa所在的等价类

再具体一点的例子就是环的着色问题

Pólya 定理

具体到染色问题,假设有mm种颜色

则Ag=mc(g)Ag=mc(g),c(g)c(g)为gg的不相交循环个数

【模板】Pólya 定理

给定一个 nn 个点，nn 条边的环，有 nn 种颜色，给每个顶点染色，问有多少种本质不同的染色方案，答案对 109+7109+7 取模

注意本题的本质不同，定义为：只需要不能通过旋转与别的染色方案相同。

很明显GG为一个轮换了ii次的置换群

问题在于计算c(g)c(g),考虑gg是轮换了ii次的的置换,当前位置为pp

p−>(p+i)mod n−>(p+2i)mod n.....p′mod n=pp−>(p+i)modn−>(p+2i)modn.....p′modn=p

即p+(n/c(g))i=p+knp+(n/c(g))i=p+kn,即c(g)=ikc(g)=ik，则c(g)c(g)既为nn的因数也为ii的因数且最大

则c(g)=gcd(i,n)c(g)=gcd(i,n)

[A/G]=1|G|∑g∈Gnc(g)=1n∑i=1nngcd(i,n)[A/G]=1|G|∑g∈Gnc(g)=1n∑i=1nngcd(i,n)

令f(x)=nxf(x)=nx

[A/G]=1n∑i=1nf(gcd(i,n))=1n∑d|nf(d)∑i=1[gcd(i,n)=d]=1n∑d|nf(d)ϕ(nd)[A/G]=1n∑i=1nf(gcd(i,n))=1n∑d|nf(d)∑i=1[gcd(i,n)=d]=1n∑d|nf(d)ϕ(nd)

这里用dfsdfs凑因子可以做到Θ(n−−√)Θ(n)

Magic Bracelet

金妮的生日快到了。哈利波特正在为他的新女友准备生日礼物。礼物是一个由nn颗魔法珠组成的魔法手镯。有mm种不同的魔珠。每种珠子都有其独特的特征。将许多珠子串在一起，将制作一个漂亮的圆形魔法手镯。正如哈利波特的朋友赫敏所指出的那样，某些种类的珠子会相互作用并爆炸，哈利波特必须非常小心地确保这些对的珠子不会并排串在一起,有无数种珠子。如果忽略围绕手镯中心旋转产生的重复，哈利能制作多少种不同的手镯？找到取模 99739973 的答案。

同样定义GG为轮换ii次的置换群,但由于不能随便染色,所以不能用PólyaPólya定理

[A/G]=1|G|∑g∈G|Ag|[A/G]=1|G|∑g∈G|Ag|

瓶颈在于计算|Ag||Ag|

我们将gg拆分成不同的循环,这些循环的内部的点颜色是相同的且每个循环大小相同,问题是不同循环之间的关系

如果我们把一个循环看成一个点,再将和他有关系的连边,最后连出还是一个环

我们可以考虑只在这个环上计算答案

设f(x)f(x)为长度为xx的环时的答案

[A/G]=1n∑g∈G|Ag|=1n∑d|nf(d)ϕ(nd)[A/G]=1n∑g∈G|Ag|=1n∑d|nf(d)ϕ(nd)

现在问题在与如何计算f(x)f(x)

构造一个邻接矩阵TT,矛盾为00，否则为11,则TxTx时的对角线之和即为f(x)f(x)

__EOF__