群

概念

對于非空集合 \(G\)，\(\cdot\) 為集合內元素的二元運算。如果滿足：

1. 封閉性。對于 \(\forall a,b\in G\)，滿足 \(a\cdot b\in G\)。
2. 結合律。對于 \(\forall a,b,c\in G\)，滿足 \((a\cdot b)\cdot c=a\cdot(b\cdot c)\)。
3. 單位元。\(\exists e\in G\)，\(\forall a\in G\)，滿足 \(a\cdot e=e\cdot a=a\)。
4. 逆元。\(\forall a\in G\)，\(\exists b\in G\)，滿足 \(a\cdot b=b\cdot a=e\)。

則稱 \((G,\cdot)\) 為群。只滿足 \(1,2\) 稱為半群，滿足 \(1,2,3\) 稱為幺半群。

交換群：滿足交換律的群。

有限群：元素有限的群，\(|G|\) 為群的階。

• 常見的有限交換群：\((\Z_n,+)\)，\((\Z_p^*,\times)\)，\((\Z_n^*,\times)\)，\((\Z_{2^n},\oplus)\)

二面體群 \(D_{2n}(n\ge 3)\)：

對于一張正 \(n\) 邊形紙片，考慮所有對稱變換

• 沿中心旋轉 \(2\pi/n\)，記作 \(r\)。
• 沿某一對稱軸翻轉，記作 \(s\)。

不難發現所有的變換即 \(r^k\) 和 \(r^ks(0\le k<n)\)，構成 \(2n\) 階群，記作 \(D_{2n}\)。

對于 \(a\in G\)，定義 \(a\) 的階為使 \(a^k=e\) 的最小正整數 \(k\)，記作 \(o(a)=|a|=k\)。

有限群元素必有階，無限群未必，如 \((\Z,+)\)。

若 \(|a|=n\)，則

1. \(|a^{-1}|=n\)。
2. \(|a^k|=\frac{n}{\gcd(n,k)}\)。
3. \(\forall b,|bab^{-1}|=n\)。

其他性質

1. \(|a|\mid |G|。\)
2. \(\forall a,b,|ab|=|ba|\)。

子群

設有群 \((G,\cdot)\)，若 \(H\subseteq G\) 且 \((H,\cdot)\) 構成群，稱 \(H\) 為 \(G\) 的子群，記作 \(H\le G\)。

子群和子群的交集一定是子群，但并集不一定。

判定定理

當且僅當 \(\forall g,h\in H\) 有 \(g^{-1}h\in H\)，則 \(H\le G\)。

陪集

設群 \(G\) 及其子群 \(H\)，\(g\in G\)，則集合 \(gH=\{gh|h\in H\}\) 稱為子群 \(H\) 包含 \(g\) 的左陪集，右陪集同理。陪集不一定構成群。

• \(|gH|=|Hg|=|H|\)。
• \(H\) 的所有不同陪集 \(gH\) 構成 \(G\) 的一個劃分。

拉格朗日定理

\([G:H]\) 為 \(H\) 能夠生成的不同左（右）陪集數量，也稱為群 \(G\) 中子群 \(H\) 的指數。

推論：子群的階是群的階的約數。

循環群

循環群 \(C_n\)：由一個元素 \(a\) 反復自乘獲得 \(G\) 中所有元素。

稱 \(a\) 為生成元，由這種方式生成的群稱為 $\left \langle a \right \rangle $，讀作 \(a\) 的生成子群。循環群必是交換群。

若 \(a\) 為 \(C_n\) 的一個生成元，則所有的生成元為

數量為 \(\varphi(n)\) 個。可以將它視作為原根。

群同構

若群 \((G1,\cdot)\) 和 \((G_2,\times)\) 之間存在雙射 \(f:G_1\to G_2\)，\(\forall a,b\in G_1\) 滿足 \(f(a\cdot b)=f(a)\times f(b)\)，稱 \(G_1,G_2\) 同構，記作 \(G_1\cong G_2\)。

