群論&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個置換的循環節個數（軌道數）。

使用快速幂計算即可，具體題目具體分析。