參考論文
這一部分在黑書中，
是在群論這一部分介紹的
是以我們先了解什麼是群
群的定義
給定一個集合G={a,b,c…}和集合G上的一個二進制計算*，滿足以下四個條件：
（1）封閉性
若a,b∈G,則存在唯一确定的c∈G,使得a*b=c;
（2）結合律成立
任意a,b,c∈G,有(a*b)* c=a* (b*c);
（3）機關元存在
存在e∈G,對任意a∈G，滿足a*e=e*a=a，稱e為機關元，也稱幺元;
（4）逆元存在
任意a∈G,存在唯一确定的b∈G, a*b=b*a=e（機關元），則稱a與b互為逆元素，簡稱逆元，記作a^(-1)=b.
通常稱G上的二進制運算*為“乘法”，稱a*b為a與b的積，并簡寫為ab.
若群G中元素個數是有限的，則G稱為有限群。否則稱為無限群。有限群的元素個數稱為有限群的階。
置換的定義
n個元素1,2,3,4,…，n之間的一個置換為
表示1被1到n中的某一個數a1取代，2被1到n中的某一個數a2取代，直到n被1到n中的某一個數an取代，且a1到an各不相同
置換群
置換群的元素是置換，運算的置換的連接配接
可以驗證置換群滿足群的四個條件：
循環
記
稱為n階循環
每個置換都可以看作是若幹互不相交的循環的乘積
為什麼呢？因為我們可以把每個元素看作是一個結點，
如果a變成b，連一條有向邊a—>b，則每一個節點一定有一個前驅結點和一個後繼結點，
即每個點的出度和入度都為1，這樣的圖對應就是若幹個環（輪換）
兩個循環(a1 a2 … an) (b1 b2 … bn)互不相交是指
ai！=bj（i，j=1,2,3,4,…,n）
例：
挺好了解的吧
這樣的表示是唯一的
置換的循環節數是上述表示中循環的個數
循環也稱為輪換
對換
簡單來說就是兩個元素的交換
經典模型
等價類計數問題
有這樣一個經典問題，給2*2方格中塗黑白兩色，有幾種方案
Ans.16
但是如果定義一種“旋轉操作”，規定逆時針旋轉90°，180°，270°後相同的方案算作一種，
那麼答案就變成6種了
這類問題被稱作是等價類計數問題
也就是說，題目中會定義一種等價關系，滿足等價關系的元素被看做是同一類
等價關系滿足自反性和傳遞性
- 自反性：A等價于B，則B等價于A
- 遺傳性：A等價于B，B等價于C，則A等價于C
有了等價關系，所有的元素就會被分成若幹等價類，
每個等價類裡的所有元素互相等價，不同等價類裡的元素不等價
為了統計等價類的個數
我們需要用一個置換集合F描述等價關系
比如說“逆時針旋轉90°”這個置換就可以把
映射到
注意
F中任意兩個置換的乘積也應當在F中，否則F無法構成置換群
對于一個置換f，若一個方案經過置換後不變，稱s為f的不動點
将f的不動點的數目記為C(f)，則有
Burnside 定理
等價類數目為所有C(f)的平均值
例如在本題中，
“逆時針旋轉180°”的不動點：
“逆時針旋轉90°”的不動點：
“逆時針旋轉270°”的不動點：
“逆時針旋轉0°”的不動點：
根據Burnside引理，答案是（16+2+2+4）/4=6
如何求C(f)呢？
我們先把格子編号
比如”逆時針旋轉180°“這個置換就可以看作是輪換（1,3）（2,4）的乘積
即1,3互換，2,4互換
則如果是不動點的話，1和3的顔色一定要一樣，2和4的顔色一定要一樣
而這兩和輪換不想交，是以互不影響，根據乘法原理一共有2*2=4種方案
一般的，
如果置換f被分解成m(f)個輪換，每個輪換内所有格子的顔色不必須相同，
假設有k種顔色，則有C(f)=k^m(f)
代入Burnside 定理表達式後得到Polya定理：
等價類個數等于所有置換f的k^m(f)的平均數
tip
一定要記住Burnside引理，一般的等價類問題均可以用ta解決