浅谈群论
群
一些基础
子群
若(H)是(G)的子集且(
则(H)既满足封闭性且求逆封闭,(forall a,bin H,abin H,a^{-1}in H)
等价于(forall a,bin H,ab^{-1}in H)
一些特殊特殊的子群:
生成子群:(ain G),则()称为生成子群
正规化子:(ain G),则()称为正规化子,记为(N(a))
共轭子群:(ain G,H)为(G)的子群,则(xHx^{-1})称为(H)的共轭子群
等价类
等价关系:满足自反性(a=a),对称性(a=bLeftrightarrow b=a),传递性(a=b,b=cLeftrightarrow a=c)((=)代表的是等价关系)
等价类:(x)的等价类([x]_R={y|
可以认为是把等价关系看作边,([x]_R)是(x)所在联通块的大小
商集:([A/R])指在以(R)为等价关系时等价类的集合
陪集
陪集分为右陪集与左陪集,两个没区别
对于(ain G),(H)是(G)的子群,称(Ha={ha|hin H})为(H)的右陪集
如果(H)为有限集,则(|Ha|=|H|)(不会证)
Lagrange定理
设(H)为(G)的子群,则(|G|)为(|H|)的倍数
考虑用陪集分解群
首先有个结论,(forall a,bin G,H)为(G)的子群,(ain HbLeftrightarrow Ha=HbLeftrightarrow ab^{-1}in H)
若已知(ain Hb),则(a=h_1b,h_1in H),(forall h_2in H),(h_2a=h_2h_1b),且(h_2h_1in H)
则(Hasubseteq Hb),反过来同理的(Hbsubseteq Ha),即(Ha=Hb)
若已知(Ha=Hb),则(exist h_1,h_2in H,h_1a=h_2b),(ab^{-1}=h_1^{-1}h_2in H)
若已知(ab^{-1}in H),则(ab^{-1}=hin H),则(a=hbin Hb)
如果将(Ha=Hb)视为一种等价关系,(H)一定单独是一个等价类
若(anotin H),则(Hanot=He),即(a)一定不与(e)在同一等价类
又(|Ha|=|H|),所以所有等价类大小相同
即(dfrac{|G|}{|H|}=|[G/R]|,R={,Ha=Hb})
由此还可以得到共轭类分解
共轭关系也是一种等价关系,将(ain G),所有与(a)共轭的(b)形成的集合称为共轭类
(a)所在的共轭类大小为(dfrac{|G|}{|N(a)|})
令(x,yin G,xax^{-1}=yay^{-1})
(xa=yay^{-1}xRightarrow y^{-1}xa=ay^{-1}xRightarrow y^{-1}xin N(a)Rightarrow xN(a)=yN(a))
如果沿用陪集分解的思路,因为(xN(a)=yN(a))则(x,y)属于同一个等价类
用(N(a))陪集分解,对于其中的一个等价类中所有的元素(x),(xax^{-1})确定(a)的一个共轭
则共轭类的大小即为(N(a))陪集分解后的等价类个数
置换群相关定理
置换群
置换群即为一个(n)元排列(P)组成的集合,定义运算(PG=(G_{P_i}))
可证满足封闭性与求逆封闭
如果将(i)和(P_i)连有向边,则图为若干个不相交的环((n)条边(n)个点)
当然,有时置换群不一定是一个排列的集合,但一定是置换的集合
轨道-稳定子群定理
定义一个集合(A),(G)为一个作用于(A)的置换群,(ain A)
定义(G^a={g|g(a)=a,gin G }),称为稳定子群
(G(a)={g(a),gin G }),称为轨道
(|G|=|G(a)|times|G^a|),证明如下
设(x,yin G),且(x(a)=y(a)),则(Leftrightarrow a=x^{-1}(y(a))Leftrightarrow x^{-1}yin G^aLeftrightarrow xG^a=yG^a)
将(G)以(G^a)陪集分解,则当(x(a)=y(a))时(x,y)属于同一等价类
考虑等价类的个数即为有多少个不同的(x(a))即为(|G(a)|)
Burnside 引理
([A/G]=dfrac{1}{|G|}sumlimits_{gin G}[A^g]),(A^g)的定义与(G^a)类似,就是(A^g={a|g(a)=a,ain A })
(|G^a|=dfrac{|G|}{|G(a)|})，两边同时求和
(sumlimits_{ain A}|G^a|=sumlimits_{ain A}dfrac{|G|}{|G(a)|}=|G|sumlimits_{ain A}dfrac{1}{|G(a)|})
观察(sumlimits_{ain A}dfrac{1}{|G(a)|})，本质为轨道个数(每一个(a)所在的等价类大小分之(1)求和就是等价类的个数)=([A/G])
(sumlimits_{ain A}|G^a|=sumlimits_{gin G}[A^g]=|G|times|[A/G]|)
即([A/G]=dfrac{1}{|G|}sumlimits_{gin G}[A^g])
在这里我们给问题赋予一个实际意义
考虑(A)表示问题的所有方案,(G)为问题视为重复方案的置换
([A/G])即为将(G)看作一个等价关系的集合后划分出的等价类集合
(G^a)即为满足对(a)置换作用后依旧不变的置换,(A^g)差不多
(G(a))为与(a)一起视为一种方案的方案集合,也可一看作是(a)所在的等价类
再具体一点的例子就是环的着色问题
Pólya 定理
具体到染色问题,假设有(m)种颜色
则(A^g=m^{c(g)}),(c(g))为(g)的不相交循环个数
【模板】Pólya 定理
给定一个 (n) 个点，(n) 条边的环，有 (n) 种颜色，给每个顶点染色，问有多少种本质不同的染色方案，答案对 (10^9+7) 取模
注意本题的本质不同，定义为：只需要不能通过旋转与别的染色方案相同。
很明显(G)为一个轮换了(i)次的置换群
问题在于计算(c(g)),考虑(g)是轮换了(i)次的的置换,当前位置为(p)
(p->(p+i)mod n->(p+2i)mod n.....p'mod n=p)
即(p+(n/c(g))i=p+kn),即(c(g)=dfrac{i}{k})，则(c(g))既为(n)的因数也为(i)的因数且最大
则(c(g)=gcd(i,n))
([A/G]=dfrac{1}{|G|}sumlimits_{gin G} n^{c(g)}=dfrac{1}{n}sumlimits_{i=1}^nn^{gcd(i,n)})
令(f(x)=n^x)
([A/G]=dfrac{1}{n}sumlimits_{i=1}^nf(gcd(i,n))=dfrac{1}{n}sumlimits_{d|n}f(d)sumlimits_{i=1}[gcd(i,n)=d]=dfrac{1}{n}sumlimits_{d|n}f(d)phi(dfrac{n}{d}))
这里用(dfs)凑因子可以做到(Theta(sqrt n))
#include
using namespace std;
const int MOD=1e9+7;
int t;
int n;
int Pow(int a,int b,int p)
{
int res=1;
int base=a;
while(b)
{
if(b&1)
{
res=((long long)res*base)%p;
}
base=((long long)base*base)%p;
b>>=1;
}
return res;
}
vector >Rec;
int Phi[105][105];
int Pri[105][105];
int Used[105];
int Res=0;
void dfs(int x)
{
if(x==Rec.size())
{
int d=1;
int phi=1;
for(int i=0;i1)
{
Rec.push_back(make_pair(now,1));
}
for(int i=0;i Magic Bracelet
金妮的生日快到了。哈利波特正在为他的新女友准备生日礼物。礼物是一个由(n)颗魔法珠组成的魔法手镯。有(m)种不同的魔珠。每种珠子都有其独特的特征。将许多珠子串在一起，将制作一个漂亮的圆形魔法手镯。正如哈利波特的朋友赫敏所指出的那样，某些种类的珠子会相互作用并爆炸，哈利波特必须非常小心地确保这些对的珠子不会并排串在一起,有无数种珠子。如果忽略围绕手镯中心旋转产生的重复，哈利能制作多少种不同的手镯？找到取模 (9973) 的答案。
同样定义(G)为轮换(i)次的置换群,但由于不能随便染色,所以不能用(Pólya)定理
([A/G]=dfrac{1}{|G|}sumlimits_{gin G}|A^g|)
瓶颈在于计算(|A^g|)
我们将(g)拆分成不同的循环,这些循环的内部的点颜色是相同的且每个循环大小相同,问题是不同循环之间的关系
如果我们把一个循环看成一个点,再将和他有关系的连边,最后连出还是一个环
我们可以考虑只在这个环上计算答案
设(f(x))为长度为(x)的环时的答案
([A/G]=dfrac{1}{n}sumlimits_{gin G}|A^g|=dfrac{1}{n}sumlimits_{d|n}f(d)phi(dfrac{n}{d}))
现在问题在与如何计算(f(x))
构造一个邻接矩阵(T),矛盾为(0)，否则为(1),则(T^x)时的对角线之和即为(f(x))
#include
#include
#include
#include
using namespace std;
const int MOD=9973;
int t;
int m;
int x,y;
int k;
int Pow(int a,int b,int p)
{
int res=1;
int base=(a%p);
while(b)
{
if(b&1)
{
res=(res*base)%p;
}
base=(base*base)%p;
b>>=1;
}
return res;
}
struct Martix{
int n, m;
int val[10][10];
void clear() { memset(val, 0, sizeof(val)); }
void init() {
clear();
for (int i = 0; i >= 1;
}
return Res;
}
int F(int x)
{
Martix IDSY=ppow(A,x);
int Res=0;
for(int i=0;i >Rec;
int Phi[205][205];
int Pri[205][205];
int Used[205];
int Res=0;
int n;
void dfs(int x)
{
if(x==Rec.size())
{
int d=1;
int phi=1;
for(int i=0;i1)
{
Rec.push_back(make_pair(now,1));
}
for(int i=0;i 文章来源于互联网：浅谈群论