形式陈述
取整数 1 ≤ t ≤ k ≤ v 与 λ ≥ 1 。t -( v , k , λ ) 区组设计是二元组 ( X , B ) :X 是含 v 个点的有限集 理路 有限集 Finite set 与某个自然数初始段等势、因而能够在有限步内无遗漏编号的集合。 ,B ⊆ ( X k ) 是一族$k$ 元子集 理路 组合 Combination · k-subset 从有限集合中无序选取固定数量元素所得的子集。 (称为区组),使得 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 − t k − t ) ,因为一个固定 t 元组只能放进这么多个不同的 k 元区组。特别地,t = k 时只能取 λ = 1 ,并且必须选取全部 k 元子集。
直觉
区组设计的出发点是"公平"。设想要用若干次小规模试验比较 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 直接构造:把 F 2 3 的七个非零向量作为点,每条线取 { a , b , a + b } ,其中 a ≠ b 。每对不同非零点唯一决定第三点,故每对恰出现一次;以三位二进制数 1 , … , 7 标号时,七个区组是 123 , 145 , 167 , 246 , 257 , 347 , 356 ,这里 123 表示点集 { 1 , 2 , 3 } 。Steiner 三元系是 2 -( v , 3 , 1 ) 设计;对 v ≥ 3 ,Kirkman 证明了它存在当且仅当 v ≡ 1 , 3 ( mod 6 ) 。
整除条件只是必要条件,并不保证设计存在,这是初学者最易忽略的边界。经典反例是 2 -( 43 , 7 , 1 ) :其参数使 b = 43 、r = 7 均为整数,但该设计(即六阶射影平面)被 Bruck–Ryser 定理排除:六阶满足 6 ≡ 2 ( mod 4 ) ,却不能写成两个整数平方之和。另一处约定性边界是重复区组:允许同一区组多次出现时,应把 B 改为多重集并按重数计入"包含次数",称为多重设计;本页默认简单设计。最后,区组设计不同于一般 k 一致超图 理路 超图 Hypergraph 边可以连接任意多个顶点而非仅两个顶点的离散结构。 ——超图对子集的出现次数没有任何均衡要求,设计则要求精确均衡,因此可视为超图中高度正则的特殊类。
推论与应用
t = 2 的情形即均衡不完全区组设计(BIBD)。Fisher 不等式断言非平凡 2 -设计(v > k )必有 b ≥ v ,等号成立的对称设计(如射影平面)同时是有限几何的核心对象。在统计实验中,BIBD 把处理分配在容量受限的区组内,以控制区组间异质性;数据分析可写成含区组与处理项的线性模型,并由方差分析 理路 方差分析 Analysis of variance · ANOVA 将组均值比较表示为线性模型,并把总平方和正交分解为组间与组内部分。 比较相应平方和。组合上的出现次数平衡并不自动提供随机化、误差独立、同方差或因果解释,这些条件必须由实验方案另行给出。
在编码理论中,有一个精确的单错例子:设二元长度 n ≥ 3 的码含零码字,且半径一的 Hamming 球恰好分割全部二元串。每个重量二的串必须由唯一一个非零码字在距离一内覆盖;最小距离至少三迫使该码字重量为三,并包含原来的两个非零位置。因此重量三码字的支撑构成 2 -( n , 3 , 1 ) Steiner 三元系。二元 [ 7 , 4 , 3 ] Hamming 线性码 理路 线性码 Linear code 有限域向量空间中的线性子空间作为码字集合的信道码。 就给出上面的 Fano 区组。其他码或其他重量层是否形成设计,需另证相应条件,不能对所有完备码的任意固定重量层一概断言。相同的覆盖均衡思想还用于抽样方案、软件成对测试覆盖与密钥分配,但每个场景对区组、重复和容错的解释并不相同。
存在性理论关心满足参数方程的组合对象是否真的存在。Keevash 于 2014 年证明:对任意固定的 1 ≤ 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 ,arXiv:1401.3665,2014 年首稿;所链作者稿修订于 2018-02-16,§1、Theorems 1.4 与 1.10(固定 t < k 的存在性及一般重数)。