栗子:给一个手镯,上面有 (n) 颗珠子,由线串成环。每种珠子可能有 红、黄、绿、蓝 四种颜色。问本质不同的手镯有多少种。对于两种手镯本质相同,当且仅当一种手镯能通过旋转和翻转变换与另一种手镯重合。
抽象化对于这类问题,我们规范化定义:设集合 (A) 表示按照顺序编号手镯的每个珠子,(B) 表示四种颜色,(X:A ightarrow B) 表示每个珠子对应一种颜色。对于旋转、翻转等操作,都可以使用置换来描述。所有操作构成的置换构成 置换群(G),称为群是由于其内的元素满足群的定义和特点。显然,(X) 中某些元素可以通过 (G) 中的操作相互转化,这些元素在 (G) 下是 等价的,问题也就是 (X) 在 (G) 下的 等价类个数,记作 (|X/G|)。
由 Burnside引理
:
这里阐述记号:(|G|) 表示置换群的大小,(X^g={x|g(x)=x,xin X}),即初始状态通过 (g) 的置换不变构成的集合。
若要理解和证明该引理,需要引入 轨道稳定子定理
。
这里考查单个状态 (xin X) 受 (G) 的影响。首先,至少有 (ein G)(即啥也不做的变换),使得 (x) 在变换中保持原样。定义 (G^x={g|g(x)=x,gin G}),表示使 (x) 不改变的置换构成的集合,称 (G^x) 为 (x) 的 稳定子;与之相对,定义 (O^x={g(x)|gin G}),即 (x) 通过变换得到的所有状态构成的集合,这里 (O^x) 称之为 (x) 的 轨道。
定理的内容:
下面来证明。首先,由群论的相关知识,不难证明 (G^x) 能构成群,故由 拉格朗日定理
:
这里 ([G:G^x]) 表示 (G^x) 不同的 陪集 数目。注意陪集互不相交且大小相等,共同构成了(G)的划分。
现在我们需要证明 (|O^x|=[G:G^x])。不难发现 (|O^x|leq |G|),也就是 有可能 两种置换 (g,hin G) 满足 (g(x)=h(x)),即被对应到轨道中 同一个点,继续推导:
(gG^x) 是 (G^x) 的陪集。发现 (g(x) eq h'(x)) 得到的是 (h' otin gG^x)。这表明 轨道(O^x)上的每一个不同的点,都会被映射到不同的陪集中。这里则证明了 (O^x) 到 (G:G^x) 满足 单射。
显然 (forall gin G),(g) 必然遍布 (G^x) 的所有陪集,并且 (g(x)in O^x)。故所有陪集中,(g(x)) 一定在 (O^x) 中。这里则证明了 (O^x) 到 (G:G^x) 满足 满射。
故 (O^x ightarrow G:G^x) 满足 双射,即证 (|O^x|=[G:G^x])。
Burnside 引理的推导上述定理描述了 单个状态不动的置换数 的关系,而 Burnside引理
则描述了 单个置换下不动的状态数 的关系,我们尝试先建立联系:
由 轨道稳定子定理
:
故:
现在考虑与 (|X/G|) 建立联系。对于 (xin X/G),是某一个 等价类(的代表),其等价类大小即为 (|O^x|)(即 (x) 能通过变换得到的所有状态)。
改变枚举方式:
整理得
即证
该定理是 Burnside引理
的进一步推导。考虑化简 (|X^g|)。由于 (g) 是一种置换,在这种置换下 (x) 不变的方案数,与 置换分解出来的环的数量 有关。显然一个环中的元素必须全部相等,令 (c(g)) 表示置换 (g) 分解出来的环的数量,则 (|X^g|=|B|^{c(g)}),这里 (B) 是 (X:A ightarrow B) 的像。
所以得到