形式陈述
取整数 1 ≤ t ≤ k ≤ v 与 λ ≥ 1 。t -( v , k , λ ) 区组设计是二元组 ( X , B ) :X 是含 v 个点的有限集 公理库 有限集 Finite set 与某个自然数初始段等势、因而能够在有限步内无遗漏编号的集合。 ,B ⊆ ( X k ) 是一族 k 元子集(称为区组),使得 X 的每个 t 元子集恰好包含在 λ 个区组中。本页默认采用简单设计约定,即 B 中区组互不重复。双计数"t 元子集与包含它的区组"的配对,得区组总数
b = λ ( v t ) ( k t ) ; 更一般地,对 0 ≤ s ≤ t ,每个 s 元子集所处的区组数与该子集的选取无关,为
λ s = λ ( v − s t − s ) ( k − s t − s ) . 由于这些量都是计数,参数 ( t , v , k , λ ) 必须使所有 λ s 为整数,这称为可除性(整除)条件。
直觉
区组设计的出发点是"公平"。设想要用若干次小规模试验比较 v 种处理,每次试验只能容纳 k 种:若某两种处理同场出现的次数比别的组合 公理库 组合 Combination · k-subset 从有限集合中无序选取固定数量元素所得的子集。 多,它们之间的比较就占了更多数据,结论会有偏。要求每个 t 元组恰好共同出现 λ 次,就是把这种偏差在设计层面归零——统计学家 Fisher 与 Yates 在农业试验中正是为此引入了均衡不完全区组设计。从组合角度看,它把"每对对象共同出现同样多次"(t = 2 )推广为任意阶的局部均衡;而 λ s 公式表明高阶均衡自动蕴含所有低阶均衡:一个 t -设计同时也是 s -设计(s < t )。这种"处处一样"的强对称要求,正是设计比一般集合族稀有得多、又有用得多的原因。
例子与边界
Fano 平面是最小的非平凡例子:以七个点、七条"直线"(每线三点)构成 2 -( 7 , 3 , 1 ) 设计,任意两点恰在一条直线上。代入公式验证:b = 1 ⋅ ( 7 2 ) / ( 3 2 ) = 21 / 3 = 7 ,每点处于 r = λ 1 = 6 / 2 = 3 条线上,与图形一致。它同时是有限域 公理库 有限域 Finite field · Galois field 底层集合有限的域。 F 2 上的射影平面,展示了设计与有限几何的联系。Steiner 三元系是 2 -( v , 3 , 1 ) 设计;Kirkman 证明了它存在当且仅当 v ≡ 1 , 3 ( mod 6 ) 。
整除条件只是必要条件,并不保证设计存在,这是初学者最易忽略的边界。经典反例是 2 -( 43 , 7 , 1 ) :其参数使 b = 43 、r = 7 均为整数,但该设计(即六阶射影平面)被 Bruck–Ryser 定理排除,根本不存在。另一处约定性边界是重复区组:允许同一区组多次出现时,应把 B 改为多重集并按重数计入"包含次数",称为多重设计;本页默认简单设计。最后,区组设计不同于一般 k 一致超图 公理库 超图 Hypergraph 边可以连接任意多个顶点而非仅两个顶点的离散结构。 ——超图对子集的出现次数没有任何均衡要求,设计则要求精确均衡,因此可视为超图中高度正则的特殊类。
推论与应用
t = 2 的情形即均衡不完全区组设计(BIBD)。Fisher 不等式断言非平凡 2 -设计(v > k )必有 b ≥ v ,等号成立的对称设计(如射影平面)同时是有限几何的核心对象。在统计实验中,BIBD 把处理分配在容量受限的区组内,以控制区组间异质性;数据分析可写成含区组与处理项的线性模型,并由方差分析 公理库 方差分析 Analysis of variance · ANOVA 将组均值比较表示为线性模型,并把总平方和正交分解为组间与组内部分。 比较相应平方和。组合上的出现次数平衡并不自动提供随机化、误差独立、同方差或因果解释,这些条件必须由实验方案另行给出。
在编码理论中,设计与好码可以互相生成:完备码的固定重量码字支撑集构成 Steiner 系统,反过来,设计也可用来构造并分析线性码 公理库 线性码 Linear code 有限域向量空间中的线性子空间作为码字集合的信道码。 的重量分布。相同的覆盖均衡思想还用于抽样方案、软件成对测试覆盖与密钥分配,但每个场景对区组、重复和容错的解释并不相同。
存在性理论关心满足参数方程的组合对象是否真的存在。Keevash 于 2014 年证明:对任意固定的 t , k , λ ,只要 v 充分大且满足全部整除条件,t -( v , k , λ ) 设计必然存在,从而把长期悬而未决的一般存在性问题化归为有限多个小参数例外。
参考资料
J. H. van Lint and R. M. Wilson, A Course in Combinatorics, 2nd ed., Cambridge University Press, 2001,Ch. 19, t-designs, BIBDs, and parameter equations。
Douglas R. Stinson, Combinatorial Designs: Constructions and Analysis, Springer, 2004,Chs. 1 and 9, BIBDs, t-designs, parameter identities, and examples。
Peter Keevash, “The Existence of Designs,” Annals of Mathematics 177(3), 2014,general existence theorem under divisibility conditions for sufficiently large parameters。