(组合数学)第5章区间设计.ppt

2011.11.09,1,组合数学第二部分 讲课老师：张承钿,2011.11.09,2,第 5 章 区组设计,2011.11.09,3,内容 问题的提出 拉丁方与正交的拉丁方 域的概念 Galois域GF(p ) 正交拉丁方的构造 正交拉丁方的应用举例 均衡不完全的区组设计 区组设计的构成方法 Steiner三元素 Kirkman女生问题,2011.11.09,4,问题的提出 有一块梯田种植3种不同的农产品A、B、C。由于高度、方位不同，所有其自 然条件有差异。按图5-1的(a)种植，每种产品只在同层出现；而按图5-1的(b) 种植，则每种产品只在同一方位出现；按图5-2种植，则每种产品即在同层出 现，又同一方位出现。显然，按图5-2种植，实验结果较准确。 测试4种轮胎，同一牌子在汽车不同位置磨损程度不同，所以每种不能只测试 一个轮胎，用4辆小汽车A、B、C、D参加测试，如右 图所示。 这个测试的特点是，每一种品牌的轮胎都在不同的汽车 和不同的位置作了安排。每种轮胎都用了4次。 测试的次数也均衡，其中A、B、C、D是汽车的代号， 矩阵的元素是轮胎的品牌代号。,2011.11.09,5,问题的提出 再论梯田种植问题 农作物类：、 梯田高度：高、中、低 日照方向：东、南、西 进一步的问题： 种子是买来的，三家种子公司都提供这些种子，价钱差不多 三种农作物的出售价格也差不多，只是播种方式不一样 实验的目的是比较出哪家公司的种子质量好，哪种作物产量高。 ？怎样安排实验 分析一：下面方法是否可行 如果把上面每块地（共九块）再分成三小块，每小块种上一家公司的作物 问题：每个小块的面积太小的话，无法判别产量 分成三次播种季节，每个季节种一家作物 问题：分三个季节的话，时间太长 分析二：下面结论是否成立 种子公司生产水平高，它的种子质量好，即公司X比公司Y好，则X的种子A、B、C应该比Y的种子A、B、C都相应的质量好。 农作物的产量不依赖于公司，即作物A比B产量高，则每家公司的作物A比B产量都高。,2011.11.09,6,问题的提出 重新描述梯田种植问题 农作物类：、 梯田高度：高、中、低 日照方向：东、南、西 种子公司：、 假如各个公司的实际产量如下： 即：公司X的A作物产量最高 ？：有没有办法，只在一个 季节内种植后，就能判 别出结果？,2011.11.09,7,问题的提出 重新描述梯田种植问题 农作物类：、 梯田高度：高、中、低 日照方向：东、南、西 种子公司：、 在九块田分别种植三家公司的三种农作物，寻找如下方案的解： 每行（梯田高度）包含三个公司，及三种作物 每列（日照方向）包含三个公司，及三种作物 例如下图方案： 具体产量： 正交拉丁方： 各个作物的产量： 各个公司的产量：,2011.11.09,8,拉丁方与正交拉丁方 拉丁方的定义： 由数1,2,. . .,n构成的nn矩阵： 如果数1,2,. . .,n中的每个都在每行和每列各出现一次，则称其为n阶拉丁方。 前面的4阶矩阵是拉丁方。如果把图5-2中的A、B、C用1、2、3代替，则我们 得到一个3阶的拉丁方。 36军官问题 有6个不同地区的6种不同军衔的军官各一名，共36名。现要将他们排成66 的一个方阵，要求做到： (a) 每行、每列都有军官来自6个地区； (b) 每行、每列都有6种军衔的军官 每个军官都有二个标志，即军衔和地区。我们把军衔按1至6编号，把地区也 按1至6编号，用(i,j)表示某军官的来自i号地区，其军衔是j号。 如果我们不考虑军衔，只寻找满足条件(a)的矩阵，则问题是求66的拉丁方。 同样，不考虑地区，只寻找满足条件(b)的矩阵，则也是求6阶拉丁方。 当我们把66方阵中的军官用其军衔号i和地区号j组成的数偶(i,j)替代后，组 成的方阵就满足：数偶(i,j)的第一个数组成一个6阶拉丁方，第二个数也组成 一个6阶拉丁方，且数偶(i,j)是唯一的。,2011.11.09,9,拉丁方与正交拉丁方 正交拉丁方的定义： 中的nn个数偶 互不相同，则称A和B是互相正交的拉丁方。 例子5-1 矩阵 都是3阶拉丁方，而方阵 中的9对数偶不同，故A和B是正交的。36名军官问题实际上就是求一对6阶 的正交拉丁方。并不是任意的n阶都有正交拉丁方。36名军官问题就是没有 解的。,2011.11.09,10,拉丁方与正交拉丁方 正交拉丁方的应用 正交拉丁方问题有实际的应用，例如测试药物： 有三种治发烧的药和三种治感冒的药配合起来给三位病人进行医疗实验， 要求在三天内每人都服过这几种药，要试验出哪种退烧药和感冒药配合起 来的疗效最佳。 用上述的二个3阶正交拉丁方，就可解决这个问题。 假设第h行、第k列的元素是(i,j)，我们就在第h天让第k号病人服用第i种的 治发烧的药和第种的治感冒的药。 具体例子就是，在第二行、第三列是数偶(1,3)，则在第二天三号病人服用 第一种治发烧的药和第三种的治感冒的药。 引理5-1 设A是拉丁方，则A的转置A仍是拉丁方。 引理5-2 设A是拉丁方，则通过置换p得到的方阵仍是拉丁方。 引理5-3 设A是拉丁方，则存在置换p，使得通过它得到规范拉丁方，即 A的第一行（或第一列）是1,2,.,n。 例子：,2011.11.09,11,正交拉丁方及其性质 一阶、二阶、三阶正交拉丁方 一阶拉丁方只有一个：1。也无所谓正交不正交。 二阶拉丁方只有二个： 它们不是正交。 三阶正交拉丁方至少有一个，就是前面的列5-1： 引理5-4 设A和B是正交拉丁方，p是对换，A是A经过p置换后的拉丁方， 则A和B仍是正交拉丁方。 引理5-5 设A和B是正交拉丁方，p是置换，A是A经过p置换后的拉丁方， 则A和B仍是正交拉丁方。 引理5-6 设A和B是正交拉丁方，A是A的行规范方，B是B的行规范方， 则A和B仍是正交拉丁方。对于都是列规范的情况也成立。 这里附带说明一下，二个行规范的正交拉丁方，其第一行组成的数偶是： (1,1) (2,2) . . . (n,n) 所有从第二行开始，它们没有相同的元素，即： ，如果 i1。,2011.11.09,12,正交拉丁方及其性质 定理5-1 若存在r(1)个n阶拉丁方两两互相正交，则：r (n-1)。按引理5-6，不妨设其都是行规范的。考察它们的第 二第一列的元素，共有r个。这些元素满足： 首先，都不能是1，即它们只能是2,.,n（共n-1个数）中的数； 其次，由于r(n-1)，故至少有二个元素相等； 即有二个行规范的正交拉丁方，它们在(2,1)这个位置是相等的，这就与引理5-6 相矛盾。故尔只能是：r n。 例子：三个四阶正交拉丁方：,2011.11.09,13,怎样构造正交拉丁方？ 构造阶乘是素数的正交拉丁方 整数同余类 集合 M(m, r) = x | x Z，xr mod(m) ，r=0,(m-1) 称为模m的一个同余类。 M(m) = M(m,0), , M(m,m-1) = 0,1, (m-1) 例子：M(7) = 0,1,6 = 周日、周一、周六 同余加法和乘法：例如在M(7)中 加法：5 + 4 = 9 2 mod(7)，即周五的过4天后是周二 乘法：5 * 4 = 20 6 mod(7) 构造拉丁方的公式： Ak = (a(k)ij)nn，k = 1,2,(n-1)，这里的n为素数 其中 a(k)ij = ak * ai + aj，这里ak、ai、aj分别是k、i、j模n， 或者 a(k)ij = (k*i+j) mod(n)。 然后把0用n替换，就是拉丁方，且共有 (n-1) 个拉丁方，它们 两两互相正交,2011.11.09,14,怎样构造正交拉丁方？ 构造阶乘是素数的正交拉丁方 例子：求5阶的正交拉丁方 M(5)的同余加法和乘法 第一个拉丁方，即 k=1 时：a(1)= (i + j) mod(5),2011.11.09,15,怎样构造正交拉丁方？ 构造阶乘是素数的正交拉丁方 例子：求5阶的正交拉丁方 第一个拉丁方，即 k=2 时：a(1)= (2 * i + j) mod(5) 对应的拉丁方阵就是：,2011.11.09,16,域的概念 群的定义： 设集合G=a,b,c,上有二元运算“”，并满足如下四个条件： (1) 封闭性：对任意a,bG，恒有 abG (2) 结合律：对任意a,b,cG，恒有 (ab)c=a(bc) (3) 单位元：存在eG，使得对任意aG，恒有 ae=ea=a (4) 逆元素：对任意aG，恒有bG使得 ab=ba=e=单位元 则称G在运算之下是一个群，简称G是群。 当一个群的元素是有限的，则称其为有限群。 交换群的定义： 如果集合G在运算之下是一个群，且进一步满足下面条件： (5) 交换律：对任意a,bG，恒有 ab=ba 则称G在运算之下是一个交换群（Abel Group），简称G是交换群。 域的定义： 设集合F至少含有二个元素，在F上有二种运算“”和“”，且满足下面条件： (1) F在“”下是交换群，其单位元记为“0”； (2) F0在“”下是交换群，其单位元记为“1”； (3) 分配律：对任意a,b,cG，恒有 (ab)c=(ac)(bc)； 则称代数系统为域，简称F为域。 同样，当一个域的元素是有限的，则称其为有限域。,2011.11.09,17,域的概念 群的例子：置换群 集合P是n的全排列，它在下述运算下是交换群： 若p,qP，p在第i个位置的值是pi，而q在第i个位置的值是qi，p和q 在运算的结果是r（即r=pq），则rpi=qpi。 同余类： 两个整数a和b，若它们除以整数m所得的余数相等，则称a和b对于模m同余， 记为 ab(mod m)，称为a同余于b模m。 集合0,1,m-1称为模m的同余类，记为mod(m)。 同余加法：在集合mod(m)中定义“”如下： 若a,b,cmod(m)，且c(a+b)(mod m)，则 ab=c 其中“+”代表正常的加法，而“”代表同余加法。 同余乘法：在集合mod(m)中定义“”如下： 若a,b,cmod(m)，且c(a*b)(mod m)，则 ab=c 其中“*”代表正常的乘法，而“”代表同余乘法。 群的例子：同余类 同余类是在同余加法下的交换群，其单位元是0。,2011.11.09,18,域的概念 域的例子：素数同余类 设p是素数，则由上面知：mod(p)=0,1,p-1是同余加法下的交换群，其单 位是0。如果我们能证明集合mod(p)0=1,p-1是同余乘法下的交换群， 则集合0,1,p-1就是域，且是p个元素的域。 我们只需要证明： 1、封闭性：若a,bmod(p)0，则恒有abmod(p)0； 2、单位元：mod(p)0在同余乘法下的单位元是1； 若c=ab，则显然cmod(p)，且存在整数n使得： a*b = n*p + c 因为p是素数，及a和b都小于p，所以c0，即cmod(p)0，封闭性得证。 由于p和a的最大公因数是1，所以根据数论定理（或用辗转相除法）知，存在 唯一的整数b和c使得： a*b = c*p + 1 或 a*b1(mod p) 用同余乘法表示就是ab=1，或b是a的逆元素。证毕。 素数p的同余类在同余加法 和同余乘法下的域用GF(p) 表示，称为p阶Galois域。 右边是p=5时的同余加法表 和同余乘法表：,2011.11.09,19,Galois域GF(p ) 整系数多项式： 大写字母Z表示所有整数的集合：Z=01,2,3,-1,-2,-3,。 系数在Z中的一元多项式，称为整系数多项式。 用Zx表示所有整系数多项式的集合，显然我们有： 和项式：若p(x),q(x)Zx，则(p(x)+q(x)Zx, 称其为和项式。 差项式：若p(x),q(x)Zx，则(p(x)-q(x)Zx, 称其为差项式。 积项式：若p(x),q(x)Zx，则(p(x)*q(x)Zx, 称其为积项式。 商项式：若p(x),q(x),t(x)Zx，且使得 p(x)*q(x)=t(x)，则称p(x)是t(x) 除以q(x)之商，记为：p(x)=t(x) / q(x)； 余项式：若p(x),q(x),r(x),s(x)Zx，r(x)的次数低于q(x)，且下式成立： p(x) = s(x) * q(x) + r(x) 则称r(x)是p(x)除以q(x)的余，记为：p(x)r(x)(mod q(x) GFp,x 用GFp,x表示系数在域GF(p)（其中p是素数）中的一元多项式的集合。 显然GFp,x是Zx的一个子集，进一步地，上面所述的和、差、积、商、余 的概念仍然成立。 不可约：若p(x)GFp,x不能用在GFp,x中的至少为一次的二个次数低 于它的积来表示，则称其为不可约的。它类似素数。,2011.11.09,20,Galois域GF(p ) 若p(x)GFp,x是可约的，即有次方0的二个多项式s(x),t(x)GFp,x，使得： p(x) = s(x) * t(x) 则称s(x)和t(x)是p(x)的因子。 公因子：若p(x),q(x)GFp,x，且有相同的因子，则称此因子是公因子。 互素的：若p(x),q(x)GFp,x无公因子，则称它们是互素的。 引理5-7 若p(x),q(x)GFp,x是互素的，则存在a(x),b(x)GFp,x，使得： p(x) * a(x) = q(x) * b(x) + 1 引理5-8 若p(x),q(x)GFp,x，且p(x)的次方大于q(x)的次方，则存在二个多 项式r(x),s(x)GFp,x，使得下式成立 p(x) = s(x) * q(x) + r(x) 其中r(x)的次方小于。 同余类： 设p(x),q(x),r(x),m(x)GFp,x，且r(x)的次方小于m(x)的次方。若下述成立： p(x)r(x)(mod m(x)， q(x)r(x)(mod m(x) 则称p(x)和q(x)是关于m(x)的同余类，记为p(x)q(x)(mod m(x)。 域GF(p ) 设m(x)GFp,x是不可约的n次多项式，GFp,x可化为关于m(x)的一些同余 类，记为GF(p )，它是GFp,x中所有次方小于n的多项式的集合，其元素个数 个数是p ，它和n位p进制数是一一对应。,2011.11.09,21,Galois域GF(p ) 例子：p=2, n=2 GFp,x = 0,1, x,1+x, x,1+x,x+x,1+x+x, x, 。 直接计算可以验证多项式 m(x)=1+x+x 是二次不可约的。 而GFp,x关于m(x)的同余类为GF(2) = 0,1, x,1+x ，在其上的同余加法和 同余乘法如下：,2011.11.09,22,Galois域GF(p ) 例子：GF(2) = 0,1, x,1+x 关于 m(x)=1+x+x 的同余加法和乘法 把x用2替换，1+x用3替换，就得： 用前面的公式 a(k)ij = k*i+j 对 k=1,2,3 进行计算可得： 把0用4替换，就得到3个4阶的正交拉丁方：,2011.11.09,23,Galois域GF(p ) 定理5-2 若u是GFp,m(x)的非零元素，则： pow(u,k)1，其中k=p -1 这表明非零元素的逆元素总存在。 定理5-3 若GFp,m(x)=a0,a1,a2,ak，其中a0=0, k=p -1，则有： (x-a0)(x-a1)(x-a2)(x-ak) = x(pow(x,k) 1) 这是多项式根与系数的关系的一种表达式。 正交拉丁方的构造 定理5-4 设m=p 2（且p是素数及n0）。则存在(m-1)个互相正交的拉丁方。 证明的过程就是就是构造的过程。设GFp,m(x)=a0,a1,a2,am，其中a0=0, m=p 。构造(m-1)个mxm矩阵A1,A2,如下： 第k个矩阵Ak = (Ak(i,j)，k=1,m-1，在(i,j)处的元素是 Ak(i,j) = ak * ai + aj, i=0,1,m-1, j=0,1,m-1 再用同余加法和同余乘法就可验证。 定理5-5 设n1的素数幂（因子）分解式是 n = pow(p1,a1) pow(p2,a2)pow(pk,ak) 若 m=min(pow(p1,a1) ,pow(pk,ak)-1 则有r个n阶的正交拉丁方。 从定理5-4可知对于n=3,4,5都有(n-1)个正交拉丁方。但当n=6时，我们不能从上 面定理中判断是否有正交拉丁方。,2011.11.09,24,正交拉丁方的构造 欧拉猜想：不存在6阶的正交拉丁方。直到1900年才获得证明。 定理5-6 设A1,A2,Ak是n阶正交拉丁方，B1,B2,Bk是m阶正交拉丁方。 则按下述方法构造的k个nxm阶矩阵也是正交拉丁方： Cr = (Cr(i,j), r=1,k，在位置(i,j)的值是 Cr(i,j) = (Ar(s,t)-1)*n + (Br(u,v)-1)*m + 1, r=1,k 其中角标(i,j)和(s,t),(u,v)之间的关系是： i = (s-1) * m + u, j = (t-1) * m + v 例子：,2011.11.09,25,正交拉丁方的应用举例 前面我们讨论了四种品牌的轮胎的测试问题，用四辆汽车进行测试，从而引进 了四节拉丁方： 若同时考察四种不同的刹车车闸对轮胎的磨损，则需满足下面测试安排： 每种牌子的轮胎在每辆汽车出现一次 轮胎在四个不同的位置上各出现一次 不同牌子的轮胎和车闸恰好配合一次 四种车闸在四辆车的四个不同位置分别出现一次。 下面二个拉丁方，第一个是轮胎的测试安排，第二个是车闸的测试安排：,2011.11.09,26,正交拉丁方的应用 下面的方阵是车轮与车闸的配合测试： 这个方阵是正交的，所有没有重复的一对数出现，即每种轮胎和每种车闸都恰 好配合一次。 假定有四种感冒药、四种退烧药和四种止咳药，试验它们的配合效果，找四位 病人，在四天内进行试验。如果只考虑一种感冒药的试验，可用四阶拉丁方： 其中A,B,C,D是病人代号，而 I, II, III, IV是日期。如果考虑二种药的配合，则需 要一对四阶的正交拉丁方，而三种药都考虑的话，则需要三个四阶正交的拉丁 方。,2011.11.09,27,均衡不完全的区间设计 基本概念 刚才我们讨论了四种品牌的轮胎，用四种汽车进行测试，每辆汽车上各种轮胎 一个，每辆汽车的被测试的轮胎称为一个区组。如果参加测试的轮胎有五个品 牌，但是汽车（一个区组）只有四个轮胎，每次只能测试四个轮胎，这样的测 试称为不完全的区组设计。我们可以用五辆汽车对五种轮胎按下面方式测试： 每一区组只包含四种轮胎，所以是不完全的，每种品牌都作了四次试验。 (b,v,r,k,)-设计 设X=x1,x2,xv是试验对象的集合，它包含v个元素。 所谓均衡不完全的区组，是指由X中的子集构成区组的集合。b为区组的个数， 即为B1,B2,Bb。每组包含X的k个元素，且满足下面条件： (1) X中的每一个元素在b组中正好出现r次； (2) 任意一对属于X的元素在b组中正好同时出现次； (3) k v； 满足上面条件的BIBD(Balanced Imcomplete Block Design)记为(b,v,r,k,)-设 计。,2011.11.09,28,均衡不完全的区间设计 例子： X=x1,x2,x7，分组如下： B1=x1,x2,x4； B2=x2,x3,x5； B3=x3,x4,x6； B4=x4,x5,x7； B5=x5,x6,x1； B6=x6,x7,x2； B7=x7,x1,x3; 它是7,7,3,3,1-设计。 为了讨论方便且不引起混乱，有时把xi简写为i，如上例可写为： B1:1 2 4；B2:2 3 5；B3:3 4 6；B4:4 5 7; B5:5 6 1；B6:6 7 2；B7:7 1 3； 定理5-8 (b,v,r,k,)-设计满足： bk = vr， r(k-1) = (v-1) 证明：(1) 每组k个元素，共b组，bk是元素出现的总次数；另外，集合X中的 v个元素，每个在b组中都出现r次，故vr也是元素出现的总次数， 所以它们相等：bk = vr。 (2) 集合X中某个元素x出现在r个组中，把x从这r个组中除去，则还剩下 r(k-1)个元素；又x与其他(v-1)个元素成对地出现在这r个组中，而且 每对出现次，故其它(v-1)个元素出现在这r个组中的次数就是 (v-1)，所以我们有：r(k-1) = (v-1)。,2011.11.09,29,均衡不完全的区间设计 区组矩阵 v个元素出现在b个组中，我们可以用0-1矩阵来描述，即 A=A(i,j), i1,b, j1,b 矩阵在(i,j)的位置的取值是： A(i,j) = 1, 如果第i个元素在第j个组里 否则：A(i,j) = 0 对于刚才的例子我们有： 定理5-8 对于(b,v,r,k,)-设计，下列等式成立： AA = ( r ) I + J 其中 I 是vv的单位矩阵，J是所有元素均为1的vv矩阵。 证明：矩阵AA 在位置(i,j)值就是A的第i行与第j行之积。按照矩阵A的定义就是 i号元素和j号元素在这二组中同时出现的次数。,2011.11.09,30,均衡不完全的区间设计 当ij时，是i号元素在b组中出现的次数，也就是r次； 当ij时，是i号元素和j号元素同时在b组中出现的次数，也就是次； 总结起来就是： = ( r )I + J 证毕 引理5-9 det(AA ) = (r+(v-1) pow(r-v,v-1)0。 对其使用消元法，可以很容易证明上面等式。 定理5-10 对于(b,v,r,k,)-设计，恒有 bv。 证明：用反证法，若不然，即bv，矩阵A的行多于列，增加(v-b)列到A里， 且新增元素全取值0，记新矩阵为B。因为A中二行的内积和B一样， 所以：det(AA ) = det(BB )。 因为B的新列都是0，故上式右边为0，但按引理5-9上式左边不是0。 这个矛盾反证了本定理。,2011.11.09,31,均衡不完全的区间设计 对称的BIBD： 当b=v时的BIBD称为对称BIBD。因bk=vr，故有k=r。 对称的BIBD记为(v,k,)-设计。 定理5-11 对称的BIBD的任意二组都正好有个共同元素。 区组设计的构成方法 定理5-12 若B1,B2,Bv是集合X=x1,x2,xv的对称BIBD，则(v-1)个区组 B2B1, B3B1, , BvB1 构成一个关于集合XB1的BIBD。 证明：显然若x属于某个BiB1，则它也属于XB1。同时，若x属于XB1，则 它仍然出现在k组中，XB1中的每对元素仍然同时出现次。最后， 由前一个定理可知，B2,Bv中每个区组与B1有个元素相同，这就 证明了B2B1,BvB1组成(v-1),(v-k),k,(k-),)-设计。,2011.11.09,32,区组设计的构成方法 定理5-13 若B1,B2,Bv是集合X=x1,x2,xv的对称BIBD，则(v-1)个区组 B2B1, B3B1 , , BvB1 构成一个关于集合XB1的BIBD。 证明：显然若x属于某个BiB1，则它也属于B1，所以x在 B2, B3 , , Bv 中的（k-1）组出现，即x在 B2B1, B3B1 , , BvB1 中的（k-1）组出现 B1中的任意一对元素，在这（v-1）个组中同时出现（-1）次。 同时，每个组BiB1中有个元素相同，这就证明了 B2B1, B3B1 , , BvB1 组成(v-1),k,k-1,-1)的BIBD。 从结论中，可以看到必须大于 1 。 例子：b=v=15, r=k=7, =3 B1：1,2,3,4,5,6,7 B2：1,2,3,8,9,10,11 B3：1,2,3,12,13,14,15 B4：1,4,5,8,9,12,13 B5：1,4,5,10,11,14,15 B6：1,6,7,8,9,14,15 B7：1,6,7,10,11,12,13 B8：2,4,6,8,10,12,14 B9：2,4,7,8,11,13,15 B10：2,5,6,9,11,12,15 B11：2,5,7,9,10,13,14 B12：3,4,6,9,11,13,14 B13：3,4,7,9,10,12,15 B14：3,5,6,8,10,13,15 B15：3,5,7,8,11,12,14,2011.11.09,33,区组设计的构成方法 前面的（15,7,3）对称BIBD，其区组矩阵为：,2011.11.09,34,区组设计的构成方法 这个矩阵的下面部分就是B2B1,B15B1：,2011.11.09,35,区组设计的构成方法 这个矩阵的上面部分就是B2B1,B15B1：,2011.11.09,36,Steiner三元系 k=3的区组设计称为三元系，（b,v,r,3,l)-设计存在的必要条件是： 3b = rv 和 2r = l(v-1) bk=rv, r(k-1)=l(v-1) 或改写为 r = l(v-1) / 2 和 b = rv/3 = lv(v-1) / 6。 因为 r 和 b 都是整数，所以 l(v-1) 是偶数，lv(v-1) 是6的倍数，即 l(v-1) 0 mod(2) 和 lv(v-1) 0 mod(6) 定义：l = 1的三元系称为斯梯纳（Steiner）三元系。 定理（科克曼 Kirkman）