（运筹学与控制论专业论文）组型为gt的34可分组设计.pdf

北京交通大学硕士学位论文中文摘要 中文摘要 可分组设计是组合设计理论中一个基本而重要的研究课题设 ，a 为正整数 且灭，朋为给定的正整数集一个三元组( 形，够，) ，其中形为一个 ，元集，够构 成影的一个划分的元素叫做区组，够的元素叫做组若满足： ( i ) 对任意b ，都有i b i 7 1 ； ( i i ) 对任意g 够，都有l g i 朋； ( i i i ) 对任意b 与任意g 箩，都有旧ng i l ； ( i v ) z 中任意一对属于不同组的元素恰好包含在a 个区组中， 则称( 彤，够，) 为一个可分组设计，记作g d ( k ，a ，a 4 ；v ) 若必= 艮：，恐， ，则 表示可分组设计中至少存在一个长为七l 的区组本文主要讨论组型为g f 的 3 ，4 卜 g d d 存在性问题全文共分四个章节： 第一章介绍有关区组设计的基本概念和定理 第二章通过给出构造方法并引用已知的结果，解决1 3 ，4 - p b d 的存在性问 题，即1 3 ，4 + 一p b d 存在的充分必要条件为1 ，三0 ，1 ( r o o d3 ) ， ，4 且 ，6 ，7 ，9 第三章研究组型为的 3 ，4 g d d ，给出一系列的构造方法和结果，基本 解决了其存在性问题，即组型为矿的 3 ，4 - g d d 存在的必要条件也是充分的，除 去( g ，t ) ( 1 ，6 ) ，( 1 ，7 ) ，( 1 ，9 ) ，( 2 ，4 ) j 不存在，以及可能的t = 6 且g 三1 ，5 ( m o d 6 ) 第四章结论以及对一些问题的探讨 关键词：p b d ；g d d ；t d 分类号： 0 1 5 7 2 北京交通大学硕士学位论文 a b s t r a c t a b s t r k 弋 c o m b i n a t o r i a ld e s i g nt h e o r yi sa ni m p o r t a n tb r a n c ho fm o d e mc o m b i n a t o r i a lt h e o r y t h er e s e a r c ho fd e s i g nr e f e r st oav e r yi m p o r t a n ta n dc e n t r a lp r o b l e mo fc o m b i n a - t o r i a lt h e o r y l e t 必a n d 莎b es e t so fp o s i t i v ei n t e g e r sa n dl e t lb eap o s i t i v ei n t e g e r a g r o u pd i v i s i b l ed e s i g no fi n d e xaa n do r d e r ，( ( 臂，, t ) - g d d ) i sat r i p l e ( 杉够，幼， w h e r e i saf i n i t es e to fc a r d i n a l i t y gi sap a r t i t i o no f i n t o p a r t s ( g r o u p s ) w h o s e s i z e sl i ei ng ，a n d 国i saf a m i l yo fs u b s e t s ( b l o c k s ) o f t h a ts a t i s f y ： ( 1 ) i f b 历t h e ni b i 必， ( 2 ) l b n g lslf o r a n y b 留，g 够， ( 3 ) e v e r yp a i ro fd i s t i n c te l e m e n t so f 少o c c u f si ne x a c t l yab l o c k so ro n eg r o u p ，b u t r i o tb o t h i f q f = 群，乜， ，w em e a nt h a tt h e r ei sa tl e a s to n eb l o c ko f k ll e n g t hi n 留 i nt h i sa r t i c l e ，w ei n v e s t i g a t e dt h ee x i s t e n c ep r o b l e mo f1 3 ，4 。j - g d do ft y p e t h i st h e s i si so r g a n i z e da sf o l l o w s i nc h a p t e rl ，s o m eb a s i cc o n c e p t i o n sa n dt h e o r e m sa r ei n t r o d u c e d i nc h a p t e r2 ，t h ee x i s t e n c eo f1 3 ，4 - p b di sd i s c u s s e d w ep r o v et h a tt h e r ee x - i s t s1 3 ，4 一p b di f a n do n l yi f ，兰0 ，l ( r o o d3 ) ，4a n d1 ，6 ，7 ，9 i nc h a p t e r3 ，w ef o c u so i lt h ee x i s t e n c eo f 3 ，4 j - o d do ft y p e 矿t h e r ee x i s t s 1 3 ，4 - g d do f t y p e 矿i f9 2 “f 1 ) 兰0 ( m o d6 ) ，t 4a n dt = 6w h e ng i ，5 ( r o o d6 ) w i t ht h ee x c e p t i o no f ( g ，磅i ( 1 ，6 ) ，( 1 ，7 ) ，( 1 ，9 ) ，( 2 ，4 ) i nc h a p t e r4 ，t h ec o n c l u s i o na n ds o l l l ep r o b l e m sa b o u tt = 6a n dg 三l ，5 ( r o o d6 ) o f 3 ，4 - g d do ft y p e 矿a r eg i v e n k e y w o r d s ：p b d ；g d d ；r g d d ；t d c l a s s n o ：0 1 5 7 2 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。 特授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学 校向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：压线够 签字日期b 卯芬年6 月乓日 导师签 签字日期：力矽峰石月角 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位 或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在 论文中作了明确的说明并表示了谢意。 学位论文作者签名：荐翁艺 签字日期：加萨伽户日 致谢 本论文的工作是在我的导师常彦勋教授的悉心指导下完成的，无论是在科研 上，还是在平时的生活中，常老师都给了我无微不至的关怀与鼓励当我在课程学 习中遇到难点时，常老师总是很细, t ) q l 耐心的举出实例进行讲解；当我在科研上 遇到困惑而停滞甚至消沉时，常老师总是不厌其烦的给我提出新的建议，鼓励我 开拓思路，大胆细心常老师还教育我们要谦逊做人，并且以身作则总之，常老师严 谨的治学风格，广博的知识体系，精益求精的科研作风，敏锐的学术思想和忘我的 工作精神极大的影响并鞭策了我在论文选题、研究、定稿的过程中，常老师自始 至终给了我大力的支持和无私的关怀，在此向常老师表示衷心的感谢 在论文的写作过程中，周君灵老师也给了我很大的帮助，在此向周老师表示深 深的感谢冯驶师兄、吴艳、王小苗、王昭、林伟伟、马增花等同学对我论文中 的许多研究工作给予了热情帮助，在此向他们表达我的感激之情 在撰写本论文时，参考了王昭同学制作的t h u t h e s i s 模板，解决了我遇到了许 多t 参r z x 的使用问题，在此表示深深的感谢 最后，感谢各位专家和学者在百忙中审阅我的论文! 北京交通大学硕士学位论文 第1 章预备知识 第1 章预备知识 组合设计理论是现代组合理论的一个重要分支，设计的研究涉及到组合论的 一个非常重要而中心的问题，即按照一定的规则来安排一些物件的问题所用的 主要数学工具是数论，线性代数和抽象代数可分组设计是组合设计理论中的一 个基本而重要的研究课题下面介绍本文用到的一些基本概念和结果 1 1 基本概念 定义1 1 设形是一个有限集，a l ，a 2 ，如是它的b 个子集称( 形，) 是 集彤上的一个区组设计，其中= a l ，a 2 ，a 6 j 诸a ( 1sf b ) 称为该设计 的区组若无混淆也称是集形上的一个区组设计 定义1 2 设( 形，) 是一个区组设计，奶c 如果对于任一元工形，x 恰 好在确的一个区组中出现，称奶是该设计的一个平行类如果可以表示为两 两不相交的若干个平行类的并，则称该设计为可分解设计 定义1 3 设 ，1 为正整数且丙为某些正整数的集一个区组设计( 万，) 若 满足： ( i ) i 彤i = y ； ( i i ) 陋l ：a c 欠； ( i i i ) 每个二元子集i x , y c 形恰好包含于a 个区组中， 则称该设计为成对平衡设计，记作b ，a ；川或者( ，必，m - p b d 例1 1 设形= l ，2 ，l o l ，= 1 1 ，2 ，3 ，4 1 ， 1 ，5 ，6 ，7 1 ， 1 ，8 ，9 ，1 0 ， 2 ，5 ，8 1 ， 1 2 ，6 ，9 j ，1 2 ，7 ，1 0 ， 3 ，5 ，1 0 ， 3 ，6 ，8 j ，1 3 ，7 ，9 l ， 4 ，5 ，9 j ， 4 ，6 ，1 0 1 ，1 4 ，7 ，8 1 1 ，则( 。形，) 为 一个f 3 ，4 卜p b d 定义1 4 一个( v ，a ) p b d 称为一个平衡不完全区组设计，记作b k ，a ；v 】或 者( v ，k ，a ) b i b d 一个( 1 ，, 0 - p b d 如果是可分解设计，则称为可分解平衡不完 全区组设计，记作尺b 限，a ；v 】或者( y ，k ，a ) r b i b d 定义1 5 一个三元组( 彤，箩，) ，其中为一个v 元集，够构成形的一个 划分的元素叫做区组，够的元素叫做组若满足： ( i ) 对任意b ，都有吲b 灭； ( i i ) 对任意g 箩，都有i g i 朋； j 室窒塑盔堂亟堂焦堡塞 第l 章预备知识 ( i i i ) 对任意b 与任意g 鳆都有i br 3 g i51 ； ( i v ) 旷中任意一对属于不同组的元素恰好包含在a 个区组中， 则称( 影，汐，) 为一个可分组设计，记作g d ( 必，a ，m ；v ) 。 当灭= 纠，朋= i m j 时，g d ( 科，无 纠；d 简记作g d ( k ，l ，m ；d 定义1 6 设( 彤，汐，) 是一个g d ( q ( ，a ，朋；d 若够包含矗个大小为m f 的 组，l i s ，且 ，= h m j ，则称( 影，够，) 是一个型为一1 m ；，l ? 的g d 设计 i = i 定义1 7 若灭= 懈，乜，j ，则表示该设计中至少存在一个长度为k i 的区组 例1 2 设影= 1 1 ，2 ，3 ，4 ，5 ，6 ，7 ，8 ，9 ，1 0 ，1 1 ，1 2 ，1 3 ，1 4 ，1 5 ，c o l ，0 0 2 ，3 l 够： 1 ，2 ，3 i ，1 4 ，5 ，6 ， 7 ，8 ，9 l ，1 1 0 ，l l ，1 2 ， 1 3 ，1 4 ，1 5 1 ，l , x , 1 ，c 0 2 ，0 0 3 ； ：l o o i ，l ，4 ，8 ，i o o i ，2 ，5 ，9 ) ，1 0 0 1 ，3 ，1 0 ，1 4 ， o o l ，7 ，1 2 ，1 3 ， 0 0 1 ，6 ，1l ，1 5 1 ， 2 ，1 ，1 2 ，1 5 1 ， 0 0 2 ，2 ，i i ，1 3 1 ，1 0 0 2 ，3 ，6 ，7 j ， 0 0 2 ，4 ，9 ，1 4 1 ， 0 0 2 ，5 ，8 ，1 0 1 ， 0 0 3 ，l ，5 ，1 3 1 ， 0 0 3 ，2 ，6 ，1 4 ，1 0 0 3 ，3 ，8 ，1 2 ， 3 ，4 ，7 ，1 1j ， 0 0 3 ，9 ，1 0 ，1 5 1 ， l ，9 ，1 1 ， 2 ，7 ，1 0 1 ，1 3 ，4 ，1 5 1 ，1 6 ，8 ，1 3 1 ， 5 ，1 2 ，1 4 1 ， 1 ，6 ，1 0 1 ， 2 ，4 ，1 2 1 ，1 3 ，9 ，1 3 l ，1 8 ，1 l ，1 4 1 ， 5 ，7 ，1 5 1 ， 1 ，7 ，1 4 1 ， 2 ，8 ，1 5 ，1 3 ，5 ，l l l ， 4 ，1 0 ，1 3 1 ，1 6 ，9 ，1 2 1 ， 可以验证此( ，够，) 是一个组型为3 6 的 3 ，4 卜g d d 定义1 8 若一个g d 设计的全部区组可划分成平行类，则称其为可分解的可 分解的g d ( q ( ，无朋；1 ，) 记作r g d ( 必，屯朋；v ) 例1 3 令形= a o ，a l ，a 2 ，a 3 ，b o ，b l ，b 2 ，b 3 ，c o ，f l ，c 2 ，c 3 ， 够：i a o ，a l ，a 2 ，a 3 ) ，l b o ，b l ，b 2 ，b 3 l ，i c o ，c l ，c 2 ，c 3 ) ：i a o ，b o ，c o ) ， a l ，b l ，c l ， a 2 ，b 2 ，c 2 j ， a 3 ，b 3 ，c 3 j ； 伽，b l ，q j ， a l ，b 0 ，c 3 ) ，l a 2 ，b 3 ，c o ， 0 3 ，b 2 ，c lj ； 口o ，b 2 ，c 3 1 ， a t ，b 3 ，c 2 1 ，l a 2 ，b o ，c l ，l a 3 ，b t ，c o l ； 口o ，b 3 ，c l ，i a l ，b 2 ，c b j ，l a 2 ，b l ，c 3 ) ， a 3 ，b o ，c 2 ) ， 则得到一个组型为4 3 的r g d ( 3 ，l ，4 ；1 2 ) ，它共有4 个平行类 可分组设计与成对平衡设计之间有着密切的联系若将一个g d ( q ( ，a ，朋；，) 设 计中的组也看作区组，并把每一个组重复五次，则得到一个成对平衡设计取必u 朋，a ； ，) ，它有，t 个平行类反之，设( 形，) 是一个口，a ；v l ，若将形的每一个 元素看作一个组，即令够= i x j ：工万j ，则( 彤，够，) 便是一个g d ( o v ，a ， l l ； ，) 例1 4 设= 1 1 ，2 ，1 2 1 ， 够： 1 ，2 ，3 ，1 4 ，5 ，6 ) ， 7 ，8 ，9 ， l o ，1 1 ，1 2 1 2 北京交通大学硕士学位论文第1 章预备知识 ： 1 ，4 ，7 ，1 0 ) ， 1 ，5 ，8 ，1 1 ，1 1 ，6 ，9 ，1 2 ； 1 2 ，4 ，8 ，1 2 1 ， 2 ，5 ，9 ，1 0 ) ， 2 ，6 ，7 ，1 1j ； 1 3 ，4 ，9 ，1 1 1 ， 3 ，5 ，7 ，1 2 ，1 3 ，6 ，8 ，1 0 1 ； 则( 形，箩，) 为一个组型为3 4 的g d ( 4 ，l ，3 ；1 2 ) 在箩的各组中添加一个新的 点o o ，则得到一个b ( 4 ，l ；1 3 ) 定义1 9 当 ，= k m 时的g d ( k ，a ，l ；1 ，) 叫做l 重横截设计，简称t d 设计，记 作t d ( k ，a ；哟可分解的t d ( k ，a ；m ) 记作r t d ( k ，i ；m ) 1 2 相关定理及结论 下面我们主要给出与p b d 设计和g d 设计的存在性相关的定理及结论 引理1 1 【1 3 j 若召( 咒a ；1 ，) 存在，则 ( d a ( v 一1 ) 兰0 ( 朋旧d 口( 必) ) ， ( 2 ) l v ( v 1 ) 三0 ( m o d f l ( o v ) ) ， 其中口( 丙) = g c d l k i l k 欠j ，夕( 必) = g c d k ( k 一1 ) l k 丙j 下面讨论g d 设计存在的必要条件，这些结果足解决本文主要问题的基础 引理1 21 1 3 若g d ( k ，a ，m ；，) 存在，则 ( 1 ) 从v n 1 ) 暑0 ( m o d ( k 1 ) ) ， ( 2 ) a v ( v 一，咒) 三0 ( m o d k ( k 一1 ) ) ， ( 3 ) v 三o ( m o d m ) ， ，艺k m 当k = 3 以及k = 4 时，g d 设计的存在性问题已经完全解决 引理1 3 t q k = 3 时，g d ( 3 ，a ，r e ；v ) 存在的必要条件也是充分的，即令g 与t 为 正整数，g o ( 3 ，l ，g ；g t ) 存在的充分必要条件是： g t 充要条件 1 ，5 ( r o o d 6 )1 ，3 ( r o o d 6 ) t 芝3 2 ，4 ( r o o d 6 )0 ，1 ( m o d3 ) t 3 3 ( r o o d6 ) 1 ( r o o d 2 )t 3 0 ( r o o d 6 】 无限制t 3 引理1 41 2 1 当k = 4 时，除去g d ( 4 ，l ，2 ；8 ) 与6 9 ( 4 ，l ，6 ；2 4 ) 这两个设计不存 在之外，g d ( 4 ，允，l ； ，) 存在的必要条件也是充分的，即令g 与t 为正整数， g d ( 4 ，l ，g ；g t ) 存在的充分必要条件是： 3 北京交通大学硕士学位论文第1 章预备知识 g t 充要条件 1 ，5 ( m o d 6 )1 ，4 ( r o o d1 2 ) t 4 2 ，4 ( r o o d 6 ) 1 ( m o d3 )t 4 ，( g ，t ) ( 2 ，4 ) 3 ( r o o d 6 )0 ，1 ( m o d4 ) t 4 0 ( r o o d 6 ) 无限制 t 4 ，( g ，t ) ( 6 ，4 ) 4 北京交通大学硕士学位论文 第2 章1 3 ，4 + 卜p b d 的存在性 第2 章 3 ，4 母卜p b d f l 3 存在性 本章完全解决了 3 ，4 - p b d 的存在性问题 2 1 必要条件 引理2 1 1 3 ，4 。 一p b d 存在的必要条件是：v 三0 ，1 ( r o o d3 ) ，v 4 证明：由引理1 1 可推得上述条件 2 2 充分条件 引理2 2v 三l ，4 ( r o o d1 2 ) 且v 4 时， 3 ，4 + 卜p b d 存在 口 证明： 由引理1 4 ，当g 三1 ( m o d6 ) ，t 三l ，4 ( m o d l 2 ) 且t 4 时，g d ( 4 ，1 ，g ；g t ) 存 在，即b ( 4 ，1 ；g t ) 存在所以当v 三l ，4 ( m o d l 2 ) 且v 4 时，1 3 ，4 卜p b d 存在口 引理2 3l ，兰0 ，3 ( m o d l 2 ) 且 ，1 2 时，1 3 ，4 + p b d 存在 证明：先引入一种构造法，即通过去掉b ( 4 ，l ；v ) 中的某一点，若通过这点的区 组个数b 7 = ( ，一1 ) 3 小于b ( 4 ，l ； ，) 中的区组个数b = v ( v 一1 ) 1 2 ，则得到一 个 3 ，4 一p b d 由此，当 ，兰1 ，4 ( m o a l 2 ) 且y 4 时，去掉b ( 4 ，1 ；，) 中的某一点，因为b b ： v 4 ，v 4 时有b ，所以可以得到所需的1 3 ，4 - p b d ，其中 ，三o ，3 ( m o d l 2 ) 且 ， 1 2 口 对于 ，三6 ，7 ，9 ，1 0 ( r o o d l 2 ) 的情况，我们需要先引入一个d l k r e h e r 和d r s t i n s o n 的引理 引理2 4 【4 】设g 和4 为正整数，组型为l 9 1 和3 9 1 的4 - g d d 存在，当且仅当以下 条件成立： g u 组型充要条件 1 ，7 ( m o d l 2 ) 0 ，3 ( m o d l 2 ) l g l u 2 t + 1 4 ，l o ( m o d l 2 ) 0 ，9 ( m o d l 2 )l 9 1 u 2 t + l 0 ，6 ( m o d l 2 ) 0 ，l ( m o d 4 )3 9 14 ( 2 t + 3 ) 3 3 ，9 ( m o d l 2 ) 0 ，3 ( r o o d 4 ) 3 g l “( 2 t + 3 ) 3 5 北京交通大学硕士学位论文 第2 章1 3 ，4 + i - p b d 的存在性 引理2 5 ，三7 ，1 0 ( m o d l 2 ) 且y 2 2 时， 3 ，4 + p b d 存在 证明： 由引理2 4 ，当组型为l 9 1 时，取g = 7 且“三0 ( m o d l 2 ) ，“1 5 时，4 g d d 存在此时将7 长的组看作区组并拆开用3 长的区组来代替，可以得到一 个1 3 ，4 卜p b d ，其中1 ，兰7 ( m o d l 2 ) 且y 3 1 同理，若取g = 7 且u 兰3 ( m o d l 2 ) ，“芝1 5 时，可以得到，兰1 0 ( m o d l 2 ) 且y 2 2 时 3 ，4 卜p b d 存在口 引理2 6 ，兰6 ，9 ( m o d l 2 ) 且 ，3 0 时，1 3 ，4 卜p b d 存在 证明：由引理2 4 ，当组型为3 9 1 时，取g = 9 且“三0 ( r o o d 4 ) ，距之7 时，4 - g d d 存 在此时将9 长的组看作区组并拆开用3 长的区组来代替，并将3 长的组看作区 组，这样可以得到一个1 3 ，4 卜p b d ，其中，兰9 ( m o d l 2 ) 且 i p 3 3 同理，若取g = 9 且u 兰3 ( r o o d 4 ) ，h 7 时，可以得到v 兰6 ( m o d l 2 ) 且，之 3 0 时 3 ，4 j - p b d 存在 n 对于v = 6 ，7 ，9 ，1 0 ，1 8 ，1 9 ，2 1 的情况比较特殊下面我们主要解决这几个小阶 数的 3 ，4 卜p b d 存在性问题 引理2 7 ，= 6 ，7 ，9 时，1 3 ，4 卜p b d 不存在 证明：1 ) 对于1 ，= 6 ，7 ，假设1 3 ，4 + 卜p b d 中4 长区组的个数为n ，3 长区组的个数 为，1 则有钿- i - 3 m = v ( v 一1 ) 2 由于九l ，所以当y = 6 时，方程钿+ 3 m = 1 5 有 两个解：n = l ，m = 3 和甩= 2 ，l = 1 下面证明这两个解都不能构造出满足要求的p b d ：设v = l a ，b ，c ，d ，e ，厂 当刀= l ，小= 3 时，不妨令l a ，b ，c ，d 为4 长的区组，则在1 1 = 1 的情况下，余下的对子不 足以构造出3 个3 长的区组而当刀= 2 ，m = l 时，令 a ，b ，c ，d j 为第一个4 长的 区组后，可以发现在a = 1 的情况下，从余下的对子中构造不出第二个4 长的区 组所以y = 6 时 3 ，4 。卜p b d 不存在 当v = 7 时，方程6 n + 3 m = 2 1 有三个解：n = 1 ，m = 5 ，刀= 2 ，m = 3 和以= 3 ，m = 1 同理可证得该阶数的( 3 ，4 l - p b d 不存在 2 ) 对于，= 9 ，假设 3 ，4 - p b d 中4 长区组的个数为刀，3 长区组的个数为肌则 有6 胛+ 3 m = v ( v 一1 ) 2 = 3 6 由于以1 ，所以方程6 力+ 3 m = 3 6 有解刀= l ，m = 1 0 ；，l = 2 ，m = 8 ；，l = 3 ，咒= 6 ；以= 4 ，n = 4 ；n = 5 ，m = 2 和行= 6 ，咒= 0 设y = a ，b ，c ，d ，p ，g ，h ，f j 不妨令i a ，b ，c ，d j 为4 长的区组，对其中任一 点，不妨a 来讲，设其组成的4 长的区组个数为，l 个，3 长的区组数为个则 有3 甩+ 2 m = 8 ，解出以= 2 ，m = 1 和，l = 0 ，m 7 = 4 两组解显然有不等 6 北京交通大学硕士学位论文第2 章1 3 ，4 + 一p b d 的存在性 式3 ( n + m 7 ) 3 n + 2 m ，即对任意取值都有m i n ( n + m 7 ) r 孕1 = 3 由于 点a 在4 长的区组上，所以应有不等式 m a x ( n + m ) m i n ( n + ，) 4 ， 但是由上面的方程解得：m a x ( n + m ) = l1 ，而r a i n ( n + 1 1 1 ) = 3 ，所以此不等式 无法成立因此v = 9 时，1 3 ，4 p b d 不存在 口 引理2 8 ，= 1 0 ，1 8 ，1 9 ，2 1 时， 3 ，4 卜p b d 存在 证明：1 ) 对于v = 1 0 ，1 3 ，4 + - p b d 的所有区组列举如下： 1 ，2 ，3 ，4 ，1 1 ，5 ，6 ，7 1 ，i l ，8 ，9 ，1 0 1 ， 1 2 ，5 ，8 ，1 2 ，6 ，9 1 ， 2 ，7 ，1 0 1 ，1 3 ，5 ，1 0 1 ， 3 , 6 ，8 1 ，1 3 ，7 ，9 1 ，1 4 ，5 ，9 ，1 4 ，6 ，1 0 ，1 4 ，7 ，8 1 2 ) 组型为3 5 的3 - g d d 为可分解设计，它共有6 个平行类。对于v = 1 8 ，添加 一个新的组1 0 0 1 ，2 ，3 l 到组型为3 5 的3 - g d d ，并把这三个无穷远点分别加到不 同的三个平行类上，组成4 长的区组，这样我们得到组型为3 6 的1 3 ，4 卜g d d ，然 后把组看作区组可以得到( 3 ，4 j ，l ；1 8 ) 一p b d 对于v = 1 9 ，添加一个新的组1 0 0 l ，0 0 2 ，3 ，4 到组型为3 5 的3 如d d ，并把这 四个无穷远点分别加到不同的四个平行类上，组成4 长的区组，这样我们得到组 型为3 5 4 1 的 3 ，4 - g d d ，然后把组看作区组可以得到( 1 3 ，4 。 ，l ； 9 ) - p b d 3 ) 对于1 ，= 2 1 ，由引理2 4 ，组型为1 1 5 7 1 的4 - g d d 存在去掉组1 1 5 中的一个 点，显然可以得到一个组型为l1 4 7 1 的 3 ，4 - g d d ，然后将7 长的组看作区组，并 拆开用3 长的区组来代替，就得到了一个( 1 3 ，4 j ，l ；2 1 ) - p b d 口 2 3 结论 由前面两节的论证，我们给出本章的主要结论 引理2 91 3 ，4 卜p b d 存在的充分必要条件是： ，兰0 ，l ( m o d3 ) ， ，4 且 ，6 ，7 ，9 证明：由前面引理2 2 至引理2 8 可得 7 口 北京交通大学硕士学位论文 第3 章1 3 ，4 - g d d 的存在性 第3 章 3 ，4 木卜g o d 的存在性 本章首先研究了 3 ，4 卜g d d 存在的必要条件，然后给出几个构造1 3 ，4 。卜 o d d 的方法，并给出了 3 ，4 + 卜g d d 的一些存在结果 3 1 必要条件 引理3 1 组型为的1 3 ，4 + 卜g d d 存在的必要条件是： ( 1 ) t 4 ， ( 2 ) 9 2 t ( t 一1 ) 兰0 ( r o o d 6 ) ，即有下表： g t 必要条件 1 ，2 ，4 ，5 ( m o d6 )0 ，1 ( r o o d3 ) t 4 0 ，3 ( r o o d 6 ) 无限制t24 证明：由引理1 3 和1 4 可推得上述条件 3 2 充分条件 引理3 2g 兰0 ，3 ( r o o d6 ) 且t 4 时，组型为g f 的1 3 ，4 + 卜g d d 存在 口 证明：1 ) 首先来看g 暑0 伽o d6 ) 的情况由引理1 4 有，g 兰0 ( r o o d6 ) 且t 4 ，( g ，力( 6 ，4 ) 时，组型为矿的4 - g d d 存在 下面主要讨论( g ，力= ( 6 ，4 ) 时 3 ，4 卜g d d 的存在性我们给出称为“减组截 断 的构造法：已知组型为6 5 的4 - g d d 存在，可以计算其中区组的个数为6 0 ，现 在去掉其中一个组使得组型变为6 4 ，在这一过程中4 长的区组被截断成3 长的区 组，可以计算被截断的区组个数为4 8 所以组型为6 5 的4 - g d d 减去一个组后，变 成了含有4 8 个3 长区组和1 2 个4 长区组的1 3 ，4 - g d d ，其组型为6 4 2 ) g 兰3 ( r o o d6 ) 的情况由引理1 4 有，g 兰3 ( r o o d 6 ) 且t 三0 ，l ( m o d4 ) ，t 4 时，组型为的4 一g d d 存在 同理再利用前面的“减组截断 的构造法，推出当t 兰3 ( m o d 4 ) ，t 7 时，组 型为矿的 3 ，4 卜o d d 存在 8 北京交通大学硕士学位论文第3 章1 3 ，4 - g d d 的存在性 当f 兰2 ( r o o d4 ) 时的情况，我们给出称为“加组增长的构造法：由定 理1 4 得到，g 兰3 ( r o o d6 ) 且f 三1 ( m o d2 ) ，t 3 时，组型为旷的3 - g d d 存在，并且 此3 - g d d 为3 - r g d d 对于组型为g 的3 - r g d d ，通过加上一个组 l ，0 0 2 ，g ，并使每一个o o i ( 15 i g ) 与3 - r g d d 中的一个平行类相连而成4 长的区组( 平行类的个数不小于组 长) ，可以得到组型为矿+ 1 的 3 ，4 - g d d 这样就推出当t 三o ( m o d2 ) ，t 4 时，组型为矿的1 3 ，4 卜g d d 存在 由1 ) 和2 ) 7 1 理得证 口 引理3 3 若组型为的4 - g d d 存在，血 4 ，则组型为矿_ 1 的 3 ，4 。卜g d d 存在 证明：由我们给出的减组截断的构造法可知，只有当砰矿c 2 噼g 成 立时，才可以由组型为的4 - g d d 构造出组型为_ 1 的 3 ，4 + - g d d ，化简此不等 式即得f 4 口 引理3 4 若组型为的3 - r g d d 存在，且f 3 ，则组型为矿1 的 3 ，4 卜g d d 存 在 证明：由我们给出的“加组增长”的构造法可知，只有当平行类的个数不小于 组长，即g ( t 一1 ) ( 3 一1 ) g 成立时才可以由组型为g f 的3 - r g d d 构造出组型 为矿1 的 3 ，4 。卜g d d ，化简此不等式即得t 3 o 引理3 5g 三2 ，4 ( r o o d6 ) 且t 兰0 ，1 ( r o o d3 ) ，t 4 ，( g ，f ) ( 2 ，4 ) 时，组型 为的 3 ，4 + 卜g d d 存在 证明：由引理1 4 有，g 誊2 ，4 ( m o d6 ) 且t 兰l ( m o d3 ) ，t 4 ，( g ，0 ( 2 ，4 ) 时，组型 为矿的4 - g d d 存在 在此结果上再由引理3 3 得知，g 三2 ，4 ( r o o d6 ) 且t 三0 ( r o o d3 ) ，t 6 时，组型 为的1 3 ，4 卜g d d 存在 下面证明( g ，力= ( 2 ，4 ) 时，组型为矿的 3 ，4 + 卜g d d 不存在不妨假设( g ，t ) = ( 2 ，4 ) 时，组型为矿的( 3 ，4 卜g d d 存在，设组为：l l a ，a j ，l 易， ， c ，c l ，l d ，a r l l ，下面 证明此设计不可能同时存在3 长和4 长的区组若此设计中存在4 长的区组，不妨 设区组经过a 点，其中一个4 长区组不妨为 口，b ，c ，d l ，显然在余下的3 个点中，与 点a 只能组成4 长的区组进一步可以推知：通过任一点的区组长度只能是4 长 的所以如果在( g ，力= ( 2 ，4 ) 时，组型为矿的 3 ，4 卜g d d 若存在，则此设计只能 是4 一g d d 而( g ，t ) = ( 2 ，4 ) 时4 一g d d 不存在，所以 3 ，4 i - g d d 也不存在 口 9 北京交通大学硕士学位论文 造： 第3 章1 3 ，4 - g d d 的存在性 对于g 兰1 ，5 ( r o o d6 ) 的情况比较复杂，为此我们引入w i l s o n 的如下基本构 引理3 61 5 若( 形，够，) 为一个组型为g l ，g 2 ，g ，的g d d 存在一个加权 函数：山：影_ z + u 0 l ，假如对任意的区组a = 协l ，x 2 一，溉l 都存 在组型为“戈1 ) ，“x 2 ) 一，o , ( x k ) 的k g d d ( ”i n g r e d i e n t g d d ) 那么存在组型 为( 力，甜( 力，“劝的k - g d d x e g lx e g 2x e g 。 引理3 7g 兰1 ，5 ( m o d6 ) 且t 兰0 ，1 ( r o o d3 ) ，t 之4 ，t 6 ，7 ，9 时，组型为g ，的 3 ，4 卜 g d d 存在 证明：由引理2 9 有， 3 ，4 卜p b d 存在当且仅当v 兰0 ，1 ( r o o d3 ) v 4 且 ， 6 ，7 ，9 将此p b d 看作组型为1 。的1 3 ，4 + 卜g d d 取加权函数为“力= g ，其中g 暑 1 ，5 ( m o d 6 ) 由引理1 3 ，对于1 3 ，4 一g d d 中的任一3 长区组，组型为9 3 的3 - g d d 存 在；由引理1 4 得知任一4 长区组，组型为矿的4 - g d d 存在最后由引理3 6 得知组 型为的 3 ，4 卜g d d 存在，其中v 兰0 ，1 ( r o o d3 ) 且v 6 ，7 ，9 e 1 3 3 t = 6 ，7 ，9 下面单独讨论g 兰1 ，5 ( r o o d 6 ) ，t = 6 ，7 ，9 时的情况 引理3 8 嗍( 彤，箩，) 为一个组型为g l , 9 2 ，踟的1 3 ，4 + 卜g d d ，若t 芝3 ，并且对 于任意的江l ，2 ，m 组型为彰的 3 - g d d 都存在，那么存在组型为i z i 的1 3 ，4 卜 g d d 再引入一个构造方法循环方法，利用此方法我们可以构造一些小阶数 的 3 ，4 i - g d d 设叩= 乙，9 = ( 叩，男) 为一个烈丙，a ；v ) 若对任一区组b = a l ，a 2 ，a k j 男，都有b + 1 = l a l + l ，a 2 + l ，诹+ lj 男，此处加法在乙中进行，则称9 = ( v ，当) 为五上的一个循环p b d 并记作c b ( g ( ，a ； ，) 设9 = ( 1 ，易) 为乙上的一个c b ( g f ，i t ；v ) ，可把加法循环群乙看作9 的一个 自同构群v 和易在乙的作用下都保持不变豸中的全体区组在乙的作用下划 分成若干轨道，每个轨道所包含的区组个数必定是v 的一个因数从而为了确定循 环设计9 = ( i ，召) ，只要在每个轨道中确定一个区组即可，这个区组叫做初始区 组 引理3 9g 三1 ，5 ( r o o d 6 ) ，g 5 ，t = 7 时，组型为g ，的 3 ，4 卜g d d 存在 1 0 北京交通大学硕士学位论文 第3 章1 3 ，4 + - g d d 的存在性 证明：1 ) 首先看g 兰l ( m o d6 ) ，t - - 7 的情况 由引理1 4 得知：组型为2 撕1 的4 - g d d 存在，其中k 2 通过去掉一个组中 的某点，可以得到组型为2 3 l 的 3 ，4 卜g d d 由引理1 3 知，组型为2 7 和1 7 的3 一 g d d 都存在由引理3 8 知g 三1 ( m o d6 ) ，g 1 3 且t = 7 时，组型为g ，的 3 ，4 卜 g d d 存在g = 7 时利用循环方法在7 - 4 9 上给出初始区组如下： 0 ，7 ，1 4 ，2 1 ，2 8 ，3 5 ，4 2 ，1 0 ，1 ，2 0 ，2 3 1 ， 0 ，8 ，1 0 ，i o ，1 l ，1 6 ，1 0 ，1 5 ，2 4 ， 0 ，1 2 ，1 8 ，1 0 ，1 3 ，1 7 ， 其中i o ，7 ，1 4 ，2 1 ，2 8 ，3 5 ，4 2 生成的轨道作为组，其他初始区组生成的轨道作为区 组，就得到一个组型为7 7 的1 3 ，4 。 - g d d 2 ) 再看g _ - - 5 ( r o o d6 ) ，t - - 7 时，由引理1 3 知，组型为3 撕1 的3 - r g d d 存在，其 中k 1 通过在其中两个平行类上分别增加一个点，得到组型为3 放2 的 3 ，4 。卜 g d d 由引理1 3 知，组型为3 7 和2 7 的3 - g d d 都存在由引理3 8 知g 兰5 ( r o o d 6 ) ，g 1 1 且t = 7 时，组型为矿的1 3 ，4 + 卜g d d 存在g = 5 时利用循环方法在z 3 5 上给出 初始区组如下： 0 ，7 ，1 4 ，2 1 ，2 8 ， 0 ，i ，1 3 ，1 6 ， 0 ，2 ，1 0 1 ，1 0 ，4 ，9 j ，1 0 ，6 ，t 7 1 ， 其中i o ，7 ，1 4 ，2 1 ，2 8 生成的轨道作为组，其他初始区组生成的轨道作为区组，就 得到一个组型为5 7 的 3 ，4 卜g d d 综合1 ) ，2 ) 引理得证 1 3 引理3 1 0g 三1 ，5 ( m o d6 ) ，g 5 ，g 7 ，且t = 9 时，组型为矿的 3 ，4 - g d d 存 在 证明：类似引理3 9 的证明过程，需要指出的是g = 5 时的情况，利用循环方 法在z 4 5 上以加法曰+ 3 的规则给出初始区组如下：1 0 ，9 ，1 8 ，2 7 ，3 6 1 ，1 0 ，i ，2 ，3 1 ， 1 0 ，4 ，7 ，1 1 ， 0 ，5 ，8 ，1 0 1 ， 0 ，6 ，1 9 ，3 0 1 ， 0 ，1 2 ，2 6 ，4 0 1 ， 0 ，1 6 ，3 1 ，4 1 ， 0 ，1 7 ，3 8 1 ， 0 ，2 0 ，3 2 1 ， 0 ，2 2 ，3 5 1 ， 0 ，2 3 ，2 9j ， 0 ，2 5 ，3 7 1 ，1 1 ，7 ，2 9 1 ， 1 ，2 0 ，3 5 1 ， 1 ，1 7 ，2 5 1 口 关于g - - l ，5 ( m o d6 ) ，t = 6 的研究目前还在进行当中，采用的基本方法类 似t = 7 ，9 时的情况另外g = 7 。f = 9 时的1 3 ，4 + 卜g d d 存在性还有待验证，作者正 借助