Posted on 2007-08-07 22:31
ZelluX 阅读(388)
评论(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
可通过分离一组对换积证得