群
定义
定义集合 (G) 和二元运算 ( imes)，计为 ((G, imes))
满足以下性质的称为群：
- 封闭性：(forall a, b in G, a imes b in G)
- 结合率：(forall a, b, c in G, (a imes b) imes c = a imes (b imes c))
- 单位元：(exists e in G, forall a in G, a imes e = e imes a = a)
- 逆元 ：(forall a in G, exists a' in G, a imes a' = a' imes a = e)
子群
若 (H) 为 (G) 的一个子集，且 ((H, imes)) 组成一个群，那么称 (H) 为 (G) 的一个子群，计做 (H le G)。
如果 (g in G):
- (gH = g imes h, h in H), 那么称其为 (H) 在 (G) 内的关于 (g) 的左陪集。
- (Hg = h imes g, h in H), 那么称其为 (H) 在 (G) 内的关于 (g) 的右陪集。
陪集的性质 (右陪集为例) ：
- (forall g in G, |H| = |Hg|)
证明：因为逆元唯一，如果 (h1 eq h2), 而且(h1 imes g = p = h2 imes g)，那么 (h2 = p imes g' = h1)，矛盾，因此 (h1 imes g eq h2 imes g)。 - (forall g in G, g in Hg)
证明：(H) 是群，(H) 内一定存在一个单位元 (e) 满足 (e imes g = g)，因此 (e imes g in Hg Leftrightarrow g in Hg)。 - (Hg = H Leftrightarrow g in H)
证明：显然？ - (Ha = Hb Leftrightarrow a imes b^{-1} in H)
证明：由性质 (3) 可得。 - (Ha cup Hb
eq varnothing
ightarrow Ha = Hb)
证明：假设 (c in Ha, c in Hb)，(exists h1, h2) 满足 (h1 imes a = c, h2 imes b = c)，(a imes b^{-1} = h1 imes h2^{-1} in H)，用性质 (4) 可以得到。 - (H) 的全体右陪集的并为 (G)
证明：因为 (H) 存在单位元 (e), (g) 取遍 (G) 中的每个元素。
表述：
如果 (H le G) :
(H / G) 表示 (H) 的所有左陪集 ({gH | g in G})
([G:H]) 表示 (G) 中 (H) 的不同的陪集的数量。
拉格朗日定理
格朗日定理：
对于有限群 (G) 与有限群 (H) ，若 (H) 为 (G) 的子群，那么有：
(|H| ext{整除} |G|)
即 (H) 的阶整除 (G) 的阶。
更具体点：(|H| imes [G:H]=|G|)
证明： 陪集大小和为 (|G|), 陪集大小为 (H), 那么 ([G:H] = frac{|G|}{|H|})
置换群
设 (N = {1, 2, ..., n})，令 (M) 为 (N) 的一个排列(一个置换),然后定义两个置换 (A) 和 (B) 的 ( imes) 操作的结果 (C) 为 (C_i = B_{A_i}), 让集合群 (G = {M, imes})。
循环：置换 (egin{pmatrix}a_1 & a_2 & ... & a_{n - 1} & a_n\ a_2 & a_3 & ... & a_n & a_1 end{pmatrix}) 称为 (n) 阶循环。记为 (egin{pmatrix}a_1 & a_2 & ... & a_{n - 1} & a_n end{pmatrix})
将置换表示为若干循环乘积的方法：
首先在这个置换的第一行任取一个元素，比如说 (a_1) ，然后去 (a_1) 下面的元素 (sigma(a_1)) ，接着取第一行 (sigma(a1)) 下面的元素，以此类推，知道渠道第一行某一元素下面的元素为 (a_1) 时为止。如果这次是索取的元素个数小于 (n) 则从置换的第一行中去一个以前没有去过的元素重复以上操作，直到取遍第一行的所有元素为止。
任何一个置换都可以表示称若干个循环的乘积，且表示方法是唯一的。
轨道-稳定子定理
轨道
作用在 (X) 上的置换群 (G)。(X) 中的元素 (x) 的 轨道 是在群 (G) 的作用下能转移到的元素集合
稳定子
稳定子被定义为 (G^x = { g | g(x) = x, g in G })
轨道-稳定子定理
(|G^x| |G(x)| = |G|)
格朗日定理可以得出 (|G^x| [G:G^x] = |G|)
因此需证明 ([G:G^x] = |G(x)|)
如果 (f(x) = g(x)), 那么 (f(x) g(x)^{-1} = e(x) in G^x)。由于陪集的性质 (fG^x = gG^x)。
因此 (fG^x = gG^x Leftrightarrow f = g)。
于是让 (g G^x) 对应 (g) 就可以不重不漏地表示所有陪集。
Burnside 引理
群 (G) 作用在 (X) 的下的等价类个数 ((|X / G|)) 为 (frac{1}{|G|}sumlimits_{g in G} G^x)。
证明：
(|X / G| = sumlimits_{x in X} frac{1}{[G:G^x]})
而根据拉格朗日定理，(|G^x| [G:G^x] = |G|)。
(|X / G| = sumlimits_{x in X} frac{|G^x|}{|G|})
(|X / G| = frac{1}{|G|} sumlimits_{x in X} G^x)
把他反过来即可。
Pólya 定理
让 (G = {g_1, g_2, ..., g_n}) 为 (n) 个对象组成的置换群，用 (m) 种颜色染色，答案为 (frac{1}{|G|}sumlimits_{g in G} m^{c(g)})，(c(g)) 表示置换 (g) 表示成的循环个数。
为什么？让 (G) 为 ({旋转 0 个，旋转 1 个，旋转 2 个... 旋转 n - 1 个})
让 (X) 为初始所有可能的染色。
所以答案就是 (frac{1}{|G|} sumlimits_{x in X} G^x)
考虑到旋转 (k) 个的不动点数量是 (c(k))。
所以答案就是给这些不动点染色的方案，即 (frac{1}{|G|}sumlimits_{g in G} m^{c(g)})