英文
combinatorial design
简介
组合学的主要分支之一.200多年前，欧拉(Euler，L.)所讨论的拉丁方及正交拉丁方是组合设计的较早例子.更早的例子可追溯到中国古代的幻方(即纵横图).著名的柯克曼女生问题所涉及的可分解平衡不完全区组设计是又一个例子.这些早期的例子往往以智力游戏的原始形态出现.由于生产技术的需要，以及诸如试验设计与纠错码这样一些相近学科的发展，为组合设计理论的发展提供了强大的推动力.近20多年来，这一分支正处于迅速成长时期，不仅积累了大量的材料，而且逐步形成了以平衡不完全区组设计为主线，将各种类型的组合设计加以统一处理的理论体系.1985年以来，以设计理论或组合设计为题的专著已有多本.它与码和密码的联系也正在受到越来越多的关注，一份新的国际性杂志《设计、码和密码》(Designs，Codes and Cryptography)已于1991年创刊.设有限集X含v个元素x1，x2，…，xv，称这些元素为点或处理.设B1，B2，…，Bb是X的b个子集，称这些子集为区组，这一族子集记为B，并称对子(X，B)为一个区组设计.若每个区组的大小为k，每个点在r个区组中出现，并且每两个相异点恰同时出现在λ个区组中，则称这样的区组设计为平衡不完全区组设计.这一概念由玻色(Bose，R.C.)于1939年提出.20世纪60年代，哈拿匿(Hanani，H.)解决了当k值较小时，这一类设计的存在性问题.至20世纪70年代，威尔森(Wilson，R.M.)提出了PBD闭集的概念并解决了对一般k值以及v充分大时这一类设计的存在性.至于v充分大这一条件的确切描述已于1996年由常彦勋给出.
在设计理论的发展过程中，平衡不完全区组设计受到了几种不同方式的推广.若放弃区组有统一的大小k，而允许区组大小在一个正整数集合K中取值，则得到的设计称为成对平衡设计.这一类设计对解决关于正交拉丁方的欧拉猜想以及对威尔森的工作起过重要的作用.在此基础上形成的PBD闭集方法有着统一处理各种不同类型设计存在性问题的作用.另一方面，若不是要求两个相异点而是任一个t元子集恰同时出现在λ个区组中，则这样的设计称为t设计.若在区组内部引进点之间的邻接关系，即把区组看成一个图，则得到又一种推广，称为图设计或G设计.若点与点之间有不同的结合关系，有第i种结合关系的两点恰在λi个区组中同时出现，则这样的推广就是部分平衡不完全区组设计.除了这些形式的推广外，还有一些组合设计与平衡不完全区组设计有着各种各样的联系.例如，正交拉丁方在具体应用PBD闭集方法时起着重要的作用，而正交拉丁方的存在性也依赖于成对平衡设计的概念和方法.又如，阿达马矩阵与一类特殊的对称平衡不完全区组设计等价，而罗姆方则等价于一类双可分解的平衡不完全区组设计.
组合设计理论主要讨论各种类型的组合设计的性质、存在性、构造方法及相互关系等问题.设计的构造方法基本上可分为两类，即直接构造及递推构造.利用有限几何构造设计以及利用有限群构造设计是主要的直接构造方法.差集及混差法就是利用有限群构造设计的方法.
由于一些重要的码类常常与某种类型的组合设计有关，有些密码问题的理论分析也涉及某些组合设计，所以设计与码、设计与密码的相互联系近年来受到了特别的关注.将设计的关联矩阵在某个q元域上张成的子空间称为设计的码.这样就有可能通过研究码来研究设计.关于6阶正交拉丁方不存在性的一个简洁证明以及10阶射影平面的不存在性证明是这种研究途径的两个成功的例证.
作为组合学的一个分支，设计问题的研究时常要用到组合计数理论中的结果以及图论中的一些概念，并且，还需要有限群、有限域、有限域上的向量空间及射影空间等代数的和几何的概念和结果作为工具.随着计算机应用的进一步普及以及信息科学的进一步发展，离散数学的重要性将越来越多地被人们所认识.组合设计乃至组合学作为离散数学的重要组成部分将有着光明的发展前景.