循环置换分解定理的一个证明及其应用

陈健夫

(广州大学数学与信息科学学院，广州510006)

循环置换分解定理的一个证明及其应用

陈健夫

(广州大学数学与信息科学学院，广州510006)

[摘要]循环置换分解定理：每一个n元置换π都可以写成若干个不相连的循环置换的乘积，是置换群理论最基本的定理之一.在一些教材中该定理的证明用了数学归纳法，本文提供了一个直观的证明方法，并给出了置换的一种表示方法以及一道关于穿珠子的排列组合问题的解法.

[关键词]置换； 循环置换分解； 置换群

1引言

2预备知识

定义1有限集的一个一一变换叫做一个置换.

定义2一个有限集的一个把ai1变到ai2，ai2变到ai3，…，aik变到ai1，而且其他元素不变的置换，叫做一个k-循环置换.用符号(i1i2…ik)或(i2i3…iki1)…或(ikik-1…i1)表示.

定义3π=(i1i2…im)和τ=(j1j2…jn)是两个循环置换，如果π和τ不含相同的文字，则称π和τ不相连.

定理1如果有两个置换

那么

定理2n次对称群Sn的阶是n!.

3循环置换分解定理的证明及置换的一种表示方法

在有n个元素的有限集中，对于任意一个置换π，暂时不考虑集中在π下不变的所有元素，现在在其他的有变动的元素中任选一个记为a11，把其在π下的像记为a12；然后把a12的像记为a13，重复这个操作，必然存在正整数k，使得a1k的像是a11…a1k-1中的一个，这是显然的，假设不然，那么会找到无穷个不同的元素，则这个不是有限集，矛盾.还要进一步说明，这个a1k的像就是a11，否则，假如a1k的像是a1p(1

由于该有限集中其他元素都是在π下不变的，那么现在可以得到π的表示了：

根据定理1，容易得出

（3）投喂饲料。春季4、5月份要多投喂一些动物性饲料，如小鱼或轧碎的螺蛳等，一方面是此时对小龙虾要增加营养，以利于抱卵繁殖虾苗，另一方面是有利于河蟹蜕壳生长。夏季6-8月份高温季节以投喂植物性饲料为主，防止中华绒螯蟹摄入过多的营养而提前进入性成熟期导致死亡。9月份的后期要多投喂一些动物性饲料，让中华绒螯蟹积累脂肪，这不仅是让中华绒螯蟹增重，还可使其增重后在食用时其口味更好。这就是中华绒螯蟹养殖中俗话说的掌握“两头精、中间青”的原则。

π=(1112… 1k)(2122… 2k′) … (m1m2… mp)，

以上已经说明了这些循环置换的文字互不重复.于是任意一个置换都可以表达成若干个不相连的循环置换的乘积.

关于这个定理还要说明一点，这个分解是唯一的，这个在证明步骤中就可以看出.我们看找出来的第一个局部循环置换，即使首先取的元素不是a11而是另一个a1r，那么最终得到的局部循环是

(1r1r+1… 1k11… 1r-1) ，

这是等于(1112… 1k)的.对于其他的局部循环也一样.所以这个分解是唯一的.

这个证明是通过有限次操作把局部的循环置换一个一个找出来，然后再合并到一起.与数学归纳法相比，这种方法更加直观，更有利于读者对置换的分解产生更深刻的认识和理解.

下面给出置换的一种表示法.常用箭头来表示一个映射，比如π:a→b，表示a在法则π下变为b.现在同样使用箭头，只是定义其为一个弯箭头，现在不妨用元素和弯箭头去表示一个置换，其中这些元素只需写一次(如果在括号用二行的文字表示置换，所有元素都书写了2次)，例如对于3个元素的有限集A的一个置换：

φ:a1→a2;a2→a3;a3→a1，

用新定义的表示方法来表示则如图1.箭头的尾部连接的元素表示π在A上作用的元素，箭头头部的元素表示像.那么当然有以下重要的规定，由于置换是一一映射，那么用这种表示方法时，所有元素都必须同时在且仅在一个箭头的尾部和一个箭头的头部.如果一个元素不在一个箭头的尾部或者一个箭头的头部，前者表明这个根本不是映射，后者表明该元素没有被作用，即不成为一个像，那么不是满射；如果一个元素同时在两个或以上的箭头的尾部或者箭头的头部，前者表明这个根本不是良性映射，后者表明该元素是多个元素的像，不是单射.有了这些规定后，就可以把一个局部的循环置换的元素排成一个环状来表示，比如上面的3元置换π.那么现在可以用这种新定义的方法来表示

了，如图2.并且一个有限集的所有置换都可以表示成这种形式，可以发现，这是由若干个封闭的圆环构成，每个圆环表示一个局部的循环置换，所有元素都穿过且仅穿过一个圆环，这是比较有趣的，而且十分形象，直观.事实上，在一般的情况下，并不必要这样来表示一个置换，但是用这种表示方法可以有助于解决下面要讨论的穿珠子问题.

图1

图2

4应用

对于n个可辨的珠子，要求用线把这些珠子穿成若干个环，而且每个珠子只能被一条线穿过，我们还规定，不同的穿珠顺序是不同的穿法，例如

a1→a2→a3→a4→a1和a1→a3→a2→a4→a1

图3

是不同的穿法，当然，对于1个珠子成环和2个珠子成环都是只有一种顺序.我们问总共有多少种穿珠的办法.

[参考文献]

[1]张禾瑞.近世代数基础[M].北京：高等教育出版社，1978，54-55.

AProoftoCirculantPermutationDecompositionTheoremanditsApplication

CHEN Jian-Fu

(SchoolofMathematicsandInformatics,GuangZhouUniversity,Guangzhou510006,China)

Abstract:Circulantpermutationdecompositiontheorem:everypermutationπcanbedenotedbytheproductofseveraldisconnectedcirculantpermutation,whichisoneofthemostfundamentaltheoremingroupstheory.Insometexts,thistheoremisprovedwithmathematicalinduction.Whilethisarticleprovidesavisualizedproofandanewmethodtodenoteapermutation,whichcanbeusedtosolveacombinatorialproblemaboutstringingbeads.

Keywords:permutation;circulantpermutationdecomposition;permutationgroup

[中图分类号]O152；O157

[文献标识码]A

[文章编号]1672-1454(2015)04-0095-04