群表示一个拥有满足封闭性、满足结合律、有单位元、有逆元的二元运算的代数结构。设 GG 是一个非空集合，∗∗ 是它的一个二元运算，如果满足以下条件：
封闭性：若 a,b∈Ga,b∈G，则存在唯一的 c∈Gc∈G 使得 a∗b=ca∗b=c。
结合律：对 GG 中任意元素 a,b,ca,b,c，都有 (a∗b)∗c=a∗(b∗c)(a∗b)∗c=a∗(b∗c)。
存在单位元：存在 e∈Ge∈G，满足对于任意 a∈Ga∈G，都有 e∗a=a∗e=ae∗a=a∗e=a。
存在逆元：对于任意 a∈Ga∈G，都存在 b∈Gb∈G，使得 a∗b=b∗a=ea∗b=b∗a=e。
则称 GG 对 ∗∗ 构成一个群。
有限集合到其自身的一一映射，称为该集合上的一个置换。
对一个有六个顶点的环来说：
沿对称轴翻转后，得到的置换为：
置换的乘法就是映射叠加。置换群中的元素是置换，运算是置换的乘法，置换群是一个不满足交换律的群。
对于集合中的一个元素 xx，xG={f(x)∣f∈G}xG={f(x)∣f∈G} 称为 xx 的轨道，Gx={f∣f(x)=x,f∈G}Gx={f∣f(x)=x,f∈G} 称为 xx 的稳定化子。
轨道-稳定化子定理：对于一个置换群 GG 和一个元素 xx，有 |xG||Gx|=|G||xG||Gx|=|G|。
对于置换 ff，集合中满足 f(x)=xf(x)=x 的元素称为该置换的不动点。
设 GG 是集合 AA 上的置换群，c(f)c(f) 为置换 ff 的不动点个数，若 GG 将集合 AA 划分为 LL 个等价类，则有：
考虑证明，发现若一个元素 xx 的轨道大小为 |xG||xG|，因为置换群中一定存在逆元，所以一共有 |xG||xG| 个元素和 xx 有相同的轨道，因此得每个元素的贡献为 1|xG|1|xG|，得：
举一个例子，44 个点的环，染 22 种颜色的方案数，要考虑旋转同构。
设不考虑旋转的 1616 种染⾊⽅案为集合 AA，置换群 G={f0,f1,f2,f3}，fi 代表对环顺时针旋转 i 次，得：
考虑一个置换可以写成轮换的形式：
这样表示是一一对应的。
对于一个置换 f，设 m(f) 为其轮换个数，若要用 k 种颜色给集合 A 染色，得 c(f)=km(f)，因为是不动点，所以每个轮换的颜色要一样，进一步得：
__EOF__
联系客服
