（概率論與數(shù)理統(tǒng)計專業(yè)論文）嚴格成對不平衡設計.pdf

北京交通大學碩士學位論文 中文摘要 中文摘要 假設k 為給定的正整數(shù)集，y 為給定的非負整數(shù)，一個成對不平衡設計是一 個二元組( x ，男) ，其中x 是一個y 元集，$ 是x 的子集族，8 中的元素稱為區(qū)組， 并且滿足：( 1 ) 對v b 召，都有ibi k ；( 2 ) x 中任意兩個元素對在區(qū)組中出現(xiàn) 的次數(shù)都不相同特別地，對于每個1 f v ( v 一1 ) 9 ，如果x 中恰好存在一個元 素對出現(xiàn)在某f 個區(qū)組中，則該成對不平衡設計是一個嚴格成對不平衡設計 s a r v a t e 和b e a m 曾在文章【6 1 中指出嚴格成對不平衡三元系存在的必要條件 是1 ，蘭0 ，1 ( m o d3 ) 并且v 3 本文主要研究成對不平衡設計的存在性問題，并 證明了嚴格成對不平衡三元系存在的必要條件也是充分的此外本文給出組型 為礦的嚴格成對不平衡可分組三元系的一些初步結(jié)論，并指出該設計存在的必要 條件是g 蘭0 ( m o d3 ) ，或者g 三1 ，2 ( r o o d3 ) 并且t 三0 ，1 ( r o o d3 ) 本文共分五章 第一章簡要介紹新類型設計的研究背景，給出成對不平衡設計的相關(guān)概念 和研究現(xiàn)狀 第二章首先介紹輔助設計的基本概念；其次給出基本構(gòu)造方法，該構(gòu)造方法 是解決成對不平衡設計的主要方法，對本文主要結(jié)論的證明非常有用 第三章首先給出一些嚴格成對不平衡三元系的小階數(shù)例子；其次給出一些 特殊新類型三元系；最后利用第二章中的基本構(gòu)造方法和輔助設計證明了嚴格成 對不平衡三元系存在的必要條件也是充分的 第四章首先給出嚴格成對不平衡可分組三元系存在的必要條件和小階數(shù)例 子，并得到一些初步結(jié)論；其次給出區(qū)組長度是4 的嚴格成對不平衡設計的小階 數(shù)例子，并給出滿足一定條件的嚴格成對不平衡設計的小階數(shù)例子 第五章總結(jié)了第一、二、三、四章的內(nèi)容，并給出了最新結(jié)果以及今后的 研究前景 關(guān)鍵詞：s a r v a t e b e a m 設計；成對不平衡設計；成對不平衡可分組設計；嚴格成對 不平衡設計；構(gòu)造 分類號：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 學位論文版權(quán)使用授權(quán)書 本學位論文作者完全了解北京交通大學有關(guān)保留、使用學位論文的規(guī)定。 特授權(quán)北京交通大學可以將學位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫進行檢 索，并采用影印、縮印或掃描等復制手段保存、匯編以供查閱和借閱。同意學 校向國家有關(guān)部門或機構(gòu)送交論文的復印件和磁盤。 ( 保密的學位論文在解密后適用本授權(quán)說明) 學位論文作者簽名：馬書留旅少 簽字日期：峙年占月節(jié)日 導師簽 簽字日期：堿翻怕 獨創(chuàng)性聲明 本人聲明所呈交的學位論文是本人在導師指導下進行的研究工作和取得的 研究成果，除了文中特別加以標注和致謝之處外，論文中不包含其他人已經(jīng)發(fā) 表或撰寫過的研究成果，也不包含為獲得北京交通大學或其他教育機構(gòu)的學位 或證書而使用過的材料。與我一同工作的同志對本研究所做的任何貢獻均已在 論文中作了明確的說明并表示了謝意。 學位論文作者簽名：弓七釩簽字日期：砌壯6 月牛日 致謝 本論文的工作是在我的導師常彥勛教授的悉心指導下完成的，在論文選題、 研究、定稿的過程中，常老師自始至終給了我大力的支持和無私的關(guān)懷感謝我 的導師，他嚴謹細致、一絲不茍的作風一直是我工作、學習中的榜樣，他循循善 誘的教導和不拘一格的思路給予我無盡的啟迪無論是在科研上，還是在平時的 生活中，他都給了我無微不至的關(guān)懷與鼓勵他嚴謹?shù)闹螌W風格，廣博的知識，精 益求精的科研作風，敏銳的學術(shù)思想和忘我的工作精神影響并鞭策了我，是我今 后生活與工作中一筆極大的財富，在此謹向常老師表示深深的感謝 感謝馮駛師兄對我的幫助和指點，無論是在平時的學習，還是在論文的寫作 中，他都給我提出了很多寶貴建議，在此向馮師兄表示真誠的感謝此外，在撰寫 論文期間，周君靈、常相茂、吳艷、i d , 苗、陳琦、王昭、李靖塵、林偉偉等師 兄師姐都給予我熱情的幫助，我也從中學到很多知識，在此向他們表達我的感激 之情 最后，感謝各位專家和學者在百忙中審閱我的論文，并給出批評意見回首兩 年的研究生生活，自己的每一步前進，都離不開老師、親朋和同學的支持與教誨， 在此表達我對他們最衷心的感謝! 北京交通大學碩士學位論文 第1 章緒論 1 1 背景介紹 第1 章緒論 在組合設計中，大家熟知平衡不完全區(qū)組設計( y ，b ，r , k ，a ) 設計作為該類 設計的一個推廣，如果用整數(shù)集k - - i k l , 如，島，k l 代替k ，我們可以得到成 對平衡設計( y ，b ，墨a ) 一設計平衡不完全區(qū)組設計和成對平衡設計的概念均 可參見文章【1 1 、【2 】和【3 1 如果我們從另一種角度推廣平衡不完全區(qū)組設計，保 持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 。】) 一設計，對相關(guān)問題做了初步研究，并得到一些結(jié)論 我們考慮集合v = 1 ，2 ，3 ，4 l 上的一個設計，該設計的7 個區(qū)組為： 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 上的所有元素對出現(xiàn)的次數(shù)是 不相同的，這個特點正好與平衡不完全區(qū)組設計相反，而且我們發(fā)現(xiàn)對于所 有江l ，2 ，3 ，4 ，5 ，6 ，集合v = 1 1 ，2 ，3 ，4 上恰好存在一個元素對出現(xiàn)的次數(shù)是i 這 種新類型設計引起一些學者的注意 s a r v a t e 和b e a m 在文章【6 】中引入這種新類型設計，稱作a d e s i g n ，他們給出 一些嚴格和不嚴格的區(qū)組長度為3 的a d e s i g n s 的例子，并指出嚴格的區(qū)組長度 為3 的a d e s i g n s 存在的必要條件是1 ，三0 ，l ( m o d3 ) 并且v 3 ，同時在文章【7 】中 給出該類設計的一些推廣和相關(guān)結(jié)論s t a n t o n 在文章【8 】中把嚴格的區(qū)組長度 為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 三元系的小 階數(shù)例子對于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 】中給出嚴格的區(qū)組長度為4 的a d e s i g n s 存在 的必要條件和小階數(shù)例子一些滿足一定條件的s a r v a t e - b e a m 三元系和區(qū)組長度 為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 三元系存在的 必要條件是否也是充分的本文基于以上背景，對這種新類型的設計做了進一步 的探討，建立了基本構(gòu)造方法，并證明了s a r v a t e b e a m 三元系存在的必要條件也 是充分的為了與傳統(tǒng)成對平衡設計的概念相一致，我們用了不同的術(shù)語，分別用 成對不平衡設計和嚴格成對不平衡三元系取代了a d e s i g n s 和s a r v a t e b e a m 三元 系 以下是新類型設計的基本概念和已有結(jié)論 北京交通大學碩+ 學位論文 第1 章緒論 1 2 基本概念 假設k 為給定的正整數(shù)集，并且a 。，a 2 ，厶是互不相同的正整數(shù) 定義1 2 1 一個( ，k ，【五l ，a 2 ，a 蝌】) 一設計是一個二元組( x ，男) ，滿足以下條件： ( 1 ) x 是一個v 元集； ( 2 ) 召是x 的子集族，$ 中的元素稱為區(qū)組，并且對v b 易，都有ibl k ； ( 3 ) x 中每個元素對恰好出現(xiàn)在某 ( 1 i m ) 個區(qū)組中； ( 4 ) 對于每個丑( 1 f m ) ，x 中至少存在一個元素對恰好出現(xiàn)在丑個區(qū) 組中 如果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 中的任意兩個元素對在區(qū)組中 出現(xiàn)的次數(shù)都不相同，我們稱這種設計為成對不平衡設計，記作p d d ( v ，1 0 定義1 2 3 在成對不平衡設計中，對于每個1 f v ( v 一1 ) 2 ，如果x 中恰好存在 一個元素對出現(xiàn)在某f 個區(qū)組中，則該成對不平衡設計被稱作嚴格成對不平衡設 計，記作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 ，一個( 嚴格) 成對不平衡設計被稱作區(qū)組長度是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 元不平衡設計的 相關(guān)定義 定義1 2 4 如果x 中的任意兩個f 元子集在區(qū)組中出現(xiàn)的次數(shù)都不同，則得到f 元 不平衡設計，記作t - d d ( v ，的如果該設計是嚴格的，則將其記作t - s d d ( v ，1 0 如果每個元素在區(qū)組中出現(xiàn)的次數(shù)都不相同，則可以得到1 - d d ( v ，k ) 值得注 意的是，如果t = 2 ，此時x 中的任意兩個元素對在區(qū)組中出現(xiàn)的次數(shù)都不相同，即 為前面定義的p d d ( v ，i o 有時我們需要考慮設計在同構(gòu)意義下的個數(shù)，因此我們引入兩個設計同構(gòu)的 定義 2 北京交通大學碩+ 學位論文 第1 章緒論 定義1 2 5 設計d 和礦被稱作是同構(gòu)的，如果存在一個從d 到的一一映 射，滿足： 妒：而_ # = 似置) ； 馬一巧= ( 乃) 其中而和葛分別是d 和d 中元素，毋和巧分別是d 和d 中的區(qū)組，此 時而島當且僅當( 而) 妒( 口) 為方便，我們有下面定義 定義1 2 6 假設( x ，囝是一個成對不平衡設計，則x 中元素對在區(qū)組中出現(xiàn)的次 數(shù)被稱作對子的次數(shù)，所有對子的次數(shù)的最大數(shù)被稱作對子的最大次數(shù) 因此設計s p d d ( 1 ，目中對子的最大次數(shù)是v ( v 一1 ) 2 1 3 已有結(jié)論 引理1 3 1 6 1s p d t s ( v ) 存在的必要條件是v 3 并且1 ，蘭0 ，1 ( r o o d3 ) 證明：當k = 3 時，每個區(qū)組中元素對的總數(shù)是3 ，s p d t s ( v ) 中所有對子的次數(shù) 的總數(shù)為： 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 ) 必成立經(jīng) 計算可知結(jié)論成立 口 引理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 時，每個區(qū)組中元素對的總數(shù)是6 ，s p d d ( v ，4 ) 中所有對子的次數(shù) 的總數(shù)為： 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 的同余類，經(jīng)計算有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 ) ，因此結(jié)論得證 口 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 ，良) 的區(qū)組個數(shù)一定是整數(shù)，因此第一個條件容易得 證對于1 - s d d ( v ，七) ，恰好存在一個元素在區(qū)組中出現(xiàn)次數(shù)為k 每個元素在某個 區(qū)組中出現(xiàn)的次數(shù)至多是1 ，并且設計具有v ( v - i - 1 ) 2 k 個區(qū)組， j y v ( v + 1 ) 2 k j k v ( v + 1 ) 2 v 毒ks ( y + 1 ) 2 另一方面，為證充分性，我們給出構(gòu)造設計1 - s d d ( v ，幼的一個算法，不妨令所 構(gòu)造設計具有b = v ( v + 1 ) 2 k 個區(qū)組令v = 1 ，2 ，1 ， ，不失一般性，我們假定元 素i 出現(xiàn)的次數(shù)為f 假定所構(gòu)造設計1 s d d ( v ，勛中的區(qū)組為風，口1 ，島，既- l 將元素1 放置在區(qū)組風中，然后將元素2 放置在區(qū)組b l 和曰2 中，依次類推， 不妨假定元素f 一1 所放置在區(qū)組中的最后一個是曰；- l ，則將元素i 放置在區(qū) 組曰，b + l ，b + 2 ，局+ 1 中，其中下標是模b 后的值第一個條件可以保證所構(gòu) 造的區(qū)組長度為k 由第二個條件可以得知，以此法構(gòu)造的區(qū)組不是多重集 k ( y + i ) 2 = k v ( v + 1 ) 2 v = j y v ( v + 1 ) 2 k 因此，以該算法構(gòu)造的設計，任何一個元素在某個區(qū)組中出現(xiàn)的次數(shù)最多為1 ， 并且每個元素在區(qū)組中出現(xiàn)的次數(shù)均不相同 口 引理1 3 4 】乒j d d ( v ，j i ；= ) 存在的必要條件是( 譬) i ( ；) ( ( ￥) + 1 ) 2 證明：設計乒s d d ( v ，七) 中的每個區(qū)組包含g ) 個f 一子集，點集y 上共有( ：) 個f 一子 集，并且該設計中t 子集出現(xiàn)次數(shù)的總數(shù)為： 1 + 2 + + g ) = ( ￥) ( ( ；) + 1 ) 2 若凇d d ( v ，d 存在，必有e ) 整除( ￥) ( ( ；) + d 2 ，因此結(jié)論得證 4 口 北京交通火學碩士學位論文第1 章緒論 下面是關(guān)于 一2 ) 一d d ( n ，挖一1 ) 存在性問題的相關(guān)結(jié)論，其證明可參見文章 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 章構(gòu)造方法 第2 章構(gòu)造方法 這部分主要介紹了三種基本構(gòu)造方法，這些構(gòu)造是我們解決成對不平衡設計 的主要方法，對本文第三章主要結(jié)論的證明非常有用在建立基本構(gòu)造方法的過 程中，我們需要用到一些輔助設計，因此首先介紹輔助設計的基本概念，然后具體 給出加權(quán)構(gòu)造、p b d 一構(gòu)造及填充子設計構(gòu)造，并給出構(gòu)造的證明 2 i 基本概念 假設k 為給定的正整數(shù)集，a 為給定的正整數(shù) 定義2 1 i 一個( k a ) 可分組設計( 或者( k ，a ) 一g d d ) 是一個三元組( x 莎，固，滿 足以下四個條件： ( i ) 莎是x 的一個劃分，眵中的元素稱為組； ( 2 ) 貿(mào)是x 的子集族，舅中的元素稱為區(qū)組，并且對v a 舅，都有l(wèi)ai k ； ( 3 ) 對v a 貿(mào)和y g 紗，都有ia ngl i ，即任意的組和區(qū)組最多只有一個 公共點： ( 4 ) x 中屬于不同組的任意一對元素恰好出現(xiàn)在a 個區(qū)組中 特別地，如果i = i ，我們可將( 墨1 ) 一g d d 簡記為k g d d 假設設計( 墨a ) g d d ( x , g ，習) 的組為i ig l ：g 夠1 對于i f j ，如果鑼中 有蜥個大小為戤的組，我們可以用“指數(shù)”形式來描述該設計的組，此時可以 稱( x ，紗，舅) 是一個組型為硝1 9 世的g d 設計如果k = ，我們可用k 代 替置 定義2 i 2 一個組型為i ”的( 噩a ) ，g d d 被稱作成對平衡設詵記作( v ，k ，a ) p b d 當k = 時，成對平衡設計被稱作平衡不完全區(qū)紐設計，記作( 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 時，不完全成對平衡設計被稱作不完全平衡不完全 區(qū)紐設計，記作( 1 ，h ；k ，1 ) 一i b i b d 以上設計中，如果參數(shù)a = i ，可將其省略 6 北京交通大學碩士學位論文第2 章構(gòu)造方法 定義2 1 4 一個成對不平衡可分紐設計( 或者p d g d d ) 是一個三元組( x ，侈，舅) ， 滿足以下四個條件： ( 1 ) 紗是x 的一個劃分，莎中的元素稱為組； ( 2 ) 貿(mào)是x 的子集族，用中的元素稱為區(qū)組，并且對v a , 7 1 ，都有l(wèi)ai k ； ( 3 ) 對y a 舅和y g 多，都有l(wèi)angl 1 ，即任意的組和區(qū)組最多只有一個 公共點： ( 4 ) x 中屬于不同組的任意兩對元素在區(qū)組中出現(xiàn)的次數(shù)都不相同 假設p d g d d 的組是集合 i g i ：g g l ，正如g d d s 。我們也可以用“指數(shù) 形式描述p d g d d s 的組型 定義2 1 5 假設p d g d d 中屬于相同組的元素對的總數(shù)是跖，對于每個1 f v ( v 一1 ) 2 一u ，如果x 中恰好存在一對來自不同組的元素出現(xiàn)在某i 個區(qū)組中， 則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 中的元素出現(xiàn)在f 個區(qū)組中，則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 ，坳正如對成對不平衡設計的對子次數(shù)，最大次數(shù)的定義，我們可以類 似地定義p d g d d 和i p d d 的對子的次數(shù)和最大次數(shù) 2 2 基本構(gòu)造 下面的構(gòu)造簡單但非常有用，三個基本構(gòu)造可以看作是文章【1 2 】中w i l s o n 基 本構(gòu)造的變形 構(gòu)造2 2 1 ( 加權(quán)構(gòu)造) 假設k 和l 是正整數(shù)集，假設( x ，繆，貝) 是一個區(qū)組為貝= ，a 2 ，a m 的k - g d d ，并且設山：xhz + u o j 0 是x 上的權(quán)函數(shù)對于 每個工x ，設s ( 力是以曲個不同x 的復制的集合對于每個1 f m ，假 設( u 礎(chǔ)；s ( 曲，l s ( x ) ：工a 兒甄；) 是一個具有對子的最大次數(shù)為 的厶p d g d d ， 對于每個2 f 歷，如果( u 剛，s ( 力，博( 力：工a f j 易：) 是一個( l ，e i - la ，、g d d ， 則( u 硝s ( 曲，l u 疆a(chǎn) 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 章構(gòu)造方法 證明：根據(jù)假設，( x ，夠，舅) 是一個區(qū)組為貿(mào)= i a l ，a 2 ，a m j 的k - g d d 對于每個2 f ，z ，存在一個具有對子的最大次數(shù)為丑的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 群，) 是一個對子的次 數(shù)為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 構(gòu)造可以看作是構(gòu)造2 2 1 的推論 構(gòu)造2 2 2 ( p b d 一構(gòu)造) 假設k 和l 是正整數(shù)集，假設( x ，舅) 是一個具有區(qū)組 為貝= i a l ，a 2 ，a m 的( v ，k ，1 ) p b d 對于每個1 ism ，假設( a ，玩。) 是 一個具有對子的最大次數(shù)為 的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 也是嚴格的 證明：根據(jù)假設，( x 翻) 是一個具有區(qū)組為7 i = l ，a 2 ，a m j 的( ，匠1 ) 一p b d 對于每個2sf m ，( a f ，玩，) 是一個具有對子的最大次數(shù)為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 緩；) 是一個對子的次數(shù)為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 也是嚴格的 口 構(gòu)造2 2 3 ( 填充子設計構(gòu)造) 假設置和是正整數(shù)集，設h 是一個非負正整 數(shù)，假設( x ，夠，兩是一個組為夠= i g l ，g 2 ，q l 的k p d g d d ( 稱為主設計) ， 并且該設計中對子的最大次數(shù)為a 假設p d d ( i g i + h ，d 存在，并且對于每 個1 i n i ，存在一個對子的最大次數(shù)為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 章構(gòu)造方法 并且對于每個lsf 路一l ，如果需要用到的子設計i p d d ( i g i _ i + ，如；d 也是嚴格 的，則最終設計p d d 也是嚴格的 證明：假設日是一個h 元集，并且h n x = 0 ，根據(jù)假設，組為妙= i g i ，g 2 。，g 。l 的 設計k - p d g d d ( 五莎，網(wǎng)存在，并且對子的最大次數(shù)為 對于每個1 i 療一1 ，假設( g j f u h ，1 - 1 , 霸) 是一個具有對子的最大次數(shù)為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 男l(wèi)u 男；) 是一個i p d d ( i g l i + | l l ，j l ；d ，其中對子的次數(shù) 為( 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 ) ，其中對子的次數(shù)為i t ： 五+ ；j a ，+ 1 t a + e i ，- i a ，j 根據(jù)題中假設可知，( g ，統(tǒng)) 是一個p d d ( i g n i + ，l ) ，并且( gu 兒域) 是一 個( i g 。i + 辦，l ，a + n f - - 1 i l 少p b d ，則( guh ，統(tǒng)u 甄) 是一個p d d ( i g 。i + 死l ) ，其中 對子的次數(shù)為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 構(gòu)造中用到的結(jié)論 下面幾個引理對本文第三、四章結(jié)論的證明很有用 引理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 勺存在性 這一章主要探討嚴格成對不平衡三元系的存在性問題，首先給出小階數(shù)例子， 然后利用基本構(gòu)造方法和輔助設計得到本文的主要結(jié)論 為方便，下面我們用r a ，b ，c l 表示區(qū)組l 口，b ，c l 出現(xiàn)，次用字母f 表示次數(shù)， 則，( i 工，y 1 ) 表示元素對 z ，) ，j 出現(xiàn)的次數(shù)，f ( i 石，y ，z d 表示區(qū)組( z ，y ，z j 出現(xiàn)的次 數(shù) 3 1 小階數(shù)例子 引理3 1 1 8 1s p d t s ( 4 ) 存在 證明：假設元素對1 1 ，2 j 出現(xiàn)的次數(shù)為1 ，不妨假設出現(xiàn)在區(qū)組1 1 ，2 ，3 j 中 當v = 4 時，設計中共有6 個元素對，對子出現(xiàn)次數(shù)的總數(shù)為：1 + 2 + 3 + 4 + 5 + 6 = 2 1 對于長度為3 的區(qū)組，每個區(qū)組提供3 個元素對，因此該設計中共 有2 1 3 = 7 個區(qū)組，此時我們可以假設有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 因此唯一的可能結(jié)果是a = 2 ，b = 4 ， 可以得知在同構(gòu)的意義下，該設計是唯一存在的 可以將元素對出現(xiàn)的次數(shù)列為下表： 元素對1 1 , 2 1 ，4 1 1 , 3 2 ，4 j1 2 ，3 j1 3 ，4 i 出現(xiàn)的次數(shù) 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 根據(jù)構(gòu)造過程可以得到下面一個引理 引理3 1 2 s ls p d t s ( 4 ) 在同構(gòu)的意義下是唯一存在的 引理3 1 3 【8 】當，= 6 ，7 時，s p d t s ( v ) 存在 1 0 口 北京交通火學碩十學位論文第3 章s p d t s 的存在性 證明：當v = 6 時，設計中共有1 5 個元素對，對子出現(xiàn)次數(shù)的總數(shù)為：i + 2 + + 6 ( 6 1 ) 2 = 1 2 0 ，因此該設計共有1 2 0 3 = 4 0 個區(qū)組，不妨假設區(qū)組出現(xiàn)的次數(shù) 為： 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 因此我們可以得到對子出現(xiàn)次數(shù)為： 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 - +