Skip to content

定义Definition

区组设计

施工中 · 内容逐步修订

Block design

使每个小子集在固定数量区组中出现的均衡有限集合族。

形式陈述 ​

取整数 1≤t≤k≤v 与 λ≥1。t-(v,k,λ) 区组设计是二元组 (X,B):X 是含 v 个点的有限集,B⊆(Xk) 是一族$k$ 元子集(称为区组),使得 X 的每个 t 元子集恰好包含在 λ 个区组中。本页默认采用简单设计约定,即 B 中区组互不重复。双计数"t 元子集与包含它的区组"的配对,得区组总数

b=λ(vt)(kt);

更一般地,对 0≤s≤t,每个 s 元子集所处的区组数与该子集的选取无关,为

λs=λ(v−st−s)(k−st−s).

由于这些量都是计数,参数 (t,v,k,λ) 必须使所有 λs 为整数,这称为可除性(整除)条件。简单设计还必须满足 λ≤(v−tk−t),因为一个固定 t 元组只能放进这么多个不同的 k 元区组。特别地,t=k 时只能取 λ=1,并且必须选取全部 k 元子集。

直觉

区组设计的出发点是"公平"。设想要用若干次小规模试验比较 v 种处理,每次试验只能容纳 k 种:若某两种处理同场出现的次数比别的组合多,它们之间的比较就会获得不同的数据量,精度可能不一致。要求每个 t 元组恰好共同出现 λ 次,可以平衡这种共同出现次数;它本身不保证统计估计无偏——统计学家 Fisher 与 Yates 在农业试验中正是为此引入了均衡不完全区组设计。从组合角度看,它把"每对对象共同出现同样多次"(t=2)推广为任意阶的局部均衡;而 λs 公式表明高阶均衡自动蕴含所有低阶均衡:一个 t-设计同时也是 s-设计(s<t)。这种"处处一样"的强对称要求,正是设计比一般集合族稀有得多、又有用得多的原因。

例子与边界

Fano 平面是最小阶的有限射影平面:以七个点、七条"直线"(每线三点)构成 2-(7,3,1) 设计,任意两点恰在一条直线上。代入公式验证:b=1⋅(72)/(32)=21/3=7,每点处于 r=λ1=6/2=3 条线上,与图形一致。它可由有限域 F2 直接构造:把 F23 的七个非零向量作为点,每条线取 {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(mod6)。

整除条件只是必要条件,并不保证设计存在,这是初学者最易忽略的边界。经典反例是 2-(43,7,1):其参数使 b=43、r=7 均为整数,但该设计(即六阶射影平面)被 Bruck–Ryser 定理排除:六阶满足 6≡2(mod4),却不能写成两个整数平方之和。另一处约定性边界是重复区组:允许同一区组多次出现时,应把 B 改为多重集并按重数计入"包含次数",称为多重设计;本页默认简单设计。最后,区组设计不同于一般 k 一致超图——超图对子集的出现次数没有任何均衡要求,设计则要求精确均衡,因此可视为超图中高度正则的特殊类。

推论与应用

t=2 的情形即均衡不完全区组设计(BIBD)。Fisher 不等式断言非平凡 2-设计(v>k)必有 b≥v,等号成立的对称设计(如射影平面)同时是有限几何的核心对象。在统计实验中,BIBD 把处理分配在容量受限的区组内,以控制区组间异质性;数据分析可写成含区组与处理项的线性模型,并由方差分析比较相应平方和。组合上的出现次数平衡并不自动提供随机化、误差独立、同方差或因果解释,这些条件必须由实验方案另行给出。

在编码理论中,有一个精确的单错例子:设二元长度 n≥3 的码含零码字,且半径一的 Hamming 球恰好分割全部二元串。每个重量二的串必须由唯一一个非零码字在距离一内覆盖;最小距离至少三迫使该码字重量为三,并包含原来的两个非零位置。因此重量三码字的支撑构成 2-(n,3,1) Steiner 三元系。二元 [7,4,3] Hamming 线性码就给出上面的 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 的存在性及一般重数)。
关系图谱6 个相邻概念 · 3 类关系

拖动节点调整位置。

显示关系

显示:依赖

  1. 前置三跳
  2. 前置二跳
  3. 前置一跳
  4. 当前条目
  5. 后续一跳
  6. 后续二跳
  7. 后续三跳
文字版关系按与当前条目的最短距离分组
分类位置

上位 / 更一般

下位 / 直接特例

暂未标注直接特例。

类型化关系

使用的工具