（基础数学专业论文）关于有限群排序问题的一些研究.pdf

摘要 b a s i lg o r d o n 在1 9 6 0 年为了研究完备l a t i n 方首次引入可排序群 的概念，并对有限的可排序交换群进行了完全分类，随后的几十年中， 人们致力于对有限非交换群可排序性分类问题的研究，为了更好的研究 这一问题，又先后引入了r 一可排序群、对称排序、2 排序和超可排序群 等相关概念，现在对这些排序的研究已得到了许多重要结论，但对有些 问题的研究，如可排序群的排序个数，各种排序的具体构造过程等，仍 有许多工作要做。本文是在现有文献的基础上，利用群论、数论的基本 知识和组合的方法做了以下几个方面的工作：一是给出了可排序群的排 序个数的一个下界估计，并将排序个数应用在构造不同的完备l a t i n 方 中，由此得出对完全有向图的h a m i l t o n i a n 路径分解的方法，从中找出 可排序群排序个数与完全有向图不同的h a m i l t o n i a n 路径数之间的关系； 二是在对r 一排序和2 排序的研究中，因为尺一排序肯定不是2 排序，反 之亦然，我们根据二者定义的区别给出了通过r 一排序构造2 排序的一 个充分条件( 见定理3 1 2 ) ，并且以例子加以说明该条件的必要性，从 而给出了由r 一排序构造2 排序的具体方法；三是给出了通过r 一排序构 造对称排序的具体过程；四是给出了一类超可排序群。 关键词：排序个数；对称排序：2 排序；超可排序群 a b s t r a e t i no r d e rt os t u d yl a t i ns q u a r e ，b a s i lg o r d o ni n t r o d u c e dt h ec o n c e p to fs e q u e n c i n g g r o u pf o r t h ef i r s tt i m ei n19 6 0 ，a n dc o m p l e t e dt h ec l a s s i f i c a t i o no ff i n i t es e q u e n c e a b l e a b e l i a ng r o u p s t h en e x tf e wd e c a d e s ，p e o p l ed e v o t e dt os t u d y i n gt h ec l a s s i f i c a t i o no f f i n i t es e q u e n c e a b l en o n a b e l i a ng r o u p s i no r d e rt os t u d yt h ei s s u eb e r e r o t h e rr e l a t e d c o n c e p t s ，s u c ha sr s e q u e n c e a b l eg r o u p ，s y m m e t r i cs e q u e n c i n g ，2 s e q u e n c i n ga n ds u p e r s e q u e n c e a b l eg r o u p ，w e r ei n t r o d u c e do n eb yo n e t h e s ea r ean u m b e ro fi m p o r t a n t c o n c l u s i o n sa b o u tt h es t u d yo ft h e s es e q u e n c i n g s b u tt h e r ei ss t i l lm u c hw o r kt od oa b o u t s o m eo ft h er e s e a r c h ，s u c ha st h en u m b e ro fs e q u e n c i n g so fs e q u e n c e a b l eg r o u p ，t h e s p e c i f i cs t r u c t u r eo fv a r i o u ss e q u e n c i n g s ，a n ds oo n u s i n gt h eb a s i ck n o w l e d g ea n dt h e m e t h o d so fg r o u pt h e o r ya n dn u m e r i c a lt h e o r ya n dc o m b i n a t o r i c s ，w ew o r ko nt h eb a s i s o ft h ee x i s t i n gl i t e r a t u r ea sf o l l o w ：f i r s t l y ，w eg i v ean u m b e ro fl o w e rb o u n de s t i m a t eo f s e q u e n c i n g so fs e q u e n c e a b l eg r o u p a n dw et r yt om a k eu s eo ft h e s er e s u l t st oc o n s t r u c t d i f f e r e n tc o m p l e t el a t i ns q u a r e s a n dt h e nw ec a l lf i n daf u l l yd r a w no nt h em a pt ot h e h a m i l t o n i a np a t hd e c o m p o s i t i o nm e t h o d w ec a na l s og e ts o m er e s u l t so ft h er e l a t i o n s h i p o ft h en u m b e rb e t w e e ns e q u e n c i n g so fs e q u e n c e a b l eg r o u p sa n dd i f f e r e n th a m i l t o n i a n p a t h so ft h ec o m p l e t ed i r e c t e dm a p s e c o n d l y , f o rt h es t u d yo fr s e q u e n c i n ga n d2 一 s e q u e n c i n g ，b e c a u s er s e q u e n c i n ga n d2 - s e q u e n c i n ga r ec e r t a i n l yd i f f e r e n t ，a c c o r d i n g t ot h ed e f i n i t i o no ft h ed i f f e r e n c eb e t w e e nt h et w os e q u e n c i n g s ，w eg i v eaf u l lc o n d i t i o n s w i t hw h i c hr - s e q u e n c i n gc a r lb et r a n s f o r m e dt o2 s e q u e n c i n g ( s e et h e o r e m3 1 2 ) ，a n d w ea l s oe x p l a i nt h en e c e s s i t yo ft h ec o n d i t i o nb ye x a m p l e s t h a ti s ，w eg i v et h es p e c i f i c s t r u c t u r eo ft r a n s f o r m i n gr s e q u e n c i n gt o2 - s e q u e n c i n g ；t h i r d l y , i ti sp r e s e n t e dt o c o n s t r u c ts y m m e t r i cs e q u e n c i n gt h r o u g hr - s e q u e n c i n g ；f o u r t h l y , i ti sg i v e nac l a s so f s u p e r - s e q u e n c e a b l eg r o u p k e yw o r d s ：t h en u m b e ro fs e q u e n c i n g s ；s y m m e t r i cs e q u e n c i n g ；2 s e q u e n c i n g ； s u p e rs e q u e n c a b l eg r o u p 青岛大学硕士学位论文 学位论文独创性声明 本人声明，所呈交的学位论文系本人在导师指导下独立完成的研究成果。文中 依法引用他人的成果，均已做出明确标注或得到许可。论文内容未包含法律意义上 已属于他人的任何形式的研究成果，也不包含本人已用于其他学位申请的论文或成 果。 本人如违反上述声明，愿意承担由此引发的一切责任和后果。 论文作者签名： 日期：w p 年妇芦日 学位论文知识产权权属声明 本人在导师指导下所完成的学位论文及相关的职务作品，知识产权归属学校。 学校享有以任何方式发表、复制、公开阅览、借阅以及申请专利等权利。本人离校 后发表或使用学位论文或与该论文直接相关的学术论文或成果时，署名单位仍然为 青岛大学。 本学位论文属于： 保密口，在年解密后适用于本声明。 不保密d ( 请在以上方框内打“4 ”) 论文作者签名：绷声 刷磁轹确耐 、参 ： 日期：w 3 年j 月w 日 日期：哩f 年f 月砂日 引言 引言 为了更好的研究完备l a t i n 方，1 9 6 0 年b a s i lg o r d o n 在文献1 中第一次引进了 排序和可排序群的概念，可排序群从此成为组合数学研究的热点问题之一。文献1 中b a s i lg o r d o n 将可排序的有限交换群进行了完全分类，证明了一个有限交换群是 可排序群的充分必要条件是该有限交换群可以写成两个群彳和b 的直积的形式，其 中a 是2 ( k 0 ) 阶循环群，曰是奇数阶群。这一结果后来被m a o l l i s 进一步简 化为一个有限交换群是可排序群的充分必要条件是该有限交换群是二元群。b a s i l g o r d o n 将所得的排序应用在l a t i n 方的研究中，从而证明了由可排序群的排序可以 直接构造完备l a t i n 方。 1 9 6 8 年j d 6 n e s 和e t 6 r 6 k 在文献1 中证明了8 阶四元数群q 8 、6 阶二面体 群d 6 和8 阶二面体群d 8 都是不可排序群，但1 0 阶二面体群d 1 。是可排序群，并进 一步证明了1 2 阶二面体群d 1 2 、1 4 阶二面体群q 。和1 6 阶二面体群q 6 都是可排序 群，还从理论上证明了2 l 阶非交换群( 最小奇数阶非交换群) 也是可排序群；而 m e n d e l s o h n 则在文献2 8 中给出了2 1 阶非交换群的排序的具体构造过程。由此，开 始了对有限非交换群可排序问题的研究，如a d k e e d w e l l 、l l w a n g 、b a a n d e r s o n 等分别在文献1 2 5 1 文献3 们和文献1 1 1 中对部分有限非交换群的可排序性 进行了研究。 到目前为止已知的可排序群包括： 1 ) 阶大于等于l o 的二面体群； 2 ) 可解( 包括交换) 二元群，q 除外； 3 ) 以丘为唯一非交换合成因子的不可解二元群； 4 ) 一些加阶群，其中p ，q 为奇素数； 5 ) 若p ，q 为奇素数，且p ，q 富3 ( m o d 4 ) ，则一些可排序朋阶群的直积仍是 可排序群； 6 ) 至少一个p ”阶非交换群，其中p 为奇素数hm 3 ； 青岛大学硕士学位论文 7 ) 门阶非交换群，其中1 0 疗3 2 ； 8 ) 4 和墨。 但至今没有文献对可排序群的排序个数进行研究，本文我们给出了可排序交换 群排序个数的一个下界估计，即： 若g 是玎阶可排序交换群，则存在正整数七，朋。，m ：，m ，使得g 中排序个数 至少为伊( 2 。) 伊( 所1 ) 缈( 聊2 ) 伊( 历。) 。 为了解决可排序二元群的分类问题，1 9 7 6 年引入了对称排序的概念，对称排序 是一种特殊的排序。 对二元群的分类最终由b u r n s i d e s 转移定理1 8 1 和g o r e n s t e i n w a l t e r 定理2 1 1 给 出，结果内容如下：d ( g ) 表示群g 的最大奇数阶正规子群。设h 是有s y l o w2 子群 的有限群，丁是日的一个s y l o w2 子群，如果丁是循环群，则h o ( h ) 兰t ；如果丁 是二面体群，则h o ( h ) 兰4 ( 交错群) 或日o ( h ) 同构于p f l ( 2 ，q ) ( p s l ( 2 ，q ) 的 自同构群) 的一个包含p s l ( 2 ，q ) ( 域c 上2 阶矩阵的投射特殊线性群) 的子群( 其 中g 是一个素数幂) 或日o ( h ) 兰t 。特别地，如果g 是一个可解二元群，则 g o ( g ) a ( g ) 同构于4 或墨或4 阶初等交换2 一群或循环2 - 群或二面体2 - 群( 其中 a ( g ) 表示群g 的二阶子群) 。 a n d e r s o n 和i r i g 在文献1 1 3 1 中证明了对所有可解的二元群g ，如果g d ( g ) 人( g ) 同构于4 阶初等交换2 群且g g ( 8 阶四元数群) ，则g 有对称排序。后来又从理 论上将这个结果扩大为所有有限可解二元群( q 除外) 都有对称排序。对于不可解 二元群的情况，a n d e r s o n 和i r i g 在文献1 1 4 1 中证明了寻找不可解二元群的排序的充 分条件是寻找4 ，p s l ( 2 ，g ) 和p g l ( 2 ，9 ) ( 域c 上2 阶矩阵的投射一般线性群) 的 2 排序，其中g 是一个大于3 的奇素数幂的形式。由此，引出了2 排序的概念。 排序的概念中要求部分积元素各不相同，条件比较强，所以一个新的排序被引 入r 一排序( 也称拟排序) ，r 一排序要求部分积最后一个元素是单位元，其他 部分积元素各不相同。下述类型的交换群是尺一可排序群： 1 ) 奇数n 阶循环群e ； 2 引言 2 ) s y l o w3 子群( 可以是平凡的) 是循环群的奇数阶交换群； 3 ) c ：，其中p 是素数，刀2 ： 4 ) c 2 c 4 。，其中刀 1 ； 5 ) s y l o w2 - 子群是q 形式的交换群，其中刀= 2 或刀4 ； 6 ) s y l o w2 一子群是c 2 e 。形式的交换群，其中刀是奇数； 7 ) c 2 c 6 。+ 2 ，珂l ； 8 ) s y l o w2 - 子群非循环，且不是c 2 c 2 或c 2x c 2 c 2 形式的所有交换群。 对于非交换群，有下列结果成立： 1 ) 2 7 阶二面体群d 2 。是r 一可排序群门是偶数； 2 ) 四元数群q 。是尺一可排序群刀是大于2 的偶数， 其中四元数群q 4 。定义如下： ( 2 4 。= 若n 是2 的幂，则幺。是广义四元数群； 3 ) p q 阶非交换群是尺一可排序群，其中p 、q 是奇素数； 4 ) 2 7 阶非交换群是尺一可排序群。 1 9 8 3 年k e e d w e l l 引进了超可排序群( 或称为超p 一群) 的概念，并在文献5 1 中给出了部分超可排序群的例子，对交换群而言，可排序群和尺一可排序群都是超 可排序群；对非交换群，超可排序群包括： 1 ) 2 以阶二面体群d 2 。，其中玎是不小于5 的奇数： 2 ) 2 刀阶二面体群d 2 。，其中疗是一个奇素数的2 倍； 3 ) p g 阶群，其中p 、q 是素数，p q 且2 是p 的一个原根。 b e d f o r d 在文献7 1 中又证明了两个2 7 阶非交换群是超可排序群。 我们根据r 一排序和2 排序定义的区别给出了通过r 一排序构造2 排序的一个 充分条件，即：若奇数玎阶群g 是r 一排序群，( 6 1 ，6 2 ，b o ) 是g 的一个尺一排序， 若6 j 是此r 一排序部分积序列中没有出现的元素，且6 ；= 6 j _ 1 ，则( 6 l ，6 2 ，b 州，b 。b ，) 是群g 的一个2 排序，并且以例子加以说明该条件的必要性，从而给出了由r 一排 青岛大学硕士学位论文 序构造2 排序的具体方法；同时也给出了通过r 一排序构造对称排序的具体过程， 即；若奇数刀阶群g 是尺一可排序群，群g 的一个r 一排序( 6 i ，b 2 ，以) 的部分积序 列中没有出现的元素是6 j ，且配= 6 j _ 1 ，则群g c 2 有对称排序：最后给出了一类超 可排序群g c ：( r l 为奇数) 。 4 第一章基础知识 第一章基础知识 1 1基本概念 这一节中主要是对本文涉及到的一些概念给出一些相关介绍。 定义1 1 1设g 是刀阶非平凡群，g 称为可排序群，如果g 中所有元素可以 排成一个序列 ( b l ，b 2 ，吒) 使得部分积 ( 口l ，a 2 ，口h ) 各不相同，其中口，= b i b 2 b j ，f = 1 , 2 ，n 。 此时，序列( 6 1 ，b 2 ，6 。) 称为g 的一个排序。 定义1 1 2 设g 是玎阶非平凡群，如果g 中所有元素可以排成一个序列 ( b l ，6 2 ，“) 使得部分积 ( q ，q 2 c 口川) 各不相同，且口。= e ( e 是单位元) ，其中q = b i b 2 b ，f = 1 , 2 ，刀，则g 称为r 一 排序群，又称为拟排序群。 此时，序列( b l ，b 2 ，瓯) 称为g 的一个r - - h 序。 定义1 1 3 设g 是玎阶非平凡群，如果g 中元素可以排成这样一个序列 ( p ，d ：，d 3 ，以) ( e 是单位元，序列中元素不一定互异) 满足： 其部分积e ，e d 2 ，e d 2 d 3 ，p d 2 以以各不相同； 若g g ，且g g 一，则 陋f 辄d j 备，g 一瑚= 2 ： 若g g ，且g = g ，则 l f ：1 f 刀，4 = g ) | = 1 ， s 青岛大学硕士学位论文 则称( p ，d 2 ，d 3 ，以) 为g 的一个2 一排序。 定义1 1 4 若群g 中有唯一一个二阶元，则称g 为二元群。 定义1 1 5 设g 是2 以阶二元群，z 是g 中唯一一个二阶元，若g 的一个排序 b 具有下面这种形式 b = ( p ，b 2 ，吒，z ，簖，酊。，西) 此时的排序b 称为对称排序。 【注】：因为z 是g 中唯一一个二阶元，所以，对2 f 刀，有6 f 6 1 。 定义1 1 6 设g 是玎阶有限群，如果g 的导群g 。的某一个陪集g o ( g g ) 中任意一个元素能够表示成g 中刀个元素按一定次序乘积的形式，则群g 称为p 一 群。 定义1 1 7 设g 是，z 阶有限群，如果g 的导群g 的某一个陪集g o ( g g 且 g e ) 中任意一个元素能够表示成g 中n 个元素按一定次序乘积的形式，并且在每 个乘积中g 的娌个元素相乘的次序恰好构成g 的一个排序：而当g = e 时，g 中任意 一个元素能够表示成g 中”个元素按一定次序乘积的形式，并且除单位元e 外构成 其他元素的每个乘积中g 的玎个元素相乘的次序恰好构成g 的一个排序，而构成单 位元e 的乘积中g 的刀个元素相乘的次序则构成g 的一个r 一排序。满足以上条件的 群g 称为超可排序群( 也称为超p 一群) 。 定义1 1 8 1 7 设集合x 中有n 个元素。一个n 阶l a t i n 方是一个定义在集合x 上的刀疗阵，满足x 中每个元素在该阵的每一行每- n 中只出现一次。 用l = ( 乞) 表示一个l a t i n 方，其中屯表示第i 行第j 列的元素。 定义1 1 9 四一个n 阶l a t i n 方称为行完备的，如果由集合x 中互异元素组成 的元素对 x ，y ) 的每一种顺序在相邻水平单元中只出现一次。 定义1 1 1 0 一个玎阶l a t i n 方称为列完备的，如果由集合x 中互异元素组成 的元素对 x ，y 的每一种顺序在相邻垂直单元中只出现一次。 定义1 1 1 1 若一个力阶l a t i n 方既是行完备的，又是列完备的，则该l a t i n 方 称为完备l a t i n 方。 6 第一章基础知识 定义1 1 1 2 【刀一个图的一条路径称为h a m i l t o n i a n 路，如果该路径经过图的所 有顶点且每个顶点只经过一次。 定义1 1 13 设g 是一个可排序群，( 6 l ，b 2 ，以) 和( 6 i ，6 ：，b ：) 是g 的两 个排序，若6 j = 玩( f = 1 , 2 ，疗) ，则称两个排序相同，否则，称两个排序不同。 7 青岛人学硕士学位论文 1 2基本结果 本节主要是对本文中用到的一些基本结论加以陈述和证明。 引理1 2 1 若( m ，门) = 1 ，其中m ，以为整数，则 伊( 朋) 缈( ，2 ) = 缈( 所力) 证明设聊= p 产p i 2 p ；7 ，刀= 卵g q ，则 m n = p p ；2 p 夕g f i g 留 矽( 朋) ：，刀( 1 一上) ( 1 一上) ，矽( 疗) ：以( 1 二上) ( 1 一上) p i p ， q lq k 所以伊( 聊) 驴( n ) ：聊( 1 一上) ( 1 一上) 刀( 1 一j _ ) ( 1 一上) p lp ，g ig ：聊玎( 1 一上) ( 1 一上) ( 1 一上) ( 1 一上) ：伊( 聊甩) p lp ，q lq k 例：取m = 9 9 ，刀= 4 0 ，则( m ，r ) = 1 ，且m ，以为整数。 因为m = 9 9 = 3 2 1 1 ，所以 咖却( 9 9 ) 9 9 ( 1 一尹1 一扣9 9 措- 6 0 因为玎= 4 0 = 2 3 5 ，所以 所以 p ( 刀) = 伊( 4 0 ) = 4 0 ( 1 一互1 ) ( 1 一；1 ) = 4 0 三詈= 1 6二j二) 伊( 聊) 伊( ) = 6 0 x 1 6 = 9 6 0 而m n = 9 9 4 0 = 3 9 6 0 = 2 3 3 2 5 11 ，所以 所以， 咖加伊( 3 9 6 0 ) 瑚6 0 ( 1 一扣i 一亏1 ) ( 1 一亏1 ) ( 1 一击) = 9 6 0 9 ( 历) 妒( 甩) = 口o ( m n ) 引理1 2 2 设m 。，所2 ，m ，是互异整数，则对任意正整数，存在唯一的整数 j o ，j 一一，j | 使得 8 第一章基础知识 j 兰j o ( m o d m l m 2 m ，) ，o = ，l + _ ，2 ，竹l + j 3 m l m 2 + + ，m l m 2 m 。一i ，0 s j f m ，( f = 1 , 2 ，s ) 证明 显然对任意的正整数，存在唯一的。满足 j 富j o ( r o o d m l m 2 m ，) 其中0 j o m l m 2 m 。 由带余除法中商和余数的唯一性定理可知： 存在唯一的整数。，：，使 j o = j l + j l 坍l 且0 j l m l ； 存在唯一的整数：，五，使 j ：= j ：+ ；m ： 且0 2 m 2 ； 存在唯一的整数州，使 _ ，二2 = j 一+ j , m j - l 且o j 。一l m ，一l 。 将上面一组式子中最后一个带入上一个，所得结果再带入上一个，依此类推带 入，可得 j o2 j l + 2 m l + 3 m i m 2 + + j , m l m 2 m j l 因为0 o 0 ) ，o ( g ，) = m ，聊，为奇数，且m im + i ( f = 1 , 2 ，j 1 ) ，则g 是 可排序的。 又如果令 青岛大学硕士学位论文 6 ：川2g o 。g i g j 6 2 + 2 = g i i + 1 9 ? + g ，+ 1 其中j ，一，；如引理1 2 2 所定义，则所有的6 ，组成g 的一个排序的部分积序列，而 且所定义的部分积序列是唯一的，所谓唯一性是指g 中选取不同的生成元，得到的 部分积序列不同。 证明 g = x 令 a = ， b = 则 g = a b 其中彳是2 ( 七 0 ) 阶循环群，b 是奇数阶群，由引理2 1 2 知，g 是可排序群。 令 b ：川= g i g i g ； 6 2 p ：= 酥+ 1 9 ，g ，+ 1 其中歹l 一，如引理1 2 2 所定义， 则所有的6 。组成g 的一个排序的部分积序列。 下证该序列的唯一性。 取g 的另一组生成元g ：，g l ，g ：，即 g = ， 其中d ( g ：) = 2 ，o ( 9 1 ) lo ( g l + 。) ，i = 1 , 2 ，s l ，由引理2 1 4 知 = 0 ) 阶循环群，曰是奇数阶群。因为b 是有限交换群，由文献【2 1 知： 存在g l ，9 2 ，g ，b 使得 b = x 其中o io ，i = 1 , 2 ，s l 。 不妨令 a = ，o = m ，i = 1 , 2 ，s g 中排序的部分积序列定义如引理2 1 5 所定义，则要确定引理2 1 5 所定义的g 中 部分积序列的个数，只需确定g 中生成元的组合数，而生成元的组合数为 伊( 2 ) q a ( m 1 ) 妒( ，竹2 ) 妒( 川，) 所以引理2 1 5 所定义的g 中由生成元确定的部分积序列的个数为 妒( 2 ) 妒( 肌1 ) 妒( ，”2 ) 妒( 脚。) 从而这些部分积序列确定的排序的个数为 9 ( 2 ) 矽( 脚j ) 妙( 所2 ) 妙( 聊，) 因为引理2 1 5 所定义的部分积序列不一定是群g 中所有的满足各元素互不相 同条件的部分积序列，所以，g 中排序个数至少为伊( 2 。) 缈( 脚。) 伊( 研2 ) 伊( 朋，) 。 推论2 2 。2 偶数阶循环群c 2 一中至少有纵2 刀) 个排序。 证明 设 c 2 。= a b 1 4 第二章可排序群 其中彳是2 ( k 0 ) 阶循环群，b 是奇数m 阶循环群， 不妨设a = ，b = ，则 c 2 一= x 由定理2 2 1 知，c 2 。中排序的个数至少为 妒( 2 ) 伊( m ) = 伊( 2 历) = 伊( 2 门) 。 例：以循环群c 4 为例，妒( 4 ) = 4 ( 1 一去) = 2 ，而c 4 实际上也只有2 个排序。 若设c 4 - - ，用f 表示a ，则循环群c 4 的所有排序及其部分积序列罗列如下： 排序 部分积 ( 0 ，1 ，2 ，3 ) ( o ，l ，3 ，2 ) ( o ，3 ，2 ，1 ) ( 0 ，3 ，1 ，2 ) 再以循环群c 6 为例，f p ( 6 ) = 6 ( 1 一三1 ) ( 1 一j 1 ) = 2 ，而c 6 实际上共有4 个排序。 若设c 6 = ，用f 表示口。，则循环群c 6 的所有排序及其部分积序列罗列如下： 排序 部分积 定理2 2 3 设群h 是奇数阶交换群，群k 是偶数阶交换二元群，则日k 是 可排序群。 证明由引理1 2 3 知，日k 是交换群。 又因为群k 是二元交换群，群日是奇数阶交换群，所以hxk 是二元交换群。 由引理2 1 2 知，日k 是可排序群。 ) 1 j c j ，j c _ j ， ， ， ， 4 5 1 2 ， ， ， ， 2 4 2 4 ， ， ， ， c j 1 i，1 ， ， ， ， l 2 4 5 ， ， ， ， 0 o o o，、，l，l，l、，)、，) 5 4 2 1 ， ， ， ， 2 1 5 4 ， ， ， ， ，j，j，j，j ， ， ， ， 4 5 1 2 ， ， ， ， l 2 4 c j ， ， ， ， 0 o 0 ok，kl，l 青岛大学硕士学位论文 2 3 可排序群的应用 前面我们提到可排序群是为了构造行完备l a t i n 方而引进的，下面这个引理就是 由群的排序构造完备l a t i n 方的过程。 引理2 3 1 【9 】设g 是可排序群，( 6 。b 2 b n ) 是g 的一个排序，对应的部分积序 列为( 口i 口2 a n ) ，则= ( 乃) 是一个完备l a t i n 方，其中乃= 口f 1 口，1 f ，_ ，刀。 有了甩阶行完备l a t i n 方，就可以将有甩个定点的完全有向图分解为刀条互不相 交的h a m i l t o n i a n 路( 路径互不相交是指它们没有公共边) ，而不同的排序得到的完 备l a t i n 方不同，对应的h a m i l t o n i a n 路分解也不同。 例：设g = c 。，其中运算为加法，由前一节知g 中共有4 个互异排序，它们分 别是( o ，1 ，4 ，3 ，2 ，5 ) ，( o ，2 ，5 ，3 ，1 ，4 ) ，( 0 , 4 ，1 ，3 ，5 ，2 ) 和( 0 ，5 ，2 ，3 ，4 ，1 ) 对应的部分积序列分别为 ( o ，l ，5 ，2 ，4 ，3 ) ，( 0 ，2 ，1 ，4 ，5 ，3 ) ，( o ，4 ，5 ，2 ，1 ，3 ) 和( 0 ，5 ，l ，4 ，2 ，3 ) 。 由( o ，l ，5 ，2 ，4 ，3 ) 得到的完备l a t i n 方和对有6 个顶点的完全有向图的h a m i l t o n i a n 分解如下： l 2 = ol 5o 12 45 2 3 34 52 4l o 3 3 0 l 4 25 1 6 43 32 54 2l o5 1o 第二章可排序群 由( o ，2 ，1 ，4 ，5 ，3 ) 得到的完备l a t i n 方和对有6 个顶点的完全有向图的h a m i l t o n i a n 分解如下： 厶= 0 2 4 0 51 24 13 3 5 l4 5 2 o 3 3 0 2 5 41 5 3 3l 42 l5 0 4 2 o 1 7 青岛大学硕士学位论文 f l j ( o ，4 ，5 ，2 ，l ，3 ) 得到的完备l a t i n 方和对有6 个顶点的完全有向图的h a m i l t o n i a n 分解如下： 岛= o4 2 o l5 42 53 31 5 2 14 o 3 3 0 41 2 5 13 3 5 2 4 5l 0 2 40 1 8 第二章可排序群 由( o ，5 ，1 ，4 ，2 ，3 ) 得到的完备l a t i n 方和对有6 个顶点的完全有向图的h a m i l t o n i a n 分解如下： l l = o 5 10 5 4 21 43 3 2 l4 25 0 3 3 o 52 4l 2 3 3 4 l2 45 o1 5 0 1 9 青岛大学硕士学位论文 第三章2 一排序、对称排序及超可排序群 3 12 一排序 引理3 1 1群g 的一个排序也是群g 的一个2 排序。 f f - n 设( 6 ，b 2 ，吃) 是g 的一个排序，则由排序的定义可知，其部分积 a 3 。b , b 2 b 3 a 。= b i b 2 b 3 吒 各不相i 司。 又因为排序是群g 中所有元素无重复的一个排列，所以 若g g ，且g g 一，则 i p ：2 f y i , b ，舀，g 一强= 2 ， 若g g ，且g = g 一，则 i 矗：1 f 力，饥= g ) l = l ， 满足2 排序的条件，所以，( 6 。，6 2 ，丸) 是g 的一个2 排序。 定理3 1 。2 设奇数n 阶群g 是足一排序群，( 岛，b 2 ，以) 是g 的一个足一排序， 若匆是此r 一排序部分积序列中没有出现的元素，且砰= 6 1 ，贝j j ( b ，b ：，巩，以色) 是群g 的一个2 排序。 证明设尺一排序( 岛，6 2 ，以) 的部分积序列为( 口l ，口：，口。) ，则 q 2e 序歹l j ( b 。，6 2 ，九- l b b ，) 的部分积为 第三章2 排序、对称排序及超可排序群 a l2a l2b l a ；= a 3 = b t b 2 b 3 口：一l = a n l = b i b 2 巩一l a ：= b i b 2 良一l b 。b j = a n b , = 6 j 由题设及r 一排序的定义可知序列( 6 i ，6 ：，b n _ l , 以6 j ) 的部分积序列 a ：，a ：，a ： 各不相同。 因为群g 为奇数阶群，所以g 中没有二阶元。 又因为 b b f e 由尺一排序的定义知单位元在序列( 6 l ，如，吒，b 。b 。) 中只出现一次。 k e b 2 ，b j ，“一。中，除酊1 外，其余元素及其逆元在序列( 岛，6 ：，b n _ l , b 。以) 中出现且仅出现一次。 又因为 6 2 = 酊 所以 以岛= 簖1 即k 1 在序列( 6 。，6 ：，以小b 。岛) 中出现两次， 但巩在序n ( b 。，6 ：，九，九色) 中没有出现， 换言之，及其逆元在序列( 6 ，6 ：，巩巾以6 ，) 中出现的次数和为两次， 所以，序列( 6 l ，6 ：，b 川，b 。b ，) 中非二阶元及其逆元出现的次数和都为两次，即序列 青岛火学硕十学位论文 ( 6 l ，6 2 ，b 川，b 。b ，) 是群g 的一个2 一排序。 分析：我们以循环群c 5 为例。 设循环群g = ，我们以f 来表示a ，则循环群g 中的所有r 一排序及其部 分积序列如下： ( 0 ，l ，2 ，4 ，3 )( o ，l ，3 ，2 ，0 ) ( o ，l ，3 ，4 ，2 )( 0 ，l ，4 ，3 ，0 ) ( 0 ，2 ，l ，3 ，4 )( 0 ，2 ，3 ，l ，0 ) ( 0 ，2 ，4 ，3 ，1 )( 0 ，2 ，l ，4 ，0 ) ( 0 ，3 ，l ，2 ，4 ) ( 0 ，3 ，4 ，1 ，o ) ( 0 ，3 ，4 ，2 ，1 )( o ，3 ，2 ，4 ，0 ) ( o ，4 ，2 ，l ，3 )( 0 ，4 ，l ，2 ，o ) ( 0 ，4 ，3 ，l ，2 )( 0 ，4 ，2 ，3 ，0 ) 循环群e 中的所有2 排序及其部分积序列如下： ( o ，1 ，2 ，4 ，2 )( 0 ，l ，3 ，2 ，4 ) ( o ，2 ，4 ，3 ，4 )( 0 ，2 ，1 ，4 ，3 ) ( 0 ，3 ，l ，2 ，1 )( 0 ，3 ，4 ，1 ，2 ) ( 0 ，4 ，3 ，l ，3 )( 0 ，4 ，2 ，3 ，1 ) 我们先来分析以下r 一排序： 尺一排序( o ，l ，2 ，4 ，3 ) 的部分积序列为( 0 ，l ，3 ，2 ，0 ) ，部分积序列中 没有出现的元素是4 ，如果要使部分积序列为( o ，1 ，3 ，2 ，4 ) ，则足一排序( 0 ，l ， 2 ，4 ，3 ) 的最后一个元素需要换成2 ，即要将该r 一排序变成( 0 ，l ，2 ，4 ，2 ) ， 这显然是一个2 排序； r 一排序( o ，2 ，4 ，3 ，1 ) 的部分积序列为( o ，2 ，1 ，4 ，0 ) ，部分积序列中 没有出现的元素是3 ，如果要使部分积序列为( 0 ，2 ，l ，4 ，3 ) ，则r 一排序( 0 ，2 ， 4 ，3 ，1 ) 的最后一个元素需要换成4 ，即要将该尺一排序变成( o ，2 ，4 ，3 ，4 ) ， 这显然是一个2 排序； 尺一排序( o 。3 ，1 ，2 ，4 ) 的部分积序列为( 0 ，3 ，4 ，l ，0 ) ，部分积序列中 没有出现的元素是2 ，如果要使部分积序列为( 0 ，3 ，4 ，l ，2 ) ，则足一排序( o ，3 ， 第三章2 排序、对称排序及超可排序群 l ，2 ，4 ) 的最后一个元素需要换成1 ，即要将该月一排序变成( 0 ，3 ，l ，2 ，1 ) ， 这显然是一个2 排序； 尺一排序( o ，4 ，3 ，1 ，2 ) 的部分积序列为( o ，4 ，2 ，3 ，0 ) ，部分积序列中 没有出现的元素是l ，如果要使部分积序列为( 0 ，4 ，2 ，3 ，1 ) ，则尺一排序( 0 ，4 ， 3 ，1 ，2 ) 的最后一个元素需要换成3 ，即要将该r 一排序变成( o ，4 ，3 ，1 ，3 ) ， 这显然是一个2 排序。 观察以上尺一排序可以发现，若用( 岛，吒) 表示循环群g 中的r - , 4 序，则 将满足条件6 2 = b 7 1 的r 一排序中最后一个元素钆换成岛，所得到的新序列 ( b l , 6 2 ，九小a a j ) 即是循环群c 5 的2 一排序。 反过来，我们比较循环群g 中不满足条件砰= 6 f 1 的r 一排序。 r 一排序( 0 ，l ，3 ，4 ，2 ) 的部分积序列为( 0 ，1 ，4 ，3 ，0 ) ，部分积序列中 没有出现的元素是2 ，如果要使部分积序列为( 0 ，l ，4 ，3 ，2 ) ，则尺一排序( 0 ，1 ， 3 ，4 ，2 ) 的最后一个元素需要换成4 ，即要将该足一排序变成( 0 ，l ，3 ，4 ，4 ) ， 这显然不是一个2 排序； 尺一排序( o ，2 ，1 ，3 ，4 ) 的部分积序列为( o ，2 ，3 ，l ，0 ) ，部分积序列中 没有出现的元素是4 ，如果要使部分积序列为( o ，2 ，3 ，1 ，4 ) ，则r 一排序( 0 ，2 ， 1 ，3 ，4 ) 的最后一个元素需要换成3 ，即要将该r 一排序变成( 0 ，2 ，1 ，3 ，3 ) ， 这显然不是一个2 排序； 尺一排序( 0 ，3 ，4 ，2 ，1 ) 的部分积序列为( o ，3 ，2 ，4 ，o ) ，部分积序列中 没有出现的元素是1 ，如果要使部分积序列为( o ，3 ，2 ，4 ，1 ) ，则r 一排序( o ，3 ， 4 ，2 ，1 ) 的最后一个元素需要换成2 ，即要将该尺一排序变成( o ，3 ，4 ，2 ，2 ) ， 这显然不是一个2 排序； 冗一排序( 0 ，4 ，2 ，l ，3 ) 的部分积序列为( 0 ，4 ，1 ，2 ，o ) ，部分积序列中 没有出现的元素是3 ，如果要使部分积序列为( o ，4 ，l ，2 ，3 ) ，则r 一排序( 0 ，4 ， 2 ，l ，3 ) 的最后一个元素需要换成l ，即要将该r 一排序变成( o ，4 ，2 ，l ，1 ) ， 青岛人学硕士学位论文 这显然不是一个2 一排序。 所以不满足条件砰= 6 1 的r 一排序不能换成2 排序。换言之，比较循环群g 中 的所有r 一排序和2 排序可发现，若将所有满足条件砰= b 1 的r 一排序的最后一个 元素都替换，就可得到循环群c 5 的所有2 一排序。 【注】若将定理3 1 2 中的条件酢= 6 1 去掉，则结论不成立。 以c