（运筹学与控制论专业论文）临近点不出现的平衡设计.pdf

摘要 考虑一个有序的有限集合，它包含”个可识别的个体，分别标记为0 ， 1 ，”一1 令；表示个体f 的数量特征，我们可以通过对个体i 的观察 得到厶我们取出( k 。) 个个体做成一个样本，同时对后个个体的数量 特征进行观察来得到此样本信息利用抽样调查，我们可以估计总体特征 t = 。v 。- - i 。在实际应用中，相邻个体的数量特征常常是相似的，因 而我们期望元样本中相邻个体同时出现的频率要很小h e d a y e t ，r a o 和 s t u f l n 在1 9 8 8 年从h o r v i t z - t h o m p s o n 估计量的角度证明了这种思想的合理 性并且提出了不舍相邻点的平衡样本设计( b a l a n c e ds a m 幽g p l a ne x d u d i n g c o n t i g u o u su n i t s 简写作b s e c ) 的存在问题 令x = s o ，z 1 ，岛一1 1 如果和研l 称作是相邻的点，其中0 i ”一2 ，址。和跏也称作是相邻的，那么称x 为循环有序的， 设x 是循环有序的”元集，b 是x 的一些缸子集( 称为区组) 构成的 集合若二元组( x ，功满足；任意两个相邻点不在任何区组中出现，而任 意两个不相邻的点恰出现在a 个区组中，则称( 置聊为一个不含邻点的_ | 长平衡样本设计，记为b s e c ( ，k ，a ) h e d a y a t ，r a o 和s t u l k e n ( r o s s 年) 证明了k = 3 ，4 时，如果口3 k ，则 存在某个 使b s e c ( v ，k ，a ) 存在s t u f k e n 和w r i g h t ( 2 0 0 1 年) 证明了如果 k = 5 ，6 ，7 且k = 7 时口2 2 ，b s e c ( ，k ，柚对于某个a 存在的充分必要条件 是”3 k + 1 但上述结果中参数a 的值随着点数”的增加增长的很快， 而我们一般希望一个设计的区组少一些，从而a 小一些c o l b o u m 和l i n g 对给定的 进行考虑，分另4 在1 9 9 8 年和1 9 9 9 年证明了b s e c ( ，3 ，a ) 存在 的充分必要条件和b s e c ( ，4 ，a ) 存在的充分必要条件 s t u i k e n ( 1 9 9 3 年) 将b s e c 的概念推广到邻近点不出现的平衡设计( b a l - a n c e ds a m p l i n gp l a nt oa v o i dt h es e l e c t i o no fa d j a c e n tu n i t s 简写作8 s a ) 设x 是循环有序的”元集，b 是x 的一些缸子集( 称为区组) 构成的 集合若二元组( x ，艿) 满足：任意两个距离小于等于a 的点不在任何区组 i i i 摘要 中出现，而任意两个距离大于o t 的点恰出现在a 个区组中，则称( x ，聊为 一个邻近点不出现的平衡样本设计，记为b s a ( v ，女， ；n ) 显见，b s a ( v ，女，a ；o t ) 在口= 1 时即为b s e c ( v ，i ，a ) 设磊= o 1 ，口一l 表示口阶循环群，( 置印是一个b s b c ( v ， ，a ) ( b s a ( 七，n ) ) 若磊是b s i c ( v ，七， ) ( b s a ( v ，i ， ；n ) ) 上的一个自同构 群，那么我们称( x ，b ) 是循环的，记为c b s e c ( v ，a ) ( c b s a ( v ，e ，a ；口) ) w e i ( 2 0 0 2 年) 得到了a = l ，2 时c b s e c ( v ，3 ，a ) 存在的充分必要条件并 且得到了a = 1 ，2 时c b s a ( v ，3 ，知的一些存在结果 在本文中，我们证明了6 b s e c ( v ，3 a ) 对任意 存在的充分必要条件， 得到了c b $ a ( v ，3 ，凡a ) 和b s a ( v ，3 ，是在n = 2 ，3 , 4 时存在的充分必要条 件，并得到了c b s e c ( v ，4 ，1 ) 的一些初步的存在结果主要结论如下t ( 1 ) c b s e c ( v ，3 ，a ) 存在的充分必要条件是t ， 1 ，3 ，p 9 且 扣一3 ) i 0 ( m o d6 ) ，但当a 兰2 ( m o d4 ) 时口2 ( 珊d d4 ) ( 2 ) 当n = 2 ，3 ，4 时，c b s a ( 口，3 ， ；口) 存在的充分必要条件是口3 ( 2 a + 1 ) ， 知扣一勉一1 ) 量0 ( m o d6 ) ，a 扣一孙一1 ) 兰0 ( m o d2 ) ，但当a 毫2 ( 脚d4 ) 时 口2 ( m o d4 ) ，当n = 2 且a = 1 时，t ，3 ( m o d6 ) ( 3 ) 口= 2 ，3 ，4 时，b s a ( v ，3 ，a ；o ) 存在的充分必要条件是j l v ( v 一2 口一1 ) 兰 0 ( m o d6 ) ，a 扣一2 a 一1 ) i0 ( m o d2 ) 且口3 ( 2 a + 1 ) ( 4 ) 存在一个c b s e c ( a v ，4 1 ) ，这里8 3 ，2 7 , 6 3 ，9 9 ，1 7 1 ，2 0 7 2 4 3 ，t ，是 q 中若干个数的乘积，q = 伽：p ；1 ( r o o d4 ) 并且p 是素数 u 口：q 兰 1 ，5 ( m o d1 2 ) ，g l 印 全文共分为6 章： 第一章在这一章中，我们介绍了相邻点不出现的平衡设计用于抽样 调查的背景，给出了相邻点不出现的平衡设计的定义和一些已知结果 第二章在这一章中，我们介绍了l a n g f o r d 序列和k - e x t e n d e dl a n g f o r d 序列，并给出了这些特殊序列的一些性质，这在构造c b s e c ( ”，3 ，a ) 和 c b s a ( v ，3 ，a ；n ) 时有重要的作用我们还给了两个引理，这有利于后面来 证明b s a ( v ，a ；q ) 存在的必要条件 第三章本章，我们应用l a n g f o r d 序列来划分一个连续的序列，从而得 摘要 到一些差三元组最后我们得到了c b s e c ( v ，3 ， ) 存在的充分必要条件 第四章在这章中，我们利用l a 耐o r d 序列和k - e x t e n d e d l a n g f o r d 序列来 分拆序列，通过适当的搭配得到了一些差三元组，最终得到了当o = 2 ，3 ，4 时c b s a ( v ，3 ，凡n ) 存在的充分必要条件 第五章我们利用辅助设计b s a * ( g ， 2 ，3 ，a ；a ，) ，组型为( g ，2 d + l p 的3 _ i g d d 和一些小阶数的b s a ( 9 + t ，3 ，a ；n ) 与b s a ( ( 2 a + i ) u ，3 ，知口) ，得到了对于 b s a ( 9 u + t ，3 ，凡q ) 的递归构造从而得到了当o = 2 ，3 ，4 时，b s a ( v ，3 ，知口) 存 在的充分必要条件本章中用到的一些小阶数的b s a ( g + t ，3 ，扯口) ，b s a ( ( 2 a + 1 ) ，3 ， ；d ) 和b s a * ( g ， 2 ，3 ，凡q ) 是通过计算机搜索得到的 第六章我们介绍了一种所谓的可划分集合的组合结构，它是阶数是 t ，( 兰1 ( m o d4 ) ) 的阿贝尔群g 上的一些无序的对子组成的集合“q ，如 ： 1 i 扣一1 ) 4 满足：u 譬1 ) 一 士啦，士堍) = g o 和l 瑶( v - 1 1 ) ，4 仕( 啦+ 如) ， 士( 啦一6 i ) = g o 我们利用可划分集合和差阵得到了c b s e c ( v ，4 ，1 ) 的 两个递归构造，从而得剜了c b s e c ( v ，4 ，1 ) 的一些初步的存在结果 关键词：相邻点不出现的平衡设计；邻近点不出现的平衡设计；不完全 可分组设计；l a a g f o r d 序列；k - e x = t e n d e di a x n g f o r d 序列；可划分集合； b s a + 扣，k ，a ；o ，f ) ；差阵；自同构群 e x t e n d e da b s t r a c t c o n s i d e raf i n i t eo r d e r e dp o p u l a t i o no f 口i d e n t i f i a b l eu n i t s ，l a b e l e da s0 ，1 ， 口一1 l e t fd e n o t eaq u a n t i t a t i v ec h a r a c t e r i s t i c f o ru n i ti w h i l et h ea i sf o r as a m p l eo fku n i t sa tat i m e ，f o rk 3 ，t h e n 口3 k ( 2 ) f o r 七= 3 ，4 ，ab s e c ( v ，k ，柚e x i s t s o r 卯胱a 矿口3 k s t u f k e na n dw r i g h t ( 3 9 1 ) e s t a b l i s h e dt h ef o l l o w i n g ： t h e o r e m1 2 2f o r 七= 5 ，6 ，7 ，ab s e c ( v ，k ，a ) e x i s t sf o rs d m ea 矿a n do n l y f 掣23 k + 1 埘执t h ee x c e p t o no ( 七，口) = ( 7 ，2 2 ) 7 i l ms o l u t i o ni nt h ea b o v et h e o r e m sg i v ev a l u e so fat h a to r ev e r yl a r g e w h i l e o n et y p i c a l l yp r e f e r sd e s i g n sw i t hf e wb l o c k sa n dh e n c es m a l l e rv a l u e so fa i nt h e s a m p l i n gc o n t e x t t h ep a r t i c u l a rv a l u eo fam a y b el e s si m p o r t a n tt h a nt h ee a s ew i t h w h i c hb l o c k sc a nb es e l e c t e d h o w e v e r d e s i g n sw i t hs m a l l e rar e q u i r el e s ss t o r a g et o r e p r e s e n te x p l i c i t l yf o rt h i sp u r p o s e c o l b o u ma n dl i n g ( f 9 ，1 0 ) c o m p l e t e l ys o l v e dt h ec a s ef o rb m a n c e ds a m p l i n gp l a n s w i t has a m p l es i z eo ft h r e eu n i t sw i t hf i x e da t h ea u t h o r sd e v e l o p e dan u m b e ro f s m a l lc y c l i ca n db i c y c l i ed e s i g n sa n dp r o v i d e dar e c u r s i v ec o n s t r u c t i o nm e t h o df o r l a r g e rd e s i g n s t h r o u g hf t l r t h e ri n v e s t i g a t i o n ，t h ea u t h o r sw e r ea l s oa b l et oc o n s t r u c t a l lb a l a n c e ds a m p l i n gp l a n sw i t has a m p l es i z eo ff o u ru n i t s 3 c h a p t e r1 i n t r o d u c t i o n t h e o r e m1 2 3 ( c o l b o u ma n dl i n g 【9 j ) ab s e c ( v ，3 ，a ) e z l s t s 矿a n do 以西i ， f o ，3 ) ，o r 9a n da 0 3 ) i 0 ( m o d6 ) t h e o r e m1 2 4 ( c o l b o u r na n dl i n g 【x 0 ) ab s e c ( v ，4 ，a ) e x i s t s 矿a n dd 砌矿 口 o ，3 ，o r ”1 2a n da v ( v 一3 ) 三0 ( m o d1 2 ) w i t ht h en oe x i s t c n e x c e p t i o n b s e c ( 1 2 ，4 ，1 ) h e d a y a ta n ds t u f k e n ( 2 0 1 ) p r e s e n t e daw a yo fe x t e n d i n gt h ei d e ao fb a l a n c e d s a m p l i n ge x c l u d i n ga d j a c e n tu n i t st ot w o - d i m e n s i o n a lp o p u l a t i o n sb yu t i l i z i n go n e - d i m e n s i o n a lb a l a n c e ds a m p l i n gp l a n se x c l u d i n ga d j a c e n tu n i t s m o r ei n f o r m a t i o na n d r e s u l t so nt w o - d i m e n s i o n a lb a l a n c e ds a m p l i n gp l a n se x c l u d i n gc o n t i g u o u su n i t s ，t h e r e a d e ri sr e f e r r e dt o 【2 ，1 6 1 s t u k e ng e n e r a l i z e dt h ec o n c e p to fb s e ct ot h a to fab a l a n c e ds a p i i n gp l a nt o a v d i dt h es e l e c t i o no fa d j a c e n tt m i t s ( o rb s a f o rs h o r t ) i n 【3 7 】，a n dg a v et h e 雠a 哦n g d e f i n i t i o n d e f i n i t i o n1 2 1ak - s i z e db a l a n c e ds a m p l i n gp l a na v o i d i n gm 哲删u n i t si sdp a i r 研，w h e r ex = 磊a n db 妇dc o l l e c t i o nd ，k - s u b s e t s 口，x “矧b l o c k s , s u c ht h a t 御p a i r 彭p o 跑t sg ，茆a p p e a r s 娩a n yb o c k 矿i j 三圭l ，土口( m o d 坊，w h i l e a n yd 趾rp a i rd ，p o i n t sa p p e a r s nb 纰c 咖ab o c k s w ew i l ll l 辩t h en o t a t i o nb s a ( v ，后，a ；n ) t od e n o t es u c had e s i g n t h ec a s e q = 0m a yb et h o u g h to fa ss i m p l er a n d o ms p l i n gw i t h o u tr e p l a c e m e n t ，w h i l e a = 1c o r r e s p o n d st oab s e c ( v ，k ，a ) l e t 磊= o ，1 ，口一1 ) d e n o t e t h ec y c l i ca d d i t i v eg r o u po f o r d e r v 磊i s a l l a u t o m o z p h i s mo fb s e c ( v ，k ，a ) ( b s a ( v ，k ，a ；口) ) ，t h e nw ec a l li tac y c l i cb s e c ( b s a ) a n dd e n o t ei ta sc b s e c ( v ，k ，a ) ( c b s a ( ，k ，凡n ) ) w e i ( 【4 1 】) d i s c u s st h ec y c l i cb s e ca n do b t a i nt h en e c e s s a r ya n ds u f f i c i e n tc o n d i - t i o n sf o rt h ee x i s t e n c eo fc b s e c ( ，3 ，a ) w i t ha = 1 ，2a n do b t a i ns o m ee x i s t e n c e r e s u l t so nc b s a ( v ，3 ，a ；o r ) w i t h 入= 1 ，2 n o t et h a tt h ec o n d i t i o n sf o rt h ee x i s t e n c e o fc b s e ca r es t r o n g e rt h a nt h o s eb s e c f o rc e r t a i np a r a m e t e r s ，ab s e ce x i s t s w h i l e2 1 c b s e cd o s en o t w ea r ei n t e r e s t e di nc b s e cb a s i c a l l yb e c a u s eo ft h e i r 4 1 3 m a i nr e s u l t s g o o da l g e b r a i ca n dt h e i ra d v a n t a g e si ns u r v e ya p p l i c a t i o n s i n c ei ti sm u c he a s i e rt o c h o o s ear a n d o mb l o c ki nac b s e ct h a ni nan o n - c y c f i cb s e c t h e o r e m1 2 5 ( w e i | 4 1 】) l e t 口9 ，ac b s e c ( v ，3 ，1 ) e x i s t s 妒a n do n l y 矿 口三3 ( m o d6 ) ，a n dac b s e c ( v ，3 ，2 ) e 2 i s t s 旷a n do n l yi f v 兰o ，3o r 9 ( m o d1 2 ) t h e o r e m1 2 6 ( w e i 4 1 1 ) ( 1 ) t h e r ee x i s t snc b s a ( 6 t + 2 a + 1 ，3 ，1 ；a ) 如rn ：f i n t e g e r t 2 a + 1 ( 2 ) t h e r ee x i s t snc b s a ( v ，3 ，2 ；口) ，d rt h ef o t t o 埘n gv a l u e s0 1 口a n d o t ： i ) 口妇c v e n ， = 1 2 t + 2 a + 4a n d t 22 a + l ； i i ) o t so d d , ”= 1 2 t + 2 0 + 1 0a n d t 2 a + 1 ； i i i ) a n yo t 1 ， = 6 t + 2 a + 1a n d t2 2 a + 1 1 3 m a i nr e s u l t s w h i l ea d v a n c e m e n t sh a v eb e e na c h i e v e dt h r o u g ht h ey e a r s ，t h e r ea l ean u m b e ro f a s p e c t si n v o l v i n gs a m p l i n gp l a n se x c l u d i n ga d j a c e n tu n i t st h a tn e e df u r t h e ri n v e s t i - g a t i o mw i t h i nt h i st h e s i s ，c o n s t r u c t i o nt e c h n i q u e sw i l lb ep r e s e n t e df o ro b t a i n i n g b a l a n c e ds a m p l i n gp l a n sa v o i d i n ga d j a c e n tt m i t sf o ro n e - d i m e n s i o n a lp o p u l a t i o n s w eu s el a n g f o r d 舶q u e n c * 8t od i v i d ea 【2 ，口一2 1i n t ot r i p l e s 皿，趣，q ) ，1 i a v ( v 一3 ) 6 ，s u c h t h a tn + 趣= c i b y l e m m a 2 1 1 ， o ，啦，c ) ：1 i a 0 3 ) 6 a r e a l l t h e b a s e b l o c k s o f a c b s e u ( v ，3 ，a ) t 胁耽g e t t h e 埘皤鞠r y a n ds u f f i c i e n t c o n d i t i o n sf o rt h ee x i s t e n c eo fac b s e c 扣，3 ，a ) t h e o r e m 3 3 2t h e n e c e s s a r y a n d s u f f w i e n tc o n d i t i o n s f o r t h ee x i s t e n c eo f a c b s e - c 扣，3 ，a ) d 佗e i t h e r v 1 ，3 ，d r 口9a n d a ( v - 3 ) 三0 ( m o d6 ) b u t 2 ( m o d4 ) w h e na 兰2 ( r o o d4 ) w e 嘴l a n g f o r ds e q u e n c e sa n dk - e x t e n d e dl a n g f o r ds e q u e n c e sp r o p e r l yt od i v i d e a 1 2 ， 一2 】i n t ot r i p l e s a i ，魄，q ) ，1 i a v ( v 一2 a 一1 ) 1 6 ，s u c ht h a tm + b i = g b yl e m m a2 1 1 ， o ，a i ，c i ) ：1 isa v ( v 一2 a 一1 ) 6 o l et h eb a s eb l o c k so f ac b s a ( v ，3 ，a ；n ) t h e nw eg e tt h en e c e s s a r ya n ds u f f i c i e n tc o n d i t i o n sf o rt h e e x i s t e n c eo fa c b s a ( v ，3 ，a ；n ) w i t ho t = 2 ，3 ，4 c h a p t e r1 i n t r o d u c t i o n t h e o r e m4 4 1ac b s a ( v ，3 ，a ；2 ) e x i s t s 矿a n do n t u v 1 5a n d ( 1 ) 村三3 ，5 ( r o o d6 ) w h e na 兰1 ，5 ( m o d6 ) b u t 3 ( m o d6 ) w h e na = 1 ； ( 2 ) ”；0 ，2 ( m o d3 ) a n d 2 ( r o o d4 ) w h e n a ；2 ，l o ( m o d1 2 ) ； ( 3 ) 兰1 ( m o d2 ) w h e na 三3 ( m o d6 ) ； ( 4 ) 1 三0 ，2 ( m o d3 ) w h e n a 三4 ，8 ( m o d1 2 ) ； ( 5 ) 口2 ( m o d4 ) w h e na 兰6 ( m o d1 2 ) ； ( 6 ) t ，妇u n r e s t r i c t e dw h e na 三0 ( r o o d1 2 ) t h e o r e m4 4 2ac b s a ( v ，3 ，a ；3 ) e x s t s 矿a n dd 嘶i v 2 1a n d ( 1 ) 口兰1 ，3 ( m o d6 ) w h e n a 三1 ，5 ( r o o d6 ) ； ( 2 ) ；0 ，1 ( m o d3 ) a n d 口2 ( m o d4 ) w h e na 三2 ，1 0 ( m o d1 2 ) ； ( 3 ) 口三1 ( r o o d2 ) w h e na 兰3 ( m o d6 ) ； ( 4 ) 甜兰0 ，1 ( m o d3 ) w h e n a 兰4 ，8 ( m o d1 2 ) ； ( 5 ) 口2 ( m o d4 ) w h e na i6 ( r o o d l 2 ) ； ( 6 ) t ，话u n r e s t r i c t e dw h e na 兰0 ( m o d1 2 ) t h e o r e m 4 4 3t h e n e c e s s a r y a n d s u f f m i e n tc o n d i t i o n s o r t h ee 匠s t e n c e o l a c b s a ( v ， 3 ，是4 ) 婉a v ( v 一9 ) i0 ( m o d6 ) ，a p 一9 ) 兰0 ( m o d2 ) a n d 口2 ( r o o d4 ) i a ；2 ( m o d4 ) ，w h e r e t ，22 7 b ym a u x i l i a r yd e s i g nb s a ( q ， 2 ，3 ，a ；o t ，t ) ( s d e f i n i t i o n5 0 1 ) a n d3 - i g d d o ft y p e0 ，2 口+ 1 p ，w eh a v et h ef o l l o w i n gr e c u r s i v ec o n s t r u c t i o nf o rab s a ( g a + t ， 3 ，凡0 。 c o n s t r u c t i o n5 1 4s u p p o s et h a tt h e r ee x i s t s 口3 - i g d do ft y p e 9 ，2 硅+ l p 戗t 矗 i n d e xo n e 可t h e r ee x i s tab s a 0 ， 2 ，3 ) ，a ；n ，t ) ，ab s a ( g + t ，3 ，凡o t ) a n da b s a ( ( 2 a + 1 ) u ，3 ，a ；o ) ，t h e nt h e r ee x i s t sab s a ( g u + t ，3 ，a ；o ) t h e nw eg e tt h en e c e s s a r ya n ds u f f i c i e n tc o n d i t i o n sf o rt h ee x i s t e n c eo fab s a ( v ， 3 ，a ；o ) w i t ho t = 2 ，3 ，4 t h e o r e m5 4 1f o rq = 2 ，3 ，4 ，t h en e c e s s a r ya n ds u f f i c i e n tc o n d i t i o n sy o rt h e e x i s t e n c eo ynb s a ( v ，3 ，凡o ) a 化a v ( v 一2 n 一1 ) 兰0 ( r o o d6 ) ，a 扣一2 q 一1 ) 兰 0 ( m o d2 ) a n d 口3 ( 2 a + 1 ) ， 6 1 3 m a i nr e s u l t s w ei n t r o d u c eac o m b i n a t o r i a ls t r u c t u r ec a l l e dp a x t i t i o n a b l es e tw h i c hi sas e t 啦，以) ：1 i 扣一1 ) 4 o fu n o r d e r e dp a i r si na l la b e e a ng r o u pg o fo r d e r 口 ( 三1 ( m o d4 ) ) s a t i s f y i n gt h a tu 量1 ) 4 仕啦，士兢) = g o a n du b ( v - 1 1 4 - i - ( a i + b 1 ) ， 4 - h b 0 = g o b yu t i l i z i n gp a r t i t i o n a b l es e t sa n dd i f f e r e n c em a t r i c e s ，w eg e t t w or e c u r s i v ec o n s t r u c t i o n sf o rac b s e c ( v ，4 ，1 ) c o n s t r u c t i o n6 2 2 可t h e r ei sn 弘n i 咖n n 姚s e t 讥磊a n d ( 口，3 ) = 1 ，t h e nt h e r e 诂口c b s e c ( 3 v ，4 ，1 ) 讥 c o n s t r u c t i o n6 2 3l e t “口b ep o s i t i v ei n t e g e r s s u p p o s et h a tt h e r ee x i s t ： ( 1 ) 口p a r t i t i o n a b l es e t 轨磊； ( 2 ) d c b s e c ( u ，4 ，1 ) 访乙； ( 3 ) d ( 口，4 ，1 ) 一d m 讥z ； t h e nt h e r ei sac b s e c ( u v ，4 1 ) 机z 0 。 t h e nw eo b t a i ns o m ep r e r n n i n a r ye x i s t e n c er e s u l t sf o rac b s e c ( v ，4 ，1 ) a 8 f o l l o w s t h e o r e m6 2 4t h e r ei s8c b s e c ( a v ，4 ，1 ) m h 唧 dp r n d c to ln u m b e r si n q = p ：p 兰1 ( m o d4 ) a n dp 主s 嘶 u q ：g 暑1 ，5 ( m o d1 2 ) ，口si 6 0 ) a n d d 3 ，2 7 ，6 3 ，9 9 ，1 7 1 ，2 0 7 , 2 4 3 c h a p t e r 2 p r e l i m i n a r i e s i nt h i sc h a p t e r ，w ep r e s e n ts o m es p e c i a ls e q u e n c e sw h i c hi su s e f u li nt h ec o n s t r u c t i o n s o fc y c l i cb s e c ( v ，3 ，a ) a n dc y c l i cb s a ( v ，3 ，a ；n ) a n dp r e s e n ts o m ep l a i nr e s u l t s f o ra b s a ( v ，k ，九口) 2 1s e q u e n c e s s u p p o s et h a tb 五l e ta b = 甄一b a m e d 。) ：6 i ，6 j b ，6 【i 毛) l e t 【n ，b l d e n o t et h e 啾o fa l li m e g e 璐ns u c ht h a ta n b ，a n da 【口，b ld e n o t et h em u l t i s e t c o n t a j n i n ge a c he l e m e n to fi n ，6 】e x a c t l ya t i m e s t h ef o l l o w i n gl e m m ai sf r o m 【1 7 l e m m a2 1 1s u p p o s et h e r ee x i s tk - s u b s e t s 历，岛，最o l 乙s u c ht h a tt h e m u l t i s e tu n i o nl j l = 1 且= a i a + 1 ，口一o t l ，t h e nt h e r ee x i s t sab s a ( v ，后，a ；0 ) t h es u b s e t sb i ，最i nl e m m a2 1 1w i l lb ec a l l e db a s eb o c k 8o ft h eb s a ( v ，k ， 九口) t h ea b o v el e m m ae n a b l eu st ou s el a n g f o r ds e q u e n c ea n de x t e n d e dl a n g f o r d s e q u e n c et oc o n s t r u c tc b s a ( v ，3 ，a ；n ) l a n g f o r ds e q u e n c ei su s e f u li nc o n s t r u c t i n g c y c l i cs t e i n e rt r i p l es y s t e m s m o r ei n f o r m a t i o no i ll a n 酉o r ds e q u e n c ea n dk - e x t e n d e d l a n g f o r ds e q u e n c e ，t h er e a d e ri sr e f e r r e dt o 【1 ，1 2 ，2 3 ，2 6 ，2 7 ，2 8 ，3 4 ，3 5 ，3 6 1 t h e f o l l o w i n gd e f i n i t i o ni sf r o m d e f i n i t i o n2 1 1a s e q u e n c es = d ，d + l ，d + m 一1 ) o mc o n s e c u t i v ei n t e g e r s i sc a l l e dap e r f e c tl a n g f o r ds e q u e n c e ，t h es e t l ，2 ，2 m nb ep a r t i t i o n e di n t o 9 c h a p t e r2 p r e l i m i n a r i e s p a i r s ( m ，) ：1sism ，s u c ht h a t b i a i ：1 m = s t h es e q u e n c e s 话例d ah 0 d k e d b a n g f o r ds e q u e n c e 矿眈es e f 1 ，2 ，2 m 一1 ，2 m + 1 ) c a nb e p a r t i t i o n e d i n t o p a i r s ( n “缸) ：1 i m s u c h t h a t 玩一a i ：1 i m = s ， s i m p s o ng a v et h en e c e s s a r ya n ds u f f i c i e n tc o n d i t i o n sf o rt h ee x i s t e n c eo fp e r f e c t a n dh o o k e dl a n g f o r ds e q u e n c e si n f o l l o w s t h e o r e m2 1 2l e t s = d ，d + 1 ，- 一，d + m l t h e n ( 1 ) si sap e r f e c tb a n g y o r ds e q u e n c e 玎a n do n l y ，mi0 ，1 ( m o d4 ) 1 0 r do d d , m 三o ，3 ( m o d4 ) y o r de v e n ，a n d m 2 d 一1 ， ( 2 ) si sdh 0 d k e db a n g f o r ds e q u e n c ei fa n do n l yi l m 兰2 ，3 ( m o d4 ) o rdo d d , m 三l ，2 ( m o d4 ) ，d r d 嗍a n d m ( m + 1 2 d ) + 2 0 l e m m a2 1 3l e t db eo d d 矿m eo 1 ( r o o d4 ) ，d re v e n 妒m 三0 , 3 ( m o d4 ) s u c h t h a t ，l 2 d 一1 t h e ni 吐d + 3 m 一1 lc a nb ep a r t i t i o n e di n t ot 坳t e s n ，k ，c i ) ， 1 i s m ，s u c h t h a ta i + 岛= c i p r o o f b yt h e o r e m2 1 2 ，t h el m a g f o r ds e q u e n c e d ，d + 1 ，d + m l l i sp e r f o c t a n dh e n c et h es e t 1 ，2 ，2 m ) c 蛆b ep a r t i t i o n e di n t op a i r s 饿，) ，s i l 出t h a t u 銎l 一6 ： = d ，d + 1 ，d + m l l e ta i = 一6 5 ，玩= 磁+ d + m 一1 a n dc i = + d + m 一1 f o r l i m i t i se a s y t os e e t h a t 【d d + 3 m 一1 】c a l lb e p a r t i t i o n e d i n t o t r i p l e s 啦，坟，q 1 i s m ，s u c h t h a t 啦+ 6 = 龟 d l e n m m2 1 4l e tdb eo d d 矿m12 ，3 ( m o d4 ) ，0 7 e v e nc m 三