（概率论与数理统计专业论文）严格成对不平衡设计.pdf

北京交通大学硕士学位论文 中文摘要 中文摘要 假设k 为给定的正整数集，y 为给定的非负整数，一个成对不平衡设计是一 个二元组( x ，男) ，其中x 是一个y 元集，$ 是x 的子集族，8 中的元素称为区组， 并且满足：( 1 ) 对v b 召，都有ibi k ；( 2 ) x 中任意两个元素对在区组中出现 的次数都不相同特别地，对于每个1 f v ( v 一1 ) 9 ，如果x 中恰好存在一个元 素对出现在某f 个区组中，则该成对不平衡设计是一个严格成对不平衡设计 s a r v a t e 和b e a m 曾在文章【6 1 中指出严格成对不平衡三元系存在的必要条件 是1 ，兰0 ，1 ( m o d3 ) 并且v 3 本文主要研究成对不平衡设计的存在性问题，并 证明了严格成对不平衡三元系存在的必要条件也是充分的此外本文给出组型 为矿的严格成对不平衡可分组三元系的一些初步结论，并指出该设计存在的必要 条件是g 兰0 ( m o d3 ) ，或者g 三1 ，2 ( r o o d3 ) 并且t 三0 ，1 ( r o o d3 ) 本文共分五章 第一章简要介绍新类型设计的研究背景，给出成对不平衡设计的相关概念 和研究现状 第二章首先介绍辅助设计的基本概念；其次给出基本构造方法，该构造方法 是解决成对不平衡设计的主要方法，对本文主要结论的证明非常有用 第三章首先给出一些严格成对不平衡三元系的小阶数例子；其次给出一些 特殊新类型三元系；最后利用第二章中的基本构造方法和辅助设计证明了严格成 对不平衡三元系存在的必要条件也是充分的 第四章首先给出严格成对不平衡可分组三元系存在的必要条件和小阶数例 子，并得到一些初步结论；其次给出区组长度是4 的严格成对不平衡设计的小阶 数例子，并给出满足一定条件的严格成对不平衡设计的小阶数例子 第五章总结了第一、二、三、四章的内容，并给出了最新结果以及今后的 研究前景 关键词：s a r v a t e b e a m 设计；成对不平衡设计；成对不平衡可分组设计；严格成对 不平衡设计；构造 分类号：0 1 5 7 2 北京交通人学硕十学位论文 a b s t r a c t a b s t r a c t l e tkb eas e to fp o s i t i v ei n t e g e r sa n d ，b eap o s i t i v ei n t e g e r ap a i r w i s ed i s t i n c t d e s i g ni sap a i r ( x ，男) ，w h e r ex i sas e to f ，p o i n t sa n d 乃i sas e to fs u b s e t so f x ( c a l l e d b l o c k s ) ，e a c ho fc a r d i n a l i t yf r o mk ，s u c ht h a tn ot w op a i r so fxo c c u ri nt h es a m e n u m b e ro fb l o c k s f u r t h e r , i ff o re a c h1 i v ( v 一1 ) 2 ，t h e r ee x i s t se x a c t l yo n ep a i r o fx o c c u r r i n gi nib l o c k s ，s u c hp a i r w i s ed i s t i n c td e s i g ni ss a i dt ob es t r i c t s a r v a t ea n db e a m 6 p r e s e n tt h a tt h en e c e s s a r yc o n d i t i o n sf o rt h ee x i s t e n c eo f s t r i c t l yp a i r w i s ed i s t i n c t 仃i p l es y s t e m sa l ev 3 a n dv 三0 ，1 ( m o d3 ) i nt h i sp a - p e rt h ee x i s t e n c eo fp a i r w i s ed i s t i n c td e s i g na r ei n v e s t i g a t e d i ti se s t a b l i s h e dt h a tt h e n e c e s s a r yc o n d i t i o n sf o r t h ee x i s t e n c eo fas t r i c t l yp a i r w i s ed i s t i n c tt r i p l es y s t e ma l e a l s os u f f i c i e n t i na d d i t i o n ，w ep r e s e n tt h a tt h en e c e s s a r yc o n d i t i o n sf o rt h ee x i s t e n c e o fas t r i c t l yp a i r w i s ed i s t i n c tg r o u pd i v i s i b l ed e s i g no ft y p e 窖a n db l o c ks i z e3 缸e g 三0 ( r o o d3 ) ，o rg 兰1 ，2 ( m o d3 ) a n dt 三0 ，1 ( m o d3 ) t h e r ea r ef i v ec h a p t e r si nt h i st h e s i s i nc h a p t e r1 ，w ei n t r o d u c es o m eb a s i cd e f i n i t i o n sa n ds o m ek n o w nr e s u l t so fp a i r - w i s ed i s t i n c td e s i g n i nc h a p t e r2 ，w ei n t r o d u c et h eb a s i cd e f i n i t i o n so fa u x i l i a r yd e s i g n s ，t h e nd e s c r i b e o u rr e c u r s i v ec o n s t r u c t i o n sw h i c ha r ev e r yu s e f u lf o rt h ep r o o fo ft h em a i nc o n c l u s i o n s i nt h et h e s i s i nc h a p t e r3 ，w ep r e s e n ts o m ee x a m p l e so fs t r i c t l yp a i r w i s ed i s t i n c tt r i p l es y s t e r n so fs m a l lo r d e r , t h e np r e s e n ts o m es p e c i a ln e wt y p eo fb l o c kd e s i g n s a tl a s t ，w e p r o v et h a tt h en e c e s s a r yc o n d i t i o n sf o rt h ee x i s t e n c eo fas t r i c t l yp a i r w i s ed i s t i n c tt r i p l e s y s t e m sa r ea l s os u f f i c i e n t i nc h a p t e r4 ，w ep r e s e n tt h en e c e s s a r yc o n d i t i o n sf o rt h ee x i s t e n c eo fas t r i c t l y p a i r w i s ed i s t i n c tg r o u pd i v i s i b l ed e s i g no ft y p e 窖a n db l o c ks i z e3 ，t h e ns o m ee x a m p i e sa n db a s i cr e s u l t so ft h ed e s i g n sa r ep r e s e n t e di nt h i ss e c t i o n w ea l s oh a v es o m e e x a m p l e so fs t r i c t l yp a i r w i s ed i s t i n c td e s i g no fb l o c k s i z e4 f i n a l l y ，w ep r e s e n ts o m e e x a m p l e so fs t r i c t l yp a i r w i s ed i s t i n c td e s i g n sw i t hs o m e r e s t r i c t i o n s i nc h a p t e r5 ，t h em a i nc o n c l u s i o n so ft h i st h e s i sa r es u m m a r i z e d ，a n dt h ef u r t h e r r e s e a r c hp r o b l e m sa r ep r e s e n t e da tl a s t k e y w o r d s ：s a r v a t e b e a md e s i g n ；p a i r w i s ed i s t i n c td e s i g n ；p a i r w i s ed i s t i n c tg r o u p d i v i s i b l ed e s i g n ；s t r i c t l yp a i r w i s ed i s t i n c td e s i g n ；c o n s t r u c t i o n c l a s s n o ：01 5 7 2 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。 特授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学 校向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：马书留旅少 签字日期：峙年占月节日 导师签 签字日期：碱翻怕 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位 或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在 论文中作了明确的说明并表示了谢意。 学位论文作者签名：弓七钒签字日期：砌壮6 月牛日 致谢 本论文的工作是在我的导师常彦勋教授的悉心指导下完成的，在论文选题、 研究、定稿的过程中，常老师自始至终给了我大力的支持和无私的关怀感谢我 的导师，他严谨细致、一丝不苟的作风一直是我工作、学习中的榜样，他循循善 诱的教导和不拘一格的思路给予我无尽的启迪无论是在科研上，还是在平时的 生活中，他都给了我无微不至的关怀与鼓励他严谨的治学风格，广博的知识，精 益求精的科研作风，敏锐的学术思想和忘我的工作精神影响并鞭策了我，是我今 后生活与工作中一笔极大的财富，在此谨向常老师表示深深的感谢 感谢冯驶师兄对我的帮助和指点，无论是在平时的学习，还是在论文的写作 中，他都给我提出了很多宝贵建议，在此向冯师兄表示真诚的感谢此外，在撰写 论文期间，周君灵、常相茂、吴艳、i d , 苗、陈琦、王昭、李靖尘、林伟伟等师 兄师姐都给予我热情的帮助，我也从中学到很多知识，在此向他们表达我的感激 之情 最后，感谢各位专家和学者在百忙中审阅我的论文，并给出批评意见回首两 年的研究生生活，自己的每一步前进，都离不开老师、亲朋和同学的支持与教诲， 在此表达我对他们最衷心的感谢! 北京交通大学硕士学位论文 第1 章绪论 1 1 背景介绍 第1 章绪论 在组合设计中，大家熟知平衡不完全区组设计( y ，b ，r , k ，a ) 设计作为该类 设计的一个推广，如果用整数集k - - i k l , 如，岛，k l 代替k ，我们可以得到成 对平衡设计( y ，b ，墨a ) 一设计平衡不完全区组设计和成对平衡设计的概念均 可参见文章【1 1 、【2 】和【3 1 如果我们从另一种角度推广平衡不完全区组设计，保 持k 不变，但用a = a l ，1 1 2 ，厶j 取代a ，可以得到一种新类型设计，m e n d e l s o h n 和l i a n g 曾在文章1 4 中引入这种新类型差集和设计，即( v ，k ，队1 ，a 2 ，厶】) 一 差集和( v ，k ，【l l ，a 2 ，a 。】) 一设计，对相关问题做了初步研究，并得到一些结论 我们考虑集合v = 1 ，2 ，3 ，4 l 上的一个设计，该设计的7 个区组为： 1 1 ，2 ，4 j ，1 1 ，3 ，4 l ，1 1 ，3 ，4 ，1 2 ，3 ，4 j ，1 2 ，3 ，4 l ，1 2 ，3 ，4 j ，1 2 ，3 ，4 观察该设计可以知道，集合v = 1 1 ，2 ，3 ，4 j 上的所有元素对出现的次数是 不相同的，这个特点正好与平衡不完全区组设计相反，而且我们发现对于所 有江l ，2 ，3 ，4 ，5 ，6 ，集合v = 1 1 ，2 ，3 ，4 上恰好存在一个元素对出现的次数是i 这 种新类型设计引起一些学者的注意 s a r v a t e 和b e a m 在文章【6 】中引入这种新类型设计，称作a d e s i g n ，他们给出 一些严格和不严格的区组长度为3 的a d e s i g n s 的例子，并指出严格的区组长度 为3 的a d e s i g n s 存在的必要条件是1 ，三0 ，l ( m o d3 ) 并且v 3 ，同时在文章【7 】中 给出该类设计的一些推广和相关结论s t a n t o n 在文章【8 】中把严格的区组长度 为3 的a d e s i g n s 称作s a r v a t e - b e a m 三元系，并给出几个s a r v a t e b e a m 三元系的小 阶数例子对于1 ，三2 ( r o o d3 ) 的情况，s t a n t o n 在文章【1 0 】中定义了s a r v a t e b e a m 类 型的三元系此外，s t a n t o n 在文章【9 】中给出严格的区组长度为4 的a d e s i g n s 存在 的必要条件和小阶数例子一些满足一定条件的s a r v a t e - b e a m 三元系和区组长度 为4 的a d e s i g n s 在s t a n t o n 的文章【引、 9 1 和【l l 】中均有所涉及 s a r v a t e 和b e a m 曾在文章 6 1 中提出这样的问题：s a r v a t e b e a m 三元系存在的 必要条件是否也是充分的本文基于以上背景，对这种新类型的设计做了进一步 的探讨，建立了基本构造方法，并证明了s a r v a t e b e a m 三元系存在的必要条件也 是充分的为了与传统成对平衡设计的概念相一致，我们用了不同的术语，分别用 成对不平衡设计和严格成对不平衡三元系取代了a d e s i g n s 和s a r v a t e b e a m 三元 系 以下是新类型设计的基本概念和已有结论 北京交通大学硕+ 学位论文 第1 章绪论 1 2 基本概念 假设k 为给定的正整数集，并且a 。，a 2 ，厶是互不相同的正整数 定义1 2 1 一个( ，k ，【五l ，a 2 ，a 蝌】) 一设计是一个二元组( x ，男) ，满足以下条件： ( 1 ) x 是一个v 元集； ( 2 ) 召是x 的子集族，$ 中的元素称为区组，并且对v b 易，都有ibl k ； ( 3 ) x 中每个元素对恰好出现在某 ( 1 i m ) 个区组中； ( 4 ) 对于每个丑( 1 f m ) ，x 中至少存在一个元素对恰好出现在丑个区 组中 如果k = 七l ，我们可以用k 代替k ，得到( ，k ，阮，1 1 2 ，厶】) 一设计，m e n d e l s o l m 和l i a n g 曾在文章【4 l 中提出此概念 定义1 2 2 对于( ，k ，【五l ，允2 ，厶】) 设计，如果x 中的任意两个元素对在区组中 出现的次数都不相同，我们称这种设计为成对不平衡设计，记作p d d ( v ，1 0 定义1 2 3 在成对不平衡设计中，对于每个1 f v ( v 一1 ) 2 ，如果x 中恰好存在 一个元素对出现在某f 个区组中，则该成对不平衡设计被称作严格成对不平衡设 计，记作s p d d ( v ，1 0 如果k = 1 3 1 ，一个( 严格) 成对不平衡设计被称作( 严格) 成对不平衡三元系， 记作p d t s ( v ) ( s p d t s ( v ) ) 如果k = 4 1 ，一个( 严格) 成对不平衡设计被称作区组长度是4 的( 严格) 成 对不平衡设计，记作p d d ( v ，4 ) ( s p d d ( y ，4 ) ) s a r v a t e 和b e a m 在文章 6 1 中把设计尸d d ( y ，妨记作a d ( v ，p ，s t a n t o n 在文 章嗍中把设计s p d t s ( v ) 记作s b t s ( v ) 正如s a r v a t e 和b e a m 在文章【7 l 中对设 计a d e s i g n s 的推广，我们可以将成对不平衡设计推广一下，得到t 元不平衡设计的 相关定义 定义1 2 4 如果x 中的任意两个f 元子集在区组中出现的次数都不同，则得到f 元 不平衡设计，记作t - d d ( v ，的如果该设计是严格的，则将其记作t - s d d ( v ，1 0 如果每个元素在区组中出现的次数都不相同，则可以得到1 - d d ( v ，k ) 值得注 意的是，如果t = 2 ，此时x 中的任意两个元素对在区组中出现的次数都不相同，即 为前面定义的p d d ( v ，i o 有时我们需要考虑设计在同构意义下的个数，因此我们引入两个设计同构的 定义 2 北京交通大学硕+ 学位论文 第1 章绪论 定义1 2 5 设计d 和矿被称作是同构的，如果存在一个从d 到的一一映 射，满足： 妒：而_ # = 似置) ； 马一巧= ( 乃) 其中而和葛分别是d 和d 中元素，毋和巧分别是d 和d 中的区组，此 时而岛当且仅当( 而) 妒( 口) 为方便，我们有下面定义 定义1 2 6 假设( x ，囝是一个成对不平衡设计，则x 中元素对在区组中出现的次 数被称作对子的次数，所有对子的次数的最大数被称作对子的最大次数 因此设计s p d d ( 1 ，目中对子的最大次数是v ( v 一1 ) 2 1 3 已有结论 引理1 3 1 6 1s p d t s ( v ) 存在的必要条件是v 3 并且1 ，兰0 ，1 ( r o o d3 ) 证明：当k = 3 时，每个区组中元素对的总数是3 ，s p d t s ( v ) 中所有对子的次数 的总数为： 1 + 2 + + 竽= ( 1 + 掣) 2 丁h v - 1 ) i 一半 对于s p d t s ( v ) ，应有3 1 1 2 + v ( v 一1 ) 】【v ( y 一1 ) 8 ，则有3 1 v ( v 1 ) 或者3 1 2 + “v 1 ) 而对于v 耋0 ，1 ，2 ( r o o d3 ) 的所有情况，3 十2 + v ( v 1 ) ，因此3 1 v ( v 一1 ) 必成立经 计算可知结论成立 口 引理1 3 21 7 s p d d ( v ，4 ) 存在的必要条件是，三0 ，1 ，3 ，6 ，9 ，1 6 ，1 9 ，2 2 ( r o o d2 4 ) 证明：当k = 4 时，每个区组中元素对的总数是6 ，s p d d ( v ，4 ) 中所有对子的次数 的总数为： 1 + 2 + + v ( v 2 - 1 ) = ( 1 + 掣) 2 - 掣= 一 2 + 丛v - 1 1 ) v ( v 一- 1 ) 1 对于s p d d ( v ，4 ) ，应有6 1 1 2 + v ( v 一1 ) 】【v ( v 1 ) 】8 ，即4 8 1 1 2 + v ( v - 1 ) 】【v ( 1 ，一1 ) 】此时 考虑3 和1 6 的同余类，经计算有v 三0 ，l ( m o d3 ) 和l ，兰0 ，1 ，3 ，6 ，8 ，9 ，1 l ，1 4 ( r o o d1 6 ) 意味着v 兰0 ，l ，3 ，6 ，9 ，1 6 ，1 9 ，2 2 ，2 4 ，2 5 ，2 7 ，3 0 ，2 2 ，4 0 ，4 3 ，4 6 ( m o d 4 8 ) 则等价于v 兰 0 ，1 ，3 ，6 ，9 ，1 6 ，1 9 ，2 2 ( r o o d2 4 ) ，因此结论得证 口 3 北京交通大学硕士学位论文 第1 章绪论 引理1 3 3 7 1l s d d ( v ，足) 存在的的充分必要条件是 ( 1 ) klv ( v + 1 ) 2 ； ( 2 ) k ( v + 1 ) 2 证明：一方面，设计1 - s d d ( v ，良) 的区组个数一定是整数，因此第一个条件容易得 证对于1 - s d d ( v ，七) ，恰好存在一个元素在区组中出现次数为k 每个元素在某个 区组中出现的次数至多是1 ，并且设计具有v ( v - i - 1 ) 2 k 个区组， j y v ( v + 1 ) 2 k j k v ( v + 1 ) 2 v 毒ks ( y + 1 ) 2 另一方面，为证充分性，我们给出构造设计1 - s d d ( v ，幼的一个算法，不妨令所 构造设计具有b = v ( v + 1 ) 2 k 个区组令v = 1 ，2 ，1 ， ，不失一般性，我们假定元 素i 出现的次数为f 假定所构造设计1 s d d ( v ，勋中的区组为风，口1 ，岛，既- l 将元素1 放置在区组风中，然后将元素2 放置在区组b l 和曰2 中，依次类推， 不妨假定元素f 一1 所放置在区组中的最后一个是曰；- l ，则将元素i 放置在区 组曰，b + l ，b + 2 ，局+ 1 中，其中下标是模b 后的值第一个条件可以保证所构 造的区组长度为k 由第二个条件可以得知，以此法构造的区组不是多重集 k ( y + i ) 2 = k v ( v + 1 ) 2 v = j y v ( v + 1 ) 2 k 因此，以该算法构造的设计，任何一个元素在某个区组中出现的次数最多为1 ， 并且每个元素在区组中出现的次数均不相同 口 引理1 3 4 】乒j d d ( v ，j i ；= ) 存在的必要条件是( 譬) i ( ；) ( ( ￥) + 1 ) 2 证明：设计乒s d d ( v ，七) 中的每个区组包含g ) 个f 一子集，点集y 上共有( ：) 个f 一子 集，并且该设计中t 子集出现次数的总数为： 1 + 2 + + g ) = ( ￥) ( ( ；) + 1 ) 2 若凇d d ( v ，d 存在，必有e ) 整除( ￥) ( ( ；) + d 2 ，因此结论得证 4 口 北京交通火学硕士学位论文第1 章绪论 下面是关于 一2 ) 一d d ( n ，挖一1 ) 存在性问题的相关结论，其证明可参见文章 7 1 引理1 3 5 7 1 对于任意的 4 ，( n 一2 ) s d d ( n ，n 一1 ) 不存在 引理1 3 6 【7 】对于任意的n ，不严格的伽一2 ) d d ( n ，l 一1 ) 均存在 5 北京交通大学硕士学位论文第2 章构造方法 第2 章构造方法 这部分主要介绍了三种基本构造方法，这些构造是我们解决成对不平衡设计 的主要方法，对本文第三章主要结论的证明非常有用在建立基本构造方法的过 程中，我们需要用到一些辅助设计，因此首先介绍辅助设计的基本概念，然后具体 给出加权构造、p b d 一构造及填充子设计构造，并给出构造的证明 2 i 基本概念 假设k 为给定的正整数集，a 为给定的正整数 定义2 1 i 一个( k a ) 可分组设计( 或者( k ，a ) 一g d d ) 是一个三元组( x 莎，固，满 足以下四个条件： ( i ) 莎是x 的一个划分，眵中的元素称为组； ( 2 ) 贸是x 的子集族，舅中的元素称为区组，并且对v a 舅，都有lai k ； ( 3 ) 对v a 贸和y g 纱，都有ia ngl i ，即任意的组和区组最多只有一个 公共点： ( 4 ) x 中属于不同组的任意一对元素恰好出现在a 个区组中 特别地，如果i = i ，我们可将( 墨1 ) 一g d d 简记为k g d d 假设设计( 墨a ) g d d ( x , g ，习) 的组为i ig l ：g 够1 对于i f j ，如果锣中 有蜥个大小为戤的组，我们可以用“指数”形式来描述该设计的组，此时可以 称( x ，纱，舅) 是一个组型为硝1 9 世的g d 设计如果k = ，我们可用k 代 替置 定义2 i 2 一个组型为i ”的( 噩a ) ，g d d 被称作成对平衡设诜记作( v ，k ，a ) p b d 当k = 时，成对平衡设计被称作平衡不完全区纽设计，记作( v ，k ，a ) 一b i b d 定义2 i 3 一个组型为i v - h h l 的( 墨1 ) g d d 被称作不完全成对平衡设计，记 作( ，7 l ；墨a ) 一i p b d 当k = l i c 时，不完全成对平衡设计被称作不完全平衡不完全 区纽设计，记作( 1 ，h ；k ，1 ) 一i b i b d 以上设计中，如果参数a = i ，可将其省略 6 北京交通大学硕士学位论文第2 章构造方法 定义2 1 4 一个成对不平衡可分纽设计( 或者p d g d d ) 是一个三元组( x ，侈，舅) ， 满足以下四个条件： ( 1 ) 纱是x 的一个划分，莎中的元素称为组； ( 2 ) 贸是x 的子集族，用中的元素称为区组，并且对v a , 7 1 ，都有lai k ； ( 3 ) 对y a 舅和y g 多，都有langl 1 ，即任意的组和区组最多只有一个 公共点： ( 4 ) x 中属于不同组的任意两对元素在区组中出现的次数都不相同 假设p d g d d 的组是集合 i g i ：g g l ，正如g d d s 。我们也可以用“指数 形式描述p d g d d s 的组型 定义2 1 5 假设p d g d d 中属于相同组的元素对的总数是跖，对于每个1 f v ( v 一1 ) 2 一u ，如果x 中恰好存在一对来自不同组的元素出现在某i 个区组中， 则p d g d d 被称为是严格的，记作s p d g d d 定义2 1 6 一个组型为i v - h 1 的k - p d g d d 被称作不完全成对不平衡设计，记 作( ，j i z ；i o 1 p d d 对于每个1 f v ( v 一1 ) 2 一h ( h 一1 ) 2 ，如果x 中恰好存在 一对不同时来自h 中的元素出现在f 个区组中，则i p d d 被称为是严格的，记 作s l p d d 特别地，设计( ，h ；3 ) i p d d 和( v ，危；3 ) 一s l p d d 可以分别简记作i p d t s ( v ，h ) 和 s l p d t s ( v ，坳正如对成对不平衡设计的对子次数，最大次数的定义，我们可以类 似地定义p d g d d 和i p d d 的对子的次数和最大次数 2 2 基本构造 下面的构造简单但非常有用，三个基本构造可以看作是文章【1 2 】中w i l s o n 基 本构造的变形 构造2 2 1 ( 加权构造) 假设k 和l 是正整数集，假设( x ，缪，贝) 是一个区组为贝= ，a 2 ，a m 的k - g d d ，并且设山：xhz + u o j 0 是x 上的权函数对于 每个工x ，设s ( 力是以曲个不同x 的复制的集合对于每个1 f m ，假 设( u 础；s ( 曲，l s ( x ) ：工a 儿甄；) 是一个具有对子的最大次数为 的厶p d g d d ， 对于每个2 f 历，如果( u 刚，s ( 力，博( 力：工a f j 易：) 是一个( l ，e i - la ，、g d d ， 则( u 硝s ( 曲，l u 疆a s ( x ) ：g 侈 ，u 贝酮( 既1u 当石) ) 是一个厶p d g d d 特别地， 对于每个15i m ，如果需要用到的子设计d p d g d d 是严格的，则最终设 计上广p d g d d 也是严格的 7 北京交通大学硕十学位论文 第2 章构造方法 证明：根据假设，( x ，够，舅) 是一个区组为贸= i a l ，a 2 ，a m j 的k - g d d 对于每个2 f ，z ，存在一个具有对子的最大次数为丑的l - p d g d d ( u ，a ， s ( 工) ， s ( 工) ：工a i ，男k ) 和( l ，甚j ，) 一g d d ( u 雕蚋；s ( 工) ， s ( 对：工a i ! ，垡咯，) 所以对于每个2 i r r ，( u 脚；s ( 而，博( 曲：工a i ，甄，u 群，) 是一个对子的次 数为i t ：翟a j + 1s ts 名l 山l 的l - p d g d d 因此能够容易验证( u 觥s ( 曲，i t o 工e g s ( 曲：g g l ，u 用酮( 鳓u ) ) 是一个l p d g d d 特别地，对于每个l f 冬m ，如果需要用到的子设计l - p d g d d 是严格的，则 最终设计l - p d g d d 也是严格的 n 下面的p b d 构造可以看作是构造2 2 1 的推论 构造2 2 2 ( p b d 一构造) 假设k 和l 是正整数集，假设( x ，舅) 是一个具有区组 为贝= i a l ，a 2 ，a m 的( v ，k ，1 ) p b d 对于每个1 ism ，假设( a ，玩。) 是 一个具有对子的最大次数为 的p d d ( i a f i d 此外，对于每个2 f m ，如 果( a f ，彩，) 是一个( m f i ，厶葛a j ) 一p b d ，则( x ，翻( 既u ) ) 一个p d d ( v ，) 特别 地，对于每个1sf 如果需要用到的子设计p d d ( i a f i ，l ) 是严格的，则最终设 计p d d 也是严格的 证明：根据假设，( x 翻) 是一个具有区组为7 i = l ，a 2 ，a m j 的( ，匠1 ) 一p b d 对于每个2sf m ，( a f ，玩，) 是一个具有对子的最大次数为i t 的p d d ( m d ，l ) ， 并且( a f ，暖，) 是一个( i a _ f i ，l ，j - = 1 l j p p b d 所以对于每个2 i m ，( i a f l ，l 玩；u 缓；) 是一个对子的次数为p ：端a + 1 t z j i ：l a j 的l - p d d 因此能够容易验证c ku a 酮( 玩u 易j ) ) 一个p d d ( v ，l ) 特别地，对于每个1 f m ，如果需要用到的子设计p d d ( i a i i ，) 是严格的， 则最终设计p d d 也是严格的 口 构造2 2 3 ( 填充子设计构造) 假设置和是正整数集，设h 是一个非负正整 数，假设( x ，够，两是一个组为够= i g l ，g 2 ，q l 的k p d g d d ( 称为主设计) ， 并且该设计中对子的最大次数为a 假设p d d ( i g i + h ，d 存在，并且对于每 个1 i n i ，存在一个对子的最大次数为l i 的i p d d ( i g i i + h ，i f l ；d 如果( i g l i + h ，j l z ；l ，a ) i p b d 和( 1 g i + h ，l ，a + n - 1 f ) - p b d 存在，并且对于每个2 f n i ， ( i g i + h ， ；l ，a + 翟a ) i p b d 也存在，则p d d ( 1 ，kud 存在，其中v = 1 l g f f + h 特别地，如果主设计k p d g d d 和需要用到的子设计p d d ( i g i + h ，d 是严格的， 8 北京交通大学硕+ 学位论文 第2 章构造方法 并且对于每个lsf 路一l ，如果需要用到的子设计i p d d ( i g i _ i + ，如；d 也是严格 的，则最终设计p d d 也是严格的 证明：假设日是一个h 元集，并且h n x = 0 ，根据假设，组为妙= i g i ，g 2 。，g 。l 的 设计k - p d g d d ( 五莎，网存在，并且对子的最大次数为 对于每个1 i 疗一1 ，假设( g j f u h ，1 - 1 , 霸) 是一个具有对子的最大次数为a f 的 设计i p d d ( 1 g j l + h ，缸l ) ，此外，由于( 1 g 1 l + 珏，_ t ；l ，抑一i p b d ( g luh ，h ，$ ：) 存在， 因此设计( g lu 见e 男lu 男；) 是一个i p d d ( i g l i + | l l ，j l ；d ，其中对子的次数 为( t ：a + 1 t a + a lj 对于每个2 f n 一1 ，设计( 1g j l + h ， ；l ，a + 端a j ) 一i p b d ( g fuh ，h ，霉) 存 在，所以( gu 日，鼠霸ug ) 是一个i p d d ( i g s + 厅，i l ；l ) ，其中对子的次数为i t ： 五+ ；j a ，+ 1 t a + e i ，- i a ，j 根据题中假设可知，( g ，统) 是一个p d d ( i g n i + ，l ) ，并且( gu 儿域) 是一 个( i g 。i + 办，l ，a + n f - - 1 i l 少p b d ，则( guh ，统u 甄) 是一个p d d ( i g 。i + 死l ) ，其中 对子的次数为i t ：a + 笮i a f + l t a + 名i a 止 因此能够容易验证uh ，( o 剖n ( 翁ug ) ) u 固是一个p d d ( v ，kud ，其 中v = 翠l 蚓+ h 特别地，如果主设计k p d g d d 和需要用到的子设计p d d ( i o 。i + ，d 是严格 的，并且对于每个1 f n 一1 ，子设计i p d d ( i g i + ，j i z ；l ) 是严格的，能够容易验 证最终设计p d d 也是严格的 c 1 2 3 构造中用到的结论 下面几个引理对本文第三、四章结论的证明很有用 引理2 3 1d 3 1 对于任意的v 三0 ，1 ( r o o d3 ) ，并且 ，岳 l o ，1 2 ，1 5 ，1 8 ，1 9 ，2 4 ，9 7 1 ，设 计( 1 ，1 4 ，6 ，7 ，9j ，1 ) 一p b d 存在 引理2 3 2d 4 1 对于任意的v 三0 ，1 ( r o o d3 ) ，并且y 6 ，设计( v ，1 3 ，4 ，1 ) 一p b d 存在 引理2 3 31 1 4 1 对于任意的v 三0 ，1 ( r o o d3 ) ，设计( v ，1 3 ，4 ，6 1 ，1 ) 一p b d 存在 引理2 3 4 【1 5 j 一个组型为m “的( 3 ，a ) g d d 存在的充分必要条件是( 1 ) “3 ，( 2 ) a ( u 1 ) m 三0 ( r o o d2 ) ，( 3 ) a u ( u 一1 ) m 2 兰0 ( r o o d6 ) 9 北京交通大学硕士学位论文 第3 章s p d t s 的存在性 第3 章s p d t s f l 勺存在性 这一章主要探讨严格成对不平衡三元系的存在性问题，首先给出小阶数例子， 然后利用基本构造方法和辅助设计得到本文的主要结论 为方便，下面我们用r a ，b ，c l 表示区组l 口，b ，c l 出现，次用字母f 表示次数， 则，( i 工，y 1 ) 表示元素对 z ，) ，j 出现的次数，f ( i 石，y ，z d 表示区组( z ，y ，z j 出现的次 数 3 1 小阶数例子 引理3 1 1 8 1s p d t s ( 4 ) 存在 证明：假设元素对1 1 ，2 j 出现的次数为1 ，不妨假设出现在区组1 1 ，2 ，3 j 中 当v = 4 时，设计中共有6 个元素对，对子出现次数的总数为：1 + 2 + 3 + 4 + 5 + 6 = 2 1 对于长度为3 的区组，每个区组提供3 个元素对，因此该设计中共 有2 1 3 = 7 个区组，此时我们可以假设有1 个( 1 ，2 ，3 1 ，a 个1 1 ，3 ，4 1 ，b 个( 2 ，3 ，4 j ， 则有a + b = 6 我们有f ( 1 ，3 1 ) = 1 + 识f ( 1 1 ，4 1 ) = a ，f ( 1 2 ，3 1 ) = 1 + b ，f ( ( 2 ，4 1 ) = b 不失一般 性，我们可以假设a 1 ，a b 因此唯一的可能结果是a = 2 ，b = 4 ， 可以得知在同构的意义下，该设计是唯一存在的 可以将元素对出现的次数列为下表： 元素对1 1 , 2 1 ，4 1 1 , 3 2 ，4 j1 2 ，3 j1 3 ，4 i 出现的次数 l23456 因此s p d t s ( 4 ) 为： 1 1 ，2 ，3 1 ，1 1 ，3 ，4 1 ，1 1 ，3 ，4 1 ，1 2 ，3 ，4 1 ，1 2 ，3 ，4 1 ， 2 ，3 ，4 1 ，1 2 ，3 ，4 1 根据构造过程可以得到下面一个引理 引理3 1 2 s ls p d t s ( 4 ) 在同构的意义下是唯一存在的 引理3 1 3 【8 】当，= 6 ，7 时，s p d t s ( v ) 存在 1 0 口 北京交通火学硕十学位论文第3 章s p d t s 的存在性 证明：当v = 6 时，设计中共有1 5 个元素对，对子出现次数的总数为：i + 2 + + 6 ( 6 1 ) 2 = 1 2 0 ，因此该设计共有1 2 0 3 = 4 0 个区组，不妨假设区组出现的次数 为： f ( i l ，2 ，3j ) = l ， f ( l ，3 ，6 j ) = 厶 f ( l ，5 ，6 j ) = f f ( 2 ，3 ，6 j ) = j ， f ( 2 ，5 ，6 ) = t n ， f ( 1 3 ，5 ，6 j ) = g ， v ( 1 ，3 ，4 1 ) = a ， f ( 1 ，4 ，5 j ) = d ， f ( 2 ，3 ，4 j ) = g ， f ( 2 ，4 ，5j ) = k ， f ( 1 3 ，4 ，5 1 ) = 牲， f ( 4 ，5 ，6 j ) = r 因此我们可以得到对子出现次数为： f ( 1 1 ，2 j ) = 1 ， f ( ( 1 ，4 j ) = a - i - d 4 - b f ( 1 1 ，6 ) = c + e + 厂， f ( 1 2 ，4 j ) = g4 - k + 厶 f ( 【2 ，6 j ) = - i - z + ，l ， f ( 1 3 ，5 ) = b4 - h + 理4 - q ， f ( ( 4 ，5 ) = d + k + ，l - i - ， f ( 1 5 ，6 j ) = 厂- i - ，咒+ g + ， f ( 1 1 ，3 ，5 ) ：b ， f ( l ，4 ，6 1 ) = e ， f ( 1 2 ，3 ，5 j ) = h ， f ( 1 2 ，4 ，6 ) = z ， f ( 1 3 ，4 ，6 1 ) = p ， ，( 1 ，3j ) = a + b + c + 1 ， 以 l ，5 j ) = b + d + 厂 f ( 2 ，3 1 ) = g + h4 - +