设G是[1,n]上的一个置换群,Ek是[1,n]在G的作用下包含k的等价类,Zk是k不动置换类.有|Ek||Zk|=|G|.轨道-稳定集定理定律定义 轨道-稳定集定理(Orbit-stabilizer theorem) 设G是[1,n]上的一个置换群,Ek是[1,n]在G的作用下包含k的等价类,Zk是k不动置换类.有|Ek||Zk|=|G|. 轨道-稳定集定理推导过程 证明: 设|Ek|=l,Ek={a1(=k),a2,...,al} k=a1→ai, i=1,2,...,l. P={p1,p2,...,pl} 令Gi=Zkpi,i=1,2,...,l.则k在Zkpi的作用下变为ai GiÍG(G关于Zk的陪集分解)i≠j,Gi∩Gj=Φ. G1+G2+...+Gl G. 另一方面,任意p∈G. k→aj→k PPj∈Zk, P∈ZkPj=Gj. ∴G Í G1+...+Gl. 从而,G=G1+G2+...+Gl. |G|=|G1|+|G2|+...+|Gl|=|Zkp1|+| Zkp2|+...+| Zkpl| = |Zk|·l= |Zk|·|Ek|.证毕. 轨道-稳定集定理实验验证 考虑正方形顶点二着色问题 ·|G|:置换个数 -只考虑旋转: 4 ·置换群 -Rotate 0 degree: p0=(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)(11)(12) (13)(14)(15)(16) -rotate 90 degree: p1=(1)(2 3 4 5)(6 7)(8 9 10 11)(12 13 14 15)(16) -rotate 180 degree: p2=(1)(2 4)(3 5)(6)(7)(8 10)(9 11)(12 14)(13 15)(16) -rotate 270 degree: p3=((1)(2 5 4 3)(6 7)(8 11 10 9)(12 15 14 13)(16) 不动置换类 Z1={p0, p1, p2, p3}=4 等价类:E1=1 E1 *Z1 = |G| =4 轨道-稳定集定理应用领域 组合数学 群论 轨道-稳定集定理定律影响 是burnside引理的基础