Posted on 2007-08-07 22:31
ZelluX 閱讀(401)
評論(0) 編輯 收藏 所屬分類:
Mathematics
1. 一個有限非空集合M到自身的一個雙射稱為置換。
若M的元素個數為n，記M的所有置換的集合記作Sn，則不難得出Sn的元素個數為n個元素的排列數，即
| Sn | = n!
2. Sn的一個把i1變到i2，i2變到i3，……，ik-1變到ik，ik變到i1，而其余的元（如果還有）不變的置換稱為k階循環置換
如
(1 2 3 4 5 6) = (1) = (2) = ... = (6)，稱為恒等置換
1 2 3 4 5 6
3.幾個定理：
1) 設f，g為兩個不相交的循環置換，則fg = gf
2) 任意置換均可唯一地分解成不相交循環置換的乘積
這個定理可由構造法證得，該證法同時也給出了分解為循環置換的乘積的方法
3) 任意置換均可分解為對換的乘積（不唯一），例如
(12)(345) = (12)(35)(34) = (12)(14)(41)(35)(34)
4. 置換的奇偶性
1) 設f ∈Sn，規定f的符號為
Sgn f = ∏[ f(i) - f(j) ] / (i - j)
貌似就是逆序對數的奇偶性，奇為-1，偶為1
2) Sgn(fg) = (Sgn f)(Sgn g)
3) n > 1時，Sn中奇置換與偶置換的個數相等，均為n! / 2
可通過分離一組對換積證得