目 录 第十一章组合设计概论 §I1.1问趣的提出………………………………1 §11.2完全区组设计…………………………… §11,3平衡不完全区组设计 10 §114一些特殊类型的平衡不完全区组设计…………… 3 §115部分平衡不完全区组设计 18 §11,6-设计和按对平衡设计……………………………20 §11,7其他设计简介………………………………… §1].8组含设计理论的内容 31 第十二章平街不完全区组设计的一般瑶论 33 §I2.1关联矩阵…………………………………… 33 §12.2完备化题… 专, 38 §I2,3一种构造方法……………………………… 45 s12.4三连系………… 65 第十三章对称设计 ……76 §13.1关联矩阵 76 §13,2山对称设计引出的一些没计…………………………8 §t3.3在性 91 §13.4关联方程…………… 113 第十四章霭环设计的性质、变体和推广 …12l 14.1循坏设计与循环差集的关系以及对二者的刻划…………121 §14,2存在性… .134 §143乘数 I42 §14.4循环拟差集………… 155 §14.5m-(巧;,kx…,;λ)-循环差集……………156 §I4,6裾环相对羔集 159 §14,7循环加集…………………… 160
§I+,若差集积上则设计………… 第十五章循环设计和正则设计的构造方法… 7 §15.!循环设计的构造方法………………… 17 §15.2眢环设计的构造方法二………… 15.循环设计的构造方法三…………… §15.4酒环设计的构造方法四……… 194 §155循环设计的构造方法五 I5.6一类正则设计的构造方法 第十六章H我 damar设计 §16.1 stannard设计和 Hadamar矩唯…… 225 §16.2 Fladanare矩阵的一些特殊类型………………233 §16.3同 Hadamard矩阵相关的一些矩阵…… 236 §16,4一般 Hadamard矩阵的构造方法之…一… 246 §16.5 Hadamard矩阼睦偶的构造法… §16.6反型 Hadamard矩阵的构造法 256 §16.7对称 Hadamard矩阵的构造法… 259 §168一般 Hadamard矩阵的构造方法之 262 §16.9 willianson型 Had amard矩阵………… §16,10小阶数的 Hadamard矩阵……………… 274 §16.11关于定理13.4,4的讨论………………… 第十七章几何设计 ………277 §1:.1有限平面… 277 §17.2平面设计………………… 283 §17.3平设计与正交拉丁方… 292 §t7,4有限射影空间与区组设计 :+·:·+4t: 298 §7.5有限向量空间与区组设计 ·甲 302 第十八章完全设计和正交设计……………………………311 §18.1拉丁方 11 s18.2完备拉丁方……… 518.3正交得…… 32 §18.正交拉丁方的构造……………………………………30 §18.5N(m)………… 34 §I8.6 Euler猜想(--):阶大于6的情形…
第十九章横截设计、按对平衡设计及其应用 35 §19.1横截设计………………………357 按对平鶴设计(一) ………363 §19.3三连系存在的充要条件… 369 §194回订分解的(b,U,,λ)-设计有关的一些结果………377 §I95可分解的(b"',,λ)-设计… §I9.6 Euler猜想(二):阶等于6的情形 391 §19.7按对平衡没计(二)……………………………………………398 第二十章部分平衡不完全区组设计………………4 §20I结合矩阵和关联矩阵…………………………… 40 §202可分组设计…………………………………………411 §20.3三角形设计 419 §20.4拉门方型设计…………… §20.5利用有限向量空间构造结合方案 §206利用有限向量空间构造PBB设计 453 参考资料 ……………460 符号表 476 名词索引………………………………………………478
第十一章组合设计概论 组合设计理论是现代组合论的一个非常重要的分支,本章介绍 这一分攴的概貌,而把详细的讨论留在本书的以后各章。在介绍概 貌时,着重三个方面:一、这个分支的实际背景,附带介绍历史的 两个著名组合学课题(§11.1);二组合设计的主要类型,即可分解 设计(§11,1),全设计和正交设计(1,2),平衡不完全区组没计 (511,2)对称设计循环设计,几何设计和 Hadamard没计(§11.4), 部分平衡不完全区组设计(51.5),t-设计和按对平衡组设计 (§11.6)Yuen设计,Room设计,称重设计幻方夏盖和填装等 (§11,7);三、组合设计理论的内容(5118) §I,1问题的提出 在组合设计这一分支中,也象在组合论的其他分支中一样,许 多课题的原始形态是智力游戏,因而人们对它们的研究最初也总 是纯数学的.然而,当这种研究深入到一定阶段,特别是当生产发 展和其他学科发展过程中产生相同或相近的问题时,这些课题就 同实际紧密结合起来,一当它们的意义明朗之后,对它们的研究 就有了强大的天然动力,因而就会吸引人们更多的注意,成果也就 更加丰富.下面首先看两个例子,一个是所谓“三十六名军官问 题”另一个是“ Kirkman女生问题”, 1782年, Euler提出的一个问题以下面的“三十六名军官 间题”为其特例 问题1111.有三十六名军官,他们来自六个不同的团队,每 个团队六名且分属于六种不同的军阶.能否把他们排成一个方形 阵列,使得每行、每列的六名军官正好来启不同的团队且属不同 的军阶?
这就是著名的“二六名军官问题”、如果在这个问题中把6 换为∽把36换为φ2,则问题就酱遍化了,为了揸述和研究普遍 化后的问题,要引进一些术语和记号 设S={s }是一个元集,如果S上的一个阶 方阵 a1s (11.1.1) a 满足条件: an,,(1≤i≤;1≤n午i≤),(11.2) ≤2),(11.1.3) 则称A是集S上的一个v阶拉丁方.条件(12)即:(111.1)的 每一行都是S的个无重全排列;条件(1.1.3)即:(11.L.1)的每 一列都是S的一个无重全排列 设B=(b)是S上的另一个v阶拉丁方,且符合条件:在 以S的元秦偶为元的矩阵 ((叫i,b))(1≤ij≤v) (11.1.4) 中,$×S中的全部萨个元没有不出现的,则称拉丁方A和B是 巢S上的一对r阶正交拉丁方,或说A和B正交 在问题11.1.1中,如果把六个团队和六种军阶都各用[1,6|中 的数码来编号,而且以(i,i)表示来自第i个闭队且属于第i种 军阶的军官,那么问题111.1就可重述为;是否存在集[1,6〕上的 对六阶正交拉「方? 这个问题可以普遍化为 问题11.12.对任意正整数v,是否存在一对v阶正交拉丁 方? 关于问题1.2以及正交拉丁方这一课题的详细订论将在第 十八章中进行.现在来看看这一问题的实际意义 今把某试验出分成纵横的九小块且欲在其上试种三个不同品 种的小麦A,B和C,以便得出在,B和C中哪一个品种最适
宜在该地区种植的有关结论.比较一下下面几种划分试验场地的 方式 (2) 11.5) C BB Bisic (3 在(15)的(1)和(2)中,品种A,B和C安排得比较集中.这 样,三横条或三竖条地上的上质的好坏对三个品种的小麦的长势 和收成的影响很不均衡,(3)比(1)和(2)都好特别是每一纵条上 三个品种的小麦都有,因而三纵条上的土质对这三个品种的小麦 的影晌比较均衡;但是,在三个横条上,三个品种的小麦却分布得 很不均衡,因而三横条上的土质对这三个品种的小麦的影响就不 均衡了.(4)就避免了上述缺点,使得三横条和三纵条上的土质对 三个品种的小麦的影响都是均衡的,这表明了方法(4)比其他三 种方法都要好些,而(4)正好是三个文字的集{A,B,C}上的 个三阶拉丁方 今欲生产一种饮料,其主要原料有A,B,C,D四种,希望 通过试验来找到一个恰当的配方使得饮料的质量最好 如果对每种原料都选择三种不同的剂量,分别记为A;;B,, C,D;(1≤i≤3),来做试猃,就得做3-=81次.能否通过作较 少次数的试验而得出比较可靠的结论呢? 粗略地说,如果能设计出…个做力次试输的方案使得四种原 料的任二种(暂记为甲、乙)的三个剂量的组合甲,(1≤j≤3), 乙,(1≤≤3)都能在这个方案巾出现,则可望由此得出较可靠 的结论.如果每一对甲,乙恰好相遇一次,那么,各种原料的各
种剂量就可认为搭配得很合黜,且在保证此合理搭配的条件下试 验次数可达到最小,因而是比较理想的试验方案 现在来计算这样的试验次数n.一次试验可以用下面的方法 来表示 A1B;CbD2;A的剂量为A,B的剂量为B;,C 的剂量为Ck,D的剂量为D 于是,一次试验中有诸原料的(2)=6对剂量相遇故m次试验 中诸原料的种剂量相遇的总次数为6n。另一方面,由A分别 与B,C,D的全部可能的剂量各相遇一次,就得相遇9次,故A 的三种剂量分别与B,C2D的全部可能的剂量各相遇一次时,其 相遇的总次数为3·9次.类似地,B的三种剂量分别与C,D的全 部可能的剂量各相遇一次时,其相遇的总次数为3·6次;C的三种 剂量与D的三种剂量各相遇一次时,其相遇的总次数为3·3次 总起来,每二种剂量恰好相遇次时,诸剂量相遇的总次数是 3(9+6+3)-54. 由6n=54得出n 这就是说,符合要求的方案如果存在的 话,它包含九次试验 为了配出这九个方案,可列出一张表,除了表头的行以外,它 的每一行表示一次试验,而第1,2,3,4列分别是A,B,C,D的 三种剂量,由于A;与B1,B2,B,都要相遇,故A1,A2A3各要出 现在二行上,而且在4出现的三行上,B1,B2,B3各出现一次。 这样一来,经过行的换序,这个表的头二列可以写为 BBBBBB时 (11.】6 B d, By
为了得出符合要求的第i列,把(.10改写为下面的形式更 为有益 CA,B),C (11.17) (42,B1),(H,B1),(42,B3) (l,B1),(3B),(H1,B3) 其中第i行与第列交口处的元素为“(A4B;),",这里A;,B1外 的括号表示A;和B;组成一个元素对.这可以略去不写,因为由 表的行头和列头已经表明了这一点,(A,B)后的逗号表明将要 添上适当的Ck.由于元秦对(,C)(1≤1个≤3)和(B;,Ck) (1≤门≤3)在全部表中恰好各出现一次,所以C1C1,C,在 (117)除表头以外的各行和各列中皆各出现一次.因此,路去 (1117)中的诸(A;,B;)且添上符合要求的各C所形成的阵列 正好是集{C:,C2,C3}上的一个三阶位丁方.而且反之亦然 例如,可以用三阶拉丁方 C1 C2 Cy C. c 1118) 把表(1117扩充为 B CA,B),C (I119) (A1,B1),C(A13B:),C(A13B3),C (A2,B1),C,(3,B:),C3(3,B,C1 占 (A,B1),C1(J3,B1),C,(耳3,B3)C3 现在还需在(119)亡添入适当的D.与添C的情形类似地,要 添人的诸D组成集{D1,D2,D}上的一个三阶拉丁方,此外,诸 D的足标与诸C的足标各相遇一次,这就是说,足标对(饣,)恰
好出现一次,亦即D4的诸足标所组成的拉了方与诸C的足标所 组成的拉丁方这二者正交。而且,反过来的推理也是对的.例如, 因为 123 231和 正交,故可把(11.1.9)扩充成符合要求的表 B B. B A、(B),C,D (,B1),C1,D(A1,B2),C2,D(A1,B3), (A2,51),1,D3(A,),3,D,(A2B1)2C,D f(3,B1),3;D2(3B2),C1,D1(a3B3),C2,D2 在表(I110)的“(A,B),C,D"栏中的九个组合就是符合要 求的试验安排 下面转而讨论 Kirkman于1847年提出的一个问题 问题1113( Kirkman女生问题)某教员打算这样安排 她班上的十五名女生散步:散步时三名女生成一组,共五组,问 能否在一周内每日安排一次散步,使得每两名女生在这周内一 道散步恰好一次? 下面就悬符合要求的分组方法 第一日:{1,2,5},{3,14,15},{4,6,12}, {7,8,11},{9,10,13} 第二日:{1,3,9},{2。8,15}{4,11,13} {5,12,14},{6,7,10}; 第三日:{1,4,15},{2,9,11},{3:10,12}, {5,7,13}3{6,8,14} 第匹日:{1,6,1!},{2,7,12},{3,8,13},(1l.1,11) 14,9,14},15,10,1
第五日:{1,8,10},{2,13,14},{3,4,7}, {5,6,9},{11,12,15}; 第八日:{1,7,14},{2,4,10},{3,5,8} {6,13,15},{8,9,12}; 第七日:{1,12,13},{2,3,6},{4,5,8}, {7,9,15},{10,11,14} 问题11.1.3表面上看起米乜纯属数学游戏,然而它的解(11.1.If) 却有其实际应用,下面是一个说明性的例子,今欲用15种饲料 对某种动物作试抢,试验分五个阶段进行,每个阶段以三种饲料的 混合物来喂养用作试验的七只同类动物,假定需要按以下条件来 安排试验:(1)每种饲料对每只用作试验的动物在五个阶段所用 的泥合饲料中恰好用一次,(2)每两种不同的饲料对全体用作试 验的动物在五个阶段所用的混合饲料中都恰好同时用过一次。那 么,根据(111),可以得到一个符合要求的安排,有如(11.112) 所 阶段 饲 第…一只 I,2,53,14,1546,12 7,8,11910,1 第只 1,3,92,8,154lI,135,12,146,7,10 第三只 第四只 1,6,112,7,123,8,13 4,9145,10,15 第五以 ⊥,8,102,I3,143,4, 5,6,911,12,l 第六只 1,71+2,4,103,5,11 6,13,158,9,12 第只 1,』2,32,3,6 4,5,5 7,91510,1,1 (11.1.12) 关于 Kirkman女生问题以及与其有关的一些河题,在第十九 章还将详细地讨论 不管是用拉丁方在试验地上安排农作物的播种,或用正交拉 丁方安排儿种原料的配方,还是用 Kirkman女生问题的解作出的 一个饲程內饲料的安排,都涉及一些科学试验的安排问题.上面