\((\Z_p^*,\times)\cong (\Z_{p-1},+)\cong C_{p-1}\)。只需構造雙射 \(f(g^a)=a\)，\(g\) 是 \(p\) 的一個原根。

群同態

把雙射改成映射。

置換群

置換：有限集合的一一變換，可用排列表示 \(p_1p_2p_3\dots p_n\)。

即 \(a_{1},a_{2},\dots,a_{n}\) 變為 \(a_{p_1},a_{p_2},\dots,a_{p_n}\)。

• 置換是映射且是雙射，可復合 $\circ $。
• 置換可以分解為若干輪換（環）或對換的復合。

置換群：若干 \(n\) 階置換構成的集合 \(G\) 與復合 \(\circ\) 運算。

全體 \(n\) 階置換構成的群成為循環群，用 \(S_n\) 表示，\(|S_n|=n!\)。\(\left\langle r,s\right\rangle=D_3\cong S_3\)。

凱萊定理：任意群 \(G\) 同構某個置換群。

群作用

若映射（二元函數） \(\alpha:G\times X\to X\)，

滿足（\(g,h\in G\)，\(x\in X\)，\(\alpha(g,x)=g\cdot x=g(x)\)）

• \((gh)\cdot x=g\cdot (h\cdot x)\)。
• \(e\cdot x=x\)。

則映射 \(\alpha\) 為 \(G\) 在 \(X\) 上的群作用。

軌道

設 \(G\) 作用在 \(X\) 上，定義集合

為群作用下的一個軌道，所有軌道構成 \(X\) 的劃分。同一軌道上的元素屬于同一個等價類。

穩定子

若 \(g(x)=x\)，稱 \(x\) 為 \(g\) 的一個不動點。

稱為 \(x\) 的穩定子群。

軌道 \(\cdot\) 穩定子定理

\(|G|=|O_x||G_x|\)。

Burnside 引理

軌道個數

\(X^g\) 表示 \(g\) 作用下的不動點集合。

考慮證明：

考慮在染色模型下 Burnside 的本質。

對于一個置換群，\(|X/G|\) 即求所有本質不同的染色方案，使得兩種方案不會在經過若干次置換后相同。

而 \(|X^g|\) 即代表有多少種染色方案在經過置換 \(g\) 之后與原方案相同。

Pólya 定理

設 \(G\) 作用在 \(X\) 上，在染色模型下，假設顏色集合為 \(C\)，則本質不同的染色方案個數為

\(c(g)\) 表示 \(g\) 分解的輪換數量。

再關注其本質。

對于置換 \(g\)，把 \((i,p_i)\) 看做一條邊，考慮將它分解成若干個環，如 \(3412\) 可以分解為 \((13)(24)\)，這即為輪換分解，環的個數即為輪換數量。

對于置換 \(g\)，稱它的型為 \((x_1)^{r_1}(x_2)^{r_2}\cdots\)，表示共有 \(r_i\) 個長度為 \(x_i\) 的輪換，在部分限定顏色數量的題目中需要用到輪換的長度。

然后考慮 \(|C|^{c(g)}\) 的意義。要求經過置換 \(g\) 本質不變，那么對于每個環的染色必須相同，共有 \(c(g)\) 個環，每個環有 \(|C|\) 種染色方案，即為上式。

模型一：空間幾何體

給定一個正方體，用 \(n\) 種顏色對它的邊/棱/角染色，求本質不同的方案數。

先確定置換群，以棱為例。

對 \(12\) 條棱標號，對于所有旋轉置換求出對應后的標號，然后進行輪換分解，求出答案。可以這樣考慮

• 恒等置換，\(1\) 種，型為 \((1)^{12}\)。
• 面面中心旋轉 \(90^{\circ}\)，\(3\times 2=6\) 種，型為 \((4)^3\)。
• 面面中心旋轉 \(180^{\circ}\)，\(3\) 種，型為 \((2)^6\)。
• 相對棱中心旋轉 \(180^{\circ}\)，\(6\) 種，型為 \((1)^2(2)^5\)。
• 對角旋轉 \(120^{\circ}\)，\(4\times 2=8\) 種，型為 \((3)^4\)。

令 \(L\) 表示向左旋轉 \(90^{\circ}\)，\(F\) 表示向前旋轉 \(90^{\circ}\)，則所有旋轉變換可以表示為 \(L^aF^b\)，分別寫轉換函數可以方便求出所有置換。

UVA10601 Cubes。

限制了每種顏色的個數。

一種方法是 [HNOI 2008] Cards 的思路，寫一個 \(O(n^6)\) 背包 dp，看一個環選擇哪種顏色。

另一種是注意到五種變換中只有第四種變換是存在長度不同的環的，而對于長度為 \(l\) 相同的環，可以視作有 \(\frac{12}{l}\) 個球；然后對于顏色 \(c\)，假如個數為 \(k\)，那么可以視作所有球中有 \(\frac{k}{l}\) 個顏色為 \(c\) 的球，如果 \(l\) 不整除 \(k\) 顯然方案數是為 \(0\) 的。

然后問題就變成有 \(6\) 種顏色的球求排列數，轉換成可重集的排列數。而對于第四種變換，顯然可以枚舉兩個長度為 \(1\) 的環怎么染色，然后同理即可。

模型二：環染色

如果旋轉翻轉同構，那么即為 \(D_{2n}\)。

考察旋轉操作。

• 設 \(g_k\) 為順時針旋轉 \(k\) 個點的置換，對于單個點，其周期 \(T\) 滿足 \(kT\equiv 0\pmod n\)，可得 \(T\) 的最小值為 \(\frac{n}{\gcd(k,n)}\)。

• 于是 \(g_k\) 對應的型為 \((\frac{n}{\gcd(k,n)})^{\gcd(k,n)}\)。

考察翻轉操作。

• 如果 \(n\) 為奇數，則 \(n\) 種翻轉操作一致，對稱軸上的點為 \(1\) 輪換，型為 \((1)^1(2)^{\frac{n-1}{2}}\)。
• 如果 \(n\) 為偶數，兩點為軸時型為 \((1)^2(2)^{\frac{n}{2}-1}\)，兩邊中點為軸時型為 \((2)^{\frac{n}{2}}\)。

旋轉翻轉同構同時，可以將所有顏色變為 \(+1\pmod m\)。

顯然是不能分開考慮的，因為不構成群。所以考慮復合。

翻轉復合操作較為簡單，考察旋轉復合操作。

考慮旋轉 \(i\) 個點，并且顏色 \(+d\)，對于一個環來說，長度為 \(k=\frac{n}{(n,i)}\)，那么對于環上的染色，需要滿足 \(a_2\equiv a_1+d\)，\(a_3\equiv a_2+d\) 以此類推。最終可以知道 \(kd\equiv 0\pmod m\)。于是 \(d\) 的取值有 \((k,m)\) 種，然后推一下式子即可。

[SHOI2006] 有色圖。

置換群顯然是點的排列。考慮對于一種點的置換，其邊的等價類的數量。

假如說該置換劃分出了長度分別為 \(b_1,b_2,\cdots,b_k\) 的置換環（相當于輪換）。那么對于一條邊，如果端點屬于同一個環中，則等價類的個數為 \(\lfloor \frac{b_i}{2}\rfloor\)，因為長度相同的環一定可以互相得到；如果不屬于同一個環中，則周期為 \(\text{lcm}(b_i,b_j)\)，所以等價類個數為 \(\frac{b_ib_j}{\text{lcm}(b_i,b_j)}=\gcd(b_i,b_j)\)。

但是顯然不能直接枚舉排列，考慮枚舉 \(b\)，欽定單調順序那么方案數即為自然數的劃分，在 \(n=53\) 的條件下在 \(3\times 10^5\) 級別左右。現在問題就轉換成對于一類置換環，統計有多少個排列。

首先是一個多重集的排列，即 \(\dfrac{n!}{\prod b_i!}\)，然后對于環需要乘上圓排列即 \(\prod(b_i-1)!\)。又因為對于 \(b_i\) 相同的可能會算重，所以需要除以 \(\prod c_i!\)，\(c_i\) 表示個數。