軌道-穩定集定理

設G是[1,n]上的一個置換群，Ek是[1,n]在G的作用下包含k的等價類，Zk是k不動置換類。有|Ek||Zk|=|G|.

基本介紹

• 中文名：軌道-穩定集定理
• 外文名：Orbit-stabilizer theorem
• 表達式：|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=Z_kp_i,i=1,2,…,l.則k在Z_kp_i的作用下變為a_i

GiÍG(G關於Z_k的陪集分解)i≠j,Gi∩Gj=Φ.

G1+G2+…+GlG.

另一方面，任意p∈G. k→aj→k

PPj∈Zk, P∈ZkPj=Gj.

∴G Í G1+…+G_l.

從而，G=G1+G2+…+Gl.

|G|=|G1|+|G2|+…+|Gl|=|Z_kp₁|+| Z_kp₂|+…+| Z_kp_l|

= |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引理的基礎