Combinatorial design theory is the part of
combinatorial
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many ap ...
mathematics that deals with the existence, construction and properties of
systems of finite sets whose arrangements satisfy generalized concepts of ''balance'' and/or ''symmetry''. These concepts are not made precise so that a wide range of objects can be thought of as being under the same umbrella. At times this might involve the numerical sizes of set intersections as in
block designs, while at other times it could involve the spatial arrangement of entries in an array as in
sudoku grids.
Combinatorial design theory can be applied to the area of
design of experiments
The design of experiments (DOE, DOX, or experimental design) is the design of any task that aims to describe and explain the variation of information under conditions that are hypothesized to reflect the variation. The term is generally associ ...
. Some of the basic theory of combinatorial designs originated in the statistician
Ronald Fisher
Sir Ronald Aylmer Fisher (17 February 1890 – 29 July 1962) was a British polymath who was active as a mathematician, statistician, biologist, geneticist, and academic. For his work in statistics, he has been described as "a genius who ...
's work on the design of biological experiments. Modern applications are also found in a wide gamut of areas including
finite geometry
Finite is the opposite of infinite. It may refer to:
* Finite number (disambiguation)
* Finite set, a set whose cardinality (number of elements) is some natural number
* Finite verb, a verb form that has a subject, usually being inflected or marke ...
,
tournament scheduling,
lotteries
A lottery is a form of gambling that involves the drawing of numbers at random for a prize. Some governments outlaw lotteries, while others endorse it to the extent of organizing a national or state lottery. It is common to find some degree of ...
,
mathematical chemistry
Mathematical chemistry is the area of research engaged in novel applications of mathematics to chemistry; it concerns itself principally with the mathematical modeling of chemical phenomena. Mathematical chemistry has also sometimes been called co ...
,
mathematical biology,
algorithm design and analysis,
networking,
group testing
In statistics and combinatorial mathematics, group testing is any procedure that breaks up the task of identifying certain objects into tests on groups of items, rather than on individual ones. First studied by Robert Dorfman in 1943, group tes ...
and
cryptography
Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...
.
Example
![Fano plane](https://upload.wikimedia.org/wikipedia/commons/a/af/Fano_plane.svg)
Given a certain number ''n'' of people, is it possible to assign them to sets so that each person is in at least one set, each pair of people is in exactly one set together, every two sets have exactly one person in common, and no set contains everyone, all but one person, or exactly one person? The answer depends on ''n''.
This has a solution only if ''n'' has the form ''q''
2 + ''q'' + 1. It is less simple to prove that a solution exists if ''q'' is a
prime power
In mathematics, a prime power is a positive integer which is a positive integer power of a single prime number.
For example: , and are prime powers, while
, and are not.
The sequence of prime powers begins:
2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 17 ...
. It is conjectured that these are the ''only'' solutions. It has been further shown that if a solution exists for ''q'' congruent to 1 or 2
mod 4, then ''q'' is a sum of two
square numbers
In mathematics, a square number or perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 9 is a square number, since it equals and can be written as .
The us ...
. This last result, the
Bruck–Ryser theorem, is proved by a combination of constructive methods based on
finite field
In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtr ...
s and an application of
quadratic forms.
When such a structure does exist, it is called a finite
projective plane
In mathematics, a projective plane is a geometric structure that extends the concept of a plane. In the ordinary Euclidean plane, two lines typically intersect in a single point, but there are some pairs of lines (namely, parallel lines) that d ...
; thus showing how
finite geometry
Finite is the opposite of infinite. It may refer to:
* Finite number (disambiguation)
* Finite set, a set whose cardinality (number of elements) is some natural number
* Finite verb, a verb form that has a subject, usually being inflected or marke ...
and combinatorics intersect. When ''q'' = 2, the projective plane is called the
Fano plane
In finite geometry, the Fano plane (after Gino Fano) is a finite projective plane with the smallest possible number of points and lines: 7 points and 7 lines, with 3 points on every line and 3 lines through every point. These points and lines ...
.
History
Combinatorial designs date to antiquity, with the
Lo Shu Square
The Luoshu (pinyin), Lo Shu ( Wade-Giles), or Nine Halls Diagram is an ancient Chinese diagram and named for the Luo River near Luoyang, Henan. The Luoshu appears in myths concerning the invention of writing by Cangjie and other culture heroe ...
being an early
magic square. One of the earliest datable application of combinatorial design is found in India in the book ''Brhat Samhita'' by Varahamihira, written around 587 AD, for the purpose of making perfumes using 4 substances selected from 16 different substances using a magic square.
Combinatorial designs developed along with the general growth of
combinatorics from the 18th century, for example with
Latin square
In combinatorics and in experimental design, a Latin square is an ''n'' × ''n'' array filled with ''n'' different symbols, each occurring exactly once in each row and exactly once in each column. An example of a 3×3 Latin sq ...
s in the 18th century and
Steiner system
250px, thumbnail, The Fano plane is a Steiner triple system S(2,3,7). The blocks are the 7 lines, each containing 3 points. Every pair of points belongs to a unique line.
In combinatorial mathematics, a Steiner system (named after Jakob Steiner) ...
s in the 19th century. Designs have also been popular in
recreational mathematics
Recreational mathematics is mathematics carried out for recreation (entertainment) rather than as a strictly research and application-based professional activity or as a part of a student's formal education. Although it is not necessarily limited ...
, such as
Kirkman's schoolgirl problem
Kirkman's schoolgirl problem is a problem in combinatorics proposed by Rev. Thomas Penyngton Kirkman in 1850 as Query VI in '' The Lady's and Gentleman's Diary'' (pg.48). The problem states:
Fifteen young ladies in a school walk out three abre ...
(1850), and in practical problems, such as the scheduling of
round-robin tournaments (solution published 1880s). In the 20th century designs were applied to the
design of experiments
The design of experiments (DOE, DOX, or experimental design) is the design of any task that aims to describe and explain the variation of information under conditions that are hypothesized to reflect the variation. The term is generally associ ...
, notably Latin squares,
finite geometry
Finite is the opposite of infinite. It may refer to:
* Finite number (disambiguation)
* Finite set, a set whose cardinality (number of elements) is some natural number
* Finite verb, a verb form that has a subject, usually being inflected or marke ...
, and
association schemes, yielding the field of
algebraic statistics.
Fundamental combinatorial designs
The classical core of the subject of combinatorial designs is built around
balanced incomplete block designs (BIBDs),
Hadamard matrices and Hadamard designs,
symmetric BIBDs,
Latin square
In combinatorics and in experimental design, a Latin square is an ''n'' × ''n'' array filled with ''n'' different symbols, each occurring exactly once in each row and exactly once in each column. An example of a 3×3 Latin sq ...
s,
resolvable BIBDs,
difference sets, and pairwise balanced designs (PBDs). Other combinatorial designs are related to or have been developed from the study of these fundamental ones.
* A balanced incomplete block design or BIBD (usually called for short a
block design) is a collection ''B'' of ''b'' subsets (called ''blocks'') of a finite set ''X'' of ''v'' elements, such that any element of ''X'' is contained in the same number ''r'' of blocks, every block has the same number ''k'' of elements, and each pair of distinct elements appear together in the same number λ of blocks. BIBDs are also known as ''2-designs'' and are often denoted as 2-(''v'',''k'',λ) designs. As an example, when λ = 1 and ''b'' = ''v'', we have a
projective plane
In mathematics, a projective plane is a geometric structure that extends the concept of a plane. In the ordinary Euclidean plane, two lines typically intersect in a single point, but there are some pairs of lines (namely, parallel lines) that d ...
: ''X'' is the point set of the plane and the blocks are the lines.
* A symmetric balanced incomplete block design or
SBIBD is a BIBD in which ''v'' = ''b'' (the number of points equals the number of blocks). They are the single most important and well studied subclass of BIBDs. Projective planes, biplanes and Hadamard 2-designs are all SBIBDs. They are of particular interest since they are the extremal examples of
Fisher's inequality Fisher's inequality is a necessary condition for the existence of a balanced incomplete block design, that is, a system of subsets that satisfy certain prescribed conditions in combinatorial mathematics. Outlined by Ronald Fisher, a population genet ...
(''b'' ≥ ''v'').
* A
resolvable BIBD is a BIBD whose blocks can be partitioned into sets (called ''parallel classes''), each of which forms a partition of the point set of the BIBD. The set of parallel classes is called a ''resolution'' of the design. A solution of the famous
15 schoolgirl problem is a resolution of a BIBD with ''v'' = 15, ''k'' = 3 and λ = 1.
* A
Latin rectangle In combinatorial mathematics, a Latin rectangle is an matrix (where ), using symbols, usually the numbers or as its entries, with no number occurring more than once in any row or column.
An Latin rectangle is called a Latin square.
An example ...
is an ''r'' × ''n''
matrix that has the numbers 1, 2, 3, ..., ''n'' as its entries (or any other set of ''n'' distinct symbols) with no number occurring more than once in any row or column where ''r'' ≤ ''n''. An ''n'' × ''n'' Latin rectangle is called a
Latin square
In combinatorics and in experimental design, a Latin square is an ''n'' × ''n'' array filled with ''n'' different symbols, each occurring exactly once in each row and exactly once in each column. An example of a 3×3 Latin sq ...
. If ''r'' < ''n'', then it is possible to append ''n'' − ''r'' rows to an ''r'' × ''n'' Latin rectangle to form a Latin square, using
Hall's marriage theorem
In mathematics, Hall's marriage theorem, proved by , is a theorem with two equivalent formulations:
* The combinatorial formulation deals with a collection of finite sets. It gives a necessary and sufficient condition for being able to select a di ...
.
:Two Latin squares of order ''n'' are said to be ''orthogonal'' if the set of all ordered pairs consisting of the corresponding entries in the two squares has ''n''
2 distinct members (all possible ordered pairs occur). A set of Latin squares of the same order forms a set of
mutually orthogonal Latin squares (MOLS) if every pair of Latin squares in the set are orthogonal. There can be at most ''n'' − 1 squares in a set of MOLS of order ''n''. A set of ''n'' − 1 MOLS of order ''n'' can be used to construct a
projective plane
In mathematics, a projective plane is a geometric structure that extends the concept of a plane. In the ordinary Euclidean plane, two lines typically intersect in a single point, but there are some pairs of lines (namely, parallel lines) that d ...
of order ''n'' (and conversely).
* A (''v'', ''k'', λ)
difference set is a
subset D of a
group
A group is a number of persons or things that are located, gathered, or classed together.
Groups of people
* Cultural group, a group whose members share the same cultural identity
* Ethnic group, a group whose members share the same ethnic ide ...
G such that the
order of G is ''v'', the
size
Size in general is the magnitude or dimensions of a thing. More specifically, ''geometrical size'' (or ''spatial size'') can refer to linear dimensions ( length, width, height, diameter, perimeter), area, or volume. Size can also be m ...
of D is ''k'', and every nonidentity element of G can be expressed as a product ''d''
1''d''
2−1 of elements of D in exactly λ ways (when G is written with a multiplicative operation).
:If D is a difference set, and ''g'' in G, then ''g'' D = is also a difference set, and is called a translate of D. The set of all translates of a difference set D forms a
symmetric block design. In such a design there are ''v'' elements and ''v'' blocks. Each block of the design consists of ''k'' points, each point is contained in ''k'' blocks. Any two blocks have exactly λ elements in common and any two points appear together in λ blocks. This SBIBD is called the ''development'' of D.
:In particular, if λ = 1, then the difference set gives rise to a
projective plane
In mathematics, a projective plane is a geometric structure that extends the concept of a plane. In the ordinary Euclidean plane, two lines typically intersect in a single point, but there are some pairs of lines (namely, parallel lines) that d ...
. An example of a (7,3,1) difference set in the group
(an abelian group written additively) is the subset . The development of this difference set gives the
Fano plane
In finite geometry, the Fano plane (after Gino Fano) is a finite projective plane with the smallest possible number of points and lines: 7 points and 7 lines, with 3 points on every line and 3 lines through every point. These points and lines ...
.
:Since every difference set gives an SBIBD, the parameter set must satisfy the
Bruck–Ryser–Chowla theorem, but not every SBIBD gives a difference set.
* An
Hadamard matrix
In mathematics, a Hadamard matrix, named after the French mathematician Jacques Hadamard, is a square matrix whose entries are either +1 or −1 and whose rows are mutually orthogonal. In geometric terms, this means that each pair of rows ...
of order ''m'' is an ''m'' × ''m'' matrix H whose entries are ±1 such that HH
⊤ = ''m''I
''m'', where H
⊤ is the transpose of H and I
''m'' is the ''m'' × ''m'' identity matrix. An Hadamard matrix can be put into ''standardized form'' (that is, converted to an equivalent Hadamard matrix) where the first row and first column entries are all +1. If the order ''m'' > 2 then ''m'' must be a multiple of 4.
:Given an Hadamard matrix of order 4''a'' in standardized form, remove the first row and first column and convert every −1 to a 0. The resulting 0–1 matrix M is the
incidence matrix
In mathematics, an incidence matrix is a logical matrix that shows the relationship between two classes of objects, usually called an incidence relation. If the first class is ''X'' and the second is ''Y'', the matrix has one row for each element ...
of a symmetric 2 − (4''a'' − 1, 2''a'' − 1, ''a'' − 1) design called an Hadamard 2-design. This construction is reversible, and the incidence matrix of a symmetric 2-design with these parameters can be used to form an Hadamard matrix of order 4''a''. When ''a'' = 2 we obtain the, by now familiar,
Fano plane
In finite geometry, the Fano plane (after Gino Fano) is a finite projective plane with the smallest possible number of points and lines: 7 points and 7 lines, with 3 points on every line and 3 lines through every point. These points and lines ...
as an Hadamard 2-design.
* A pairwise balanced design (or PBD) is a set ''X'' together with a family of subsets of ''X'' (which need not have the same size and may contain repeats) such that every pair of distinct elements of ''X'' is contained in exactly λ (a positive integer) subsets. The set ''X'' is allowed to be one of the subsets, and if all the subsets are copies of ''X'', the PBD is called ''trivial''. The size of ''X'' is ''v'' and the number of subsets in the family (counted with multiplicity) is ''b''.
:
Fisher's inequality Fisher's inequality is a necessary condition for the existence of a balanced incomplete block design, that is, a system of subsets that satisfy certain prescribed conditions in combinatorial mathematics. Outlined by Ronald Fisher, a population genet ...
holds for PBDs: For any non-trivial PBD, ''v'' ≤ ''b''.
:This result also generalizes the famous
Erdős–De Bruijn theorem: For a PBD with ''λ'' = 1 having no blocks of size 1 or size ''v'', ''v'' ≤ ''b'', with equality if and only if the PBD is a
projective plane
In mathematics, a projective plane is a geometric structure that extends the concept of a plane. In the ordinary Euclidean plane, two lines typically intersect in a single point, but there are some pairs of lines (namely, parallel lines) that d ...
or a near-pencil.
Other combinatorial designs
The ''Handbook of Combinatorial Designs'' has, amongst others, 65 chapters, each devoted to a combinatorial design other than those given above. A partial listing is given below:
*
Association schemes
* A balanced ternary design BTD(''V'', ''B''; ''ρ''
1, ''ρ''
2, ''R''; ''K'', Λ) is an arrangement of ''V'' elements into ''B''
multiset
In mathematics, a multiset (or bag, or mset) is a modification of the concept of a set that, unlike a set, allows for multiple instances for each of its elements. The number of instances given for each element is called the multiplicity of that e ...
s (blocks), each of cardinality ''K'' (''K'' ≤ ''V''), satisfying:
# Each element appears ''R'' = ''ρ''
1 + 2''ρ''
2 times altogether, with multiplicity one in exactly ''ρ''
1 blocks and multiplicity two in exactly ''ρ''
2 blocks.
# Every pair of distinct elements appears Λ times (counted with multiplicity); that is, if ''m''
''vb'' is the multiplicity of the element ''v'' in block ''b'', then for every pair of distinct elements ''v'' and ''w'',
.
:For example, one of the only two nonisomorphic BTD(4,8;2,3,8;4,6)s (blocks are columns) is:
:The
incidence matrix
In mathematics, an incidence matrix is a logical matrix that shows the relationship between two classes of objects, usually called an incidence relation. If the first class is ''X'' and the second is ''Y'', the matrix has one row for each element ...
of a BTD (where the entries are the multiplicities of the elements in the blocks) can be used to form a ternary error-correcting code analogous to the way binary codes are formed from the incidence matrices of BIBDs.
* A of order ''n'' (a BTD(''n'')) is an arrangement of all the distinct unordered pairs of a 2''n''-set ''V'' into an ''n'' × (2''n'' − 1) array such that
# every element of ''V'' appears precisely once in each column, and
# every element of ''V'' appears at most twice in each row.
:An example of a BTD(3) is given by
:The columns of a BTD(''n'') provide a
1-factorization of the complete graph on 2''n'' vertices, ''K''
2''n''.
:BTD(''n'')s can be used to schedule
round-robin tournaments: the rows represent the locations, the columns the rounds of play and the entries are the competing players or teams.
*
Bent function
In the mathematical field of combinatorics, a bent function is a special type of Boolean function which is maximally non-linear; it is as different as possible from the set of all linear and affine functions when measured by Hamming distance bet ...
s
*
Costas array
In mathematics, a Costas array can be regarded geometrically as a set of ''n'' points, each at the center of a square in an ''n''×''n'' square tiling such that each row or column contains only one point, and all of the ''n''(''n'' &minu ...
s
*
Factorial design
In statistics, a full factorial experiment is an experiment whose design consists of two or more factors, each with discrete possible values or "levels", and whose experimental units take on all possible combinations of these levels across all ...
s
* A frequency square (F-square) is a higher order generalization of a
Latin square
In combinatorics and in experimental design, a Latin square is an ''n'' × ''n'' array filled with ''n'' different symbols, each occurring exactly once in each row and exactly once in each column. An example of a 3×3 Latin sq ...
. Let ''S'' = be a set of distinct symbols and (''λ''
1, ''λ''
2, ...,''λ''
''m'') a ''frequency vector'' of positive integers. A ''frequency square'' of order ''n'' is an ''n'' × ''n'' array in which each symbol ''s''
''i'' occurs ''λ''
''i'' times, ''i'' = 1,2,...,''m'', in each row and column. The ''order'' ''n'' = ''λ''
1 + ''λ''
2 + ... + ''λ''
''m''. An F-square is in ''standard form'' if in the first row and column, all occurrences of ''s''
''i'' precede those of ''s''
''j'' whenever ''i'' < ''j''.
:A frequency square ''F''
1 of order ''n'' based on the set with frequency vector (''λ''
1, ''λ''
2, ...,''λ''
''m'') and a frequency square ''F''
2, also of order ''n'', based on the set with frequency vector (''μ''
1, ''μ''
2, ...,''μ''
''k'') are ''orthogonal'' if every ordered pair (''s''
''i'', ''t''
''j'') appears precisely ''λ''
''i''''μ''
''j'' times when ''F''
1 and ''F''
2 are superimposed.
* Hall triple systems (HTSs) are
Steiner triple systems (STSs) (but the blocks are called ''lines'') with the property that the substructure generated by two intersecting lines is isomorphic to the
finite affine plane AG(2,3).
:Any affine space AG(''n'',3) gives an example of an HTS. Such an HTS is an ''affine'' HTS. Nonaffine HTSs also exist.
:The number of points of an HTS is 3
m for some integer ''m'' ≥ 2. Nonaffine HTSs exist for any ''m'' ≥ 4 and do not exist for ''m'' = 2 or 3.
:Every Steiner triple system is equivalent to a Steiner
quasigroup
In mathematics, especially in abstract algebra, a quasigroup is an algebraic structure resembling a group in the sense that " division" is always possible. Quasigroups differ from groups mainly in that they need not be associative and need not have ...
(
idempotent
Idempotence (, ) is the property of certain operations in mathematics and computer science whereby they can be applied multiple times without changing the result beyond the initial application. The concept of idempotence arises in a number of pl ...
,
commutative
In mathematics, a binary operation is commutative if changing the order of the operands does not change the result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it. Most familiar as the name of ...
and satisfying (''xy'')''y'' = ''x'' for all ''x'' and ''y''). A Hall triple system is equivalent to a Steiner quasigroup which is
distributive, that is, satisfies for all ''a'',''x'',''y'' in the quasigroup.
* Let ''S'' be a set of 2''n'' elements. A Howell design, H(''s'',2''n'') (on symbol set ''S'') is an ''s'' × ''s'' array such that:
# Each cell of the array is either empty or contains an unordered pair from ''S'',
# Each symbol occurs exactly once in each row and column of the array, and
# Every unordered pair of symbols occurs in at most one cell of the array.
:An example of an ''H''(4,6) is
:An H(2''n'' − 1, 2''n'') is a
Room square of side 2''n'' − 1, and thus the Howell designs generalize the concept of Room squares.
:The pairs of symbols in the cells of a Howell design can be thought of as the edges of an ''s'' regular graph on 2''n'' vertices, called the ''underlying graph'' of the Howell design.
:Cyclic Howell designs are used as ''Howell movements'' in duplicate bridge tournaments. The rows of the design represent the rounds, the columns represent the boards, and the diagonals represent the tables.
*
Linear spaces
* An (''n'',''k'',''p'',''t'')-lotto design is an ''n''-set ''V'' of elements together with a set β of ''k''-element subsets of ''V'' (blocks), so that for any ''p''-subset P of ''V'', there is a block B in ''β'' for which , P ∩ B , ≥ ''t''. L(''n'',''k'',''p'',''t'') denotes the smallest number of blocks in any (''n'',''k'',''p'',''t'')-lotto design. The following is a (7,5,4,3)-lotto design with the smallest possible number of blocks:
:: .
:Lotto designs model any
lottery that is run in the following way: Individuals purchase ''tickets'' consisting of ''k'' numbers chosen from a set of ''n'' numbers. At a certain point the sale of tickets is stopped and a set of ''p'' numbers is randomly selected from the ''n'' numbers. These are the ''winning numbers''. If any sold ticket contains ''t'' or more of the winning numbers, a prize is given to the ticket holder. Larger prizes go to tickets with more matches. The value of L(''n'',''k'',''p'',''t'') is of interest to both gamblers and researchers, as this is the smallest number of tickets that are needed to be purchased in order to guarantee a prize.
:The Hungarian Lottery is a (90,5,5,''t'')-lotto design and it is known that L(90,5,5,2) = 100. Lotteries with parameters (49,6,6,''t'') are also popular worldwide and it is known that L(49,6,6,2) = 19. In general though, these numbers are hard to calculate and remain unknown.
:A geometric construction of one such design is given in
Transylvanian lottery.
*
Magic squares
* A (''v'',''k'',''λ'')-Mendelsohn design, or MD(''v'',''k'',''λ''),is a ''v''-set ''V'' and a collection β of ordered ''k''-tuples of distinct elements of ''V'' (called ''blocks''), such that each ordered pair (''x'',''y'') with ''x'' ≠ ''y'' of elements of ''V'' is cyclically adjacent in ''λ'' blocks. The ordered pair (''x'',''y'') of distinct elements is ''cyclically adjacent'' in a block if the elements appear in the block as (...,''x'',''y'',...) or (''y'',...,''x''). An MD(''v'',3,''λ'') is a Mendelsohn triple system, MTS(''v'',''λ''). An example of an MTS(4,1) on V = is:
:: (0,1,2) (1,0,3) (2,1,3) (0,2,3)
:Any triple system can be made into a Mendelson triple system by replacing the unordered triple with the pair of ordered triples (''a'',''b'',''c'') and (''a'',''c'',''b''), but as the example shows, the converse of this statement is not true.
:If (''Q'',∗) is an idempotent semisymmetric
quasigroup
In mathematics, especially in abstract algebra, a quasigroup is an algebraic structure resembling a group in the sense that " division" is always possible. Quasigroups differ from groups mainly in that they need not be associative and need not have ...
, that is, ''x'' ∗ ''x'' = ''x'' (idempotent) and ''x'' ∗ (''y'' ∗ ''x'') = ''y'' (semisymmetric) for all ''x'', ''y'' in ''Q'', let β = . Then (''Q'', β) is a Mendelsohn triple system MTS(, ''Q'', ,1). This construction is reversible.
*
Orthogonal arrays
* A quasi-3 design is a symmetric design (SBIBD) in which each triple of blocks intersect in either ''x'' or ''y'' points, for fixed ''x'' and ''y'' called the ''triple intersection numbers'' (''x'' < ''y''). Any symmetric design with ''λ'' ≤ 2 is a quasi-3 design with ''x'' = 0 and ''y'' = 1. The point-hyperplane design of
PG(''n'',''q'') is a quasi-3 design with ''x'' = (''q''
''n''−2 − 1)/(''q'' − 1) and ''y'' = ''λ'' = (''q''
''n''−1 − 1)/(''q'' − 1). If ''y'' = ''λ'' for a quasi-3 design, the design is isomorphic to PG(''n'',''q'') or a
projective plane
In mathematics, a projective plane is a geometric structure that extends the concept of a plane. In the ordinary Euclidean plane, two lines typically intersect in a single point, but there are some pairs of lines (namely, parallel lines) that d ...
.
* A ''t''-(''v'',''k'',''λ'') design ''D'' is quasi-symmetric with intersection numbers ''x'' and ''y'' (''x'' < ''y'') if every two distinct blocks intersect in either ''x'' or ''y'' points. These designs naturally arise in the investigation of the duals of designs with ''λ'' = 1. A non-symmetric (''b'' > ''v'') 2-(''v'',''k'',1) design is quasisymmetric with ''x'' = 0 and ''y'' = 1. A multiple (repeat all blocks a certain number of times) of a symmetric 2-(''v'',''k'',''λ'') design is quasisymmetric with ''x'' = ''λ'' and ''y'' = ''k''. Hadamard 3-designs (extensions of
Hadamard 2-designs) are quasisymmetric.
:Every quasisymmetric block design gives rise to a
strongly regular graph
In graph theory, a strongly regular graph (SRG) is defined as follows. Let be a regular graph with vertices and degree . is said to be strongly regular if there are also integers and such that:
* Every two adjacent vertices have comm ...
(as its block graph), but not all SRGs arise in this way.
:The
incidence matrix
In mathematics, an incidence matrix is a logical matrix that shows the relationship between two classes of objects, usually called an incidence relation. If the first class is ''X'' and the second is ''Y'', the matrix has one row for each element ...
of a quasisymmetric 2-(''v'',''k'',''λ'') design with ''k'' ≡ ''x'' ≡ ''y'' (mod 2) generates a binary self-orthogonal
code (when bordered if ''k'' is odd).
*
Room squares
* A
spherical design is a finite set ''X'' of points in a (''d'' − 1)-dimensional
sphere
A sphere () is a geometrical object that is a three-dimensional analogue to a two-dimensional circle. A sphere is the set of points that are all at the same distance from a given point in three-dimensional space.. That given point is th ...
such that, for some integer ''t'', the average value on ''X'' of every polynomial
::
:of total degree at most ''t'' is equal to the average value of ''f'' on the whole sphere, i.e., the
integral
In mathematics, an integral assigns numbers to functions in a way that describes displacement, area, volume, and other concepts that arise by combining infinitesimal data. The process of finding integrals is called integration. Along wit ...
of ''f'' divided by the area of the sphere.
*
Turán systems
* An ''r'' × ''n'' tuscan-''k'' rectangle on ''n'' symbols has ''r'' rows and ''n'' columns such that:
# each row is a permutation of the ''n'' symbols and
# for any two distinct symbols ''a'' and ''b'' and for each ''m'' from 1 to ''k'', there is at most one row in which ''b'' is ''m'' steps to the right of ''a''.
: If ''r'' = ''n'' and ''k'' = 1 these are referred to as Tuscan squares, while if ''r'' = ''n'' and ''k'' = ''n'' - 1 they are Florentine squares. A Roman square is a Tuscan square which is also a
latin square
In combinatorics and in experimental design, a Latin square is an ''n'' × ''n'' array filled with ''n'' different symbols, each occurring exactly once in each row and exactly once in each column. An example of a 3×3 Latin sq ...
(these are also known as ''row complete Latin squares''). A Vatican square is a Florentine square which is also a Latin square.
: The following example is a tuscan-1 square on 7 symbols which is not tuscan-2:
:A tuscan square on ''n'' symbols is equivalent to a decomposition of the complete graph with ''n'' vertices into ''n'' hamiltonian directed paths.
:In a sequence of visual impressions, one flash card may have some effect on the impression given by the next. This bias can be cancelled by using ''n'' sequences corresponding to the rows of an ''n'' × ''n'' tuscan-1 square.
* A t-wise balanced design (or ''t'' BD) of type ''t'' − (''v'',K,''λ'') is a ''v''-set ''X'' together with a family of subsets of ''X'' (called ''blocks'') whose sizes are in the set K, such that every ''t''-subset of distinct elements of ''X'' is contained in exactly ''λ'' blocks. If K is a set of positive integers strictly between ''t'' and ''v'', then the ''t'' BD is ''proper''. If all the ''k''-subsets of ''X'' for some ''k'' are blocks, the ''t'' BD is a ''trivial design''.
:Notice that in the following example of a 3-
{12,{4,6},1) design based on the set ''X'' = {1,2,...,12}, some pairs appear four times (such as 1,2) while others appear five times (6,12 for instance).
:: 1 2 3 4 5 6 1 2 7 8 1 2 9 11 1 2 10 12 3 5 7 8 3 5 9 11 3 5 10 12 4 6 7 8 4 6 9 11 4 6 10 12
:: 7 8 9 10 11 12 2 3 8 9 2 3 10 7 2 3 11 12 4 1 8 9 4 1 10 7 4 1 11 12 5 6 8 9 5 6 10 7 5 6 11 12
:: 3 4 9 10 3 4 11 8 3 4 7 12 5 2 9 10 5 2 11 8 5 2 7 12 1 6 9 10 1 6 11 8 1 6 7 12
:: 4 5 10 11 4 5 7 9 4 5 8 12 1 3 10 11 1 3 7 9 1 3 8 12 2 6 10 11 2 6 7 9 2 6 8 12
:: 5 1 11 7 5 1 8 10 5 1 9 12 2 4 11 7 2 4 8 10 2 4 9 12 3 6 11 7 3 6 8 10 3 6 9 12
*
Weighing matrices, A generalization of Hadamard matrices that allows zero entries, are used in some combinatoric designs. In particular, the design of experiments for estimating the individual weights of multiple objects in few trials.
* A Youden square is a ''k'' × ''v'' ''rectangular'' array (''k'' < ''v'') of ''v'' symbols such that each symbol appears exactly once in each row and the symbols appearing in any column form a block of a symmetric (''v'', ''k'', ''λ'') design, all the blocks of which occur in this manner. A Youden square is a Latin rectangle. The term "square" in the name comes from an older definition which did use a square array.
An example of a 4 × 7 Youden square is given by:
{, class="wikitable" style="margin:1em auto;"
, 1 , , 2 , , 3 , , 4 , , 5 , , 6 , , 7
, -
, 2 , , 3 , , 4 , , 5 , , 6 , , 7 , , 1
, -
, 3 , , 4 , , 5 , , 6 , , 7 , , 1 , , 2
, -
, 5 , , 6 , , 7 , , 1 , , 2 , , 3 , , 4
:The seven blocks (columns) form the order 2
biplane (a symmetric (7,4,2)-design).
See also
*
Algebraic statistics
*
Hypergraph
In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices. In contrast, in an ordinary graph, an edge connects exactly two vertices.
Formally, an undirected hypergraph H is a pair H = (X,E) w ...
*
Williamson conjecture
Notes
References
*
*. 2nd ed. (1999) .
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
{{Incidence structures
Families of sets
Design of experiments