群论&polya定理笔记

一、群

（一）定义

一种包含一些元素和相关元素的一个运算符的结构

（二）基本性质

1、封闭性：∀x,y∈S,x⊕y∈S(x,y可以相等)

2、结合律：∀a,b,c∈S,a⊕b⊕c=a⊕(b⊕c)(a,b,c可以相等)

3、单位元：∃e∈S,∀x∈S,e⊕x=x⊕e=x(x,e可以相等，我们往往用e代表单位元，也叫幺元)

4、逆元：∀x∈S,∃y∈S,x⊕y=y⊕x=e(x,y可以相等，我们称y为x的逆元，记作x−1)

若s⊕x=e，则s是x的左逆元，若x⊕t=e，则t是x的右逆元，所以逆元唯一。

需要注意的是，群内元素不一定满足交换律和分配律。

（部分转自http://blog.csdn.net/ta201314/article/details/51050846）

（三）一些证明

首先，x^-1中x不一定是数，可以是任意元素，x^-1指x在某运算下的逆元。

例如：

在（实数，+）这个群中，e=0 x^-1=-x

在（实数，*）中，e=1，x^-1=1/x

1.若x存在左逆元，则右逆元一定和左逆元大小相等，即只有一个逆元。

证明：

s⊕x=e

x⊕t=e

s=s⊕e=s⊕x⊕t=e⊕t=t

2.逆元的存在与消去律等价

逆元->消去律：只需在等式两边⊕a−1即可。

消去律->逆元：对于a，若∀x,y∈S,ax=ay<=>x=y，则令S′=ax|x∈S，因为ax互不相同，所以|S′|=|S|，又因为封闭性，所以S′⊂S，即S′=S，那么必然∃e∈S′，即∃x∈S,ax=e，于是我们就找到了a的逆元。（转自TA）

（四）拉格朗日定理

内容：

若(s,+)有子群(s’,+)，则|s|是|s’|的倍数。

首先引入陪集的概念：对于集合s，左陪集Sa={a+x|x∈S}，右陪集同理。

证明：

∃x,y∈S

x⊕a=y⊕b

a=x−1⊕y⊕b

∀z∈S′,z⊕a=z⊕(x−1⊕y⊕b)=(z⊕x−1⊕y)⊕b

即对于一个元素z属于Sa陪集，一定有一个元素属于Sb，所以|Sa|=|Sb|。

又因为s的所有陪集大小相等且互不相交，所以|S’|||S|，证毕。

（五）轨道-稳定化子定理

对于置换群G，其中每个元素是1~n的置换。

稳定集 stab(x)={f∈G | f(x)=x}，即不会使x发生置换的数量。

x通过G中的置换能变换到的位置称为x的轨道

轨道数：orbit(x)={f(x) | f∈G}

|orbit(x)|实际上是stab(x)的陪集数,也就是说，把s中的元素拿出来和stab(x)造陪集，一共能造出orbit(x)个陪集。可以理解为使stab(x)++的每一个元素所造出的陪集是相同的，最终造出的陪集数就是轨道数。

由拉格朗日定理有：

|orbit(x)|∗|stab(x)|=|G|

（六） burnside引理

群论中最重要的引理。

对于一个置换，轨道数=循环节数=轮换数，轨道长度=循环节长度。

此引理用于求M中本质不同的元素个数，若置换f(),使得f(x)=y，则x与y本质相同。

设M为集合，G为置换群。

引理：

M中的轨道数：

∑x∈M1|orbit(x)|

对于一个轨道中的所有元素，设轨道长度为k，则有k个元素，每个元素计算k次，每次加1/k,这样对于一个轨道/循环节来说就使答案加一。

再由轨道-稳定化子定理得

=∑x∈Mstab(x)|G|

=1|G|∗∑x∈Mstab(x)

=1|G|∗∑f∈G|{x∈m|f(x)=x}|

根据上式，可以使用二重循环求解。

吕欣总结的burnside引理：

集合 M 关于置换群 G 的轨道

数，等于 G 中每个置换下不不动点的个数的算术平均

数。

（七）polya定理

最实用的群论知识。

实质就是burnside引理，换个形式而已，但便于实现和计算。

内容：

定义置换群G，其中的每一个置换f若使得f(x)等于y，则x与y本质相同。

使用c中颜色对n个点染色，其本质不同的方案数为：

1|G|∗(cf1+cf2+⋯+cf|G|)

其中c^fn指置换群G中第n个置换的循环节个数（轨道数）。

使用快速幂计算即可，具体题目具体分析。