Combinatorial design theory is the part ofcombinatorialmathematics that deals with the existence, construction and properties ofsystems of finite sets whose arrangements satisfy generalized concepts ofbalance and/orsymmetry. 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 inblock designs, while at other times it could involve the spatial arrangement of entries in an array as insudoku grids.

Combinatorial design theory can be applied to the area ofdesign of experiments. Some of the basic theory of combinatorial designs originated in the statisticianRonald Fisher's work on the design of biological experiments. Modern applications are also found in a wide gamut of areas includingfinite geometry,tournament scheduling,lotteries,mathematical chemistry,mathematical biology,algorithm design and analysis,networking,group testing andcryptography.^[1]

Given a certain numbern 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 onn.

This has a solution only ifn has the formq² +q + 1. It is less simple to prove that a solution exists ifq is aprime power. It is conjectured that these are theonly solutions. It has been further shown that if a solution exists forq congruent to 1 or 2mod 4, thenq is a sum of twosquare numbers. This last result, theBruck–Ryser theorem, is proved by a combination of constructive methods based onfinite fields and an application ofquadratic forms.

When such a structure does exist, it is called a finiteprojective plane; thus showing howfinite geometry and combinatorics intersect. Whenq = 2, the projective plane is called theFano plane.

Combinatorial designs date to antiquity, with theLo Shu Square being an earlymagic square. One of the earliest datable application of combinatorial design is found in India in the bookBrhat 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.^[2]

Combinatorial designs developed along with the general growth ofcombinatorics from the 18th century, for example withLatin squares in the 18th century andSteiner systems in the 19th century. Designs have also been popular inrecreational mathematics, such asKirkman's schoolgirl problem (1850), and in practical problems, such as the scheduling ofround-robin tournaments (solution published 1880s). In the 20th century designs were applied to thedesign of experiments, notably Latin squares,finite geometry, andassociation schemes, yielding the field ofalgebraic statistics.

The classical core of the subject of combinatorial designs is built aroundbalanced incomplete block designs (BIBDs),Hadamard matrices and Hadamard designs,symmetric BIBDs,Latin squares,resolvable BIBDs,difference sets, and pairwise balanced designs (PBDs).^[3] Other combinatorial designs are related to or have been developed from the study of these fundamental ones.

• Abalanced incomplete block design or BIBD (usually called for short ablock design) is a collectionB ofb subsets (calledblocks) of a finite setX ofv elements, such that any element ofX is contained in the same numberr of blocks, every block has the same numberk of elements, and each pair of distinct elements appear together in the same number λ of blocks. BIBDs are also known as2-designs and are often denoted as 2-(v,k,λ) designs. As an example, when λ = 1 andb =v, we have aprojective plane:X is the point set of the plane and the blocks are the lines.
• Asymmetric balanced incomplete block design orSBIBD is a BIBD in whichv  = 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 ofFisher's inequality (b ≥v).
• Aresolvable BIBD is a BIBD whose blocks can be partitioned into sets (calledparallel classes), each of which forms a partition of the point set of the BIBD. The set of parallel classes is called aresolution of the design. A solution of the famous15 schoolgirl problem is a resolution of a BIBD withv  = 15,k  = 3 and λ = 1.^[4]
• ALatin rectangle is anr × nmatrix that has the numbers 1, 2, 3, ..., n as its entries (or any other set ofn distinct symbols) with no number occurring more than once in any row or column where r ≤ n. Ann × n Latin rectangle is called aLatin square. Ifr < n, then it is possible to appendn − r rows to anr × n Latin rectangle to form a Latin square, usingHall's marriage theorem.^[5]

Two Latin squares of ordern are said to beorthogonal if the set of all ordered pairs consisting of the corresponding entries in the two squares hasn² distinct members (all possible ordered pairs occur). A set of Latin squares of the same order forms a set ofmutually orthogonal Latin squares (MOLS) if every pair of Latin squares in the set are orthogonal. There can be at mostn − 1 squares in a set of MOLS of ordern. A set ofn − 1 MOLS of ordern can be used to construct aprojective plane of ordern (and conversely).

• A (v,k, λ)difference set is asubsetD of agroupG such that theorder ofG isv, thesize ofD isk, and every nonidentity element ofG can be expressed as a productd₁d₂⁻¹ of elements ofD in exactly λ ways (whenG is written with a multiplicative operation).^[6]

IfD is a difference set, andg inG, thengD = {gd:d inD} is also a difference set, and is called atranslate ofD. The set of all translates of a difference setD forms asymmetric BIBD. In such a design there arev elements andv blocks. Each block of the design consists ofk points, each point is contained ink blocks. Any two blocks have exactly λ elements in common and any two points appear together in λ blocks. This SBIBD is called thedevelopment ofD.^[7]

In particular, if λ = 1, then the difference set gives rise to aprojective plane. An example of a (7,3,1) difference set in the group${\displaystyle \mathbb{Z}/7\mathbb{Z}}$ (an abelian group written additively) is the subset {1,2,4}. The development of this difference set gives theFano plane.

Since every difference set gives an SBIBD, the parameter set must satisfy theBruck–Ryser–Chowla theorem, but not every SBIBD gives a difference set.

• AnHadamard matrix of orderm is anm ×m matrixH whose entries are ±1 such thatHH^⊤  = mI_m, whereH^⊤ is the transpose ofH andI_m is them × m identity matrix. An Hadamard matrix can be put intostandardized form (that is, converted to an equivalent Hadamard matrix) where the first row and first column entries are all +1. If the orderm > 2 thenm must be a multiple of 4.

Given an Hadamard matrix of order 4a in standardized form, remove the first row and first column and convert every −1 to a 0. The resulting 0–1 matrixM is theincidence matrix of a symmetric 2 − (4a − 1, 2a − 1,a − 1) design called anHadamard 2-design.^[8] 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 4a. Whena = 2 we obtain the, by now familiar,Fano plane as an Hadamard 2-design.

• Apairwise balanced design (or PBD) is a setX together with a family of subsets ofX (which need not have the same size and may contain repeats) such that every pair of distinct elements ofX is contained in exactly λ (a positive integer) subsets. The setX is allowed to be one of the subsets, and if all the subsets are copies ofX, the PBD is calledtrivial. The size ofX isv and the number of subsets in the family (counted with multiplicity) is b.

Fisher's inequality holds for PBDs:^[9] For any non-trivial PBD,v ≤ b.

This result also generalizes the famousErdő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 aprojective plane or a near-pencil.^[10]

TheHandbook of Combinatorial Designs (Colbourn & Dinitz 2007) has, amongst others, 65 chapters, each devoted to a combinatorial design other than those given above. A partial listing is given below:

• Association schemes
• Abalanced ternary design BTD(V,B;ρ₁,ρ₂,R;K, Λ) is an arrangement ofV elements intoBmultisets (blocks), each of cardinalityK (K ≤V), satisfying:

1. Each element appearsR =ρ₁ + 2ρ₂ times altogether, with multiplicity one in exactlyρ₁ blocks and multiplicity two in exactlyρ₂ blocks.
2. Every pair of distinct elements appears Λ times (counted with multiplicity); that is, ifm_vb is the multiplicity of the elementv in blockb, then for every pair of distinct elementsv andw,${\displaystyle \sum _{b=1}^B{m}_{vb}{m}_{wb}=\mathrm{\Lambda }}$.

For example, one of the only two nonisomorphic BTD(4,8;2,3,8;4,6)s (blocks are columns) is:^[11]

Theincidence matrix 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.^[12]

• Abalanced tournament design of ordern (a BTD(n)) is an arrangement of all the distinct unordered pairs of a 2n-setV into ann × (2n − 1) array such that

1. every element ofV appears precisely once in each column, and
2. every element ofV appears at most twice in each row.

An example of a BTD(3) is given by

The columns of a BTD(n) provide a1-factorization of the complete graph on 2n vertices,K_2n.^[13]

BTD(n)s can be used to scheduleround-robin tournaments: the rows represent the locations, the columns the rounds of play and the entries are the competing players or teams.

• Bent functions
• Costas arrays
• Factorial designs
• Afrequency square (F-square) is a higher order generalization of aLatin square. LetS = {s₁,s₂, ...,s_m} be a set of distinct symbols and (λ₁,λ₂, ...,λ_m) afrequency vector of positive integers. Afrequency square of ordern is ann ×n array in which each symbols_i occursλ_i times,i = 1,2,...,m, in each row and column. Theordern =λ₁ + λ₂ + ... + λ_m. An F-square is instandard form if in the first row and column, all occurrences ofs_i precede those ofs_j wheneveri < j.

A frequency squareF₁ of ordern based on the set {s₁,s₂, ...,s_m} with frequency vector (λ₁,λ₂, ...,λ_m) and a frequency squareF₂, also of ordern, based on the set {t₁,t₂, ...,t_k} with frequency vector (μ₁,μ₂, ...,μ_k) areorthogonal if every ordered pair (s_i,t_j) appears preciselyλ_iμ_j times whenF₁ andF₂ are superimposed.

• Hall triple systems (HTSs) areSteiner triple systems (STSs) (but the blocks are calledlines) with the property that the substructure generated by two intersecting lines is isomorphic to thefinite affine plane AG(2,3).

Any affine space AG(n,3) gives an example of an HTS. Such an HTS is anaffine HTS. Nonaffine HTSs also exist.

The number of points of an HTS is 3^m for some integerm ≥ 2. Nonaffine HTSs exist for anym ≥ 4 and do not exist form = 2 or 3.^[14]

Every Steiner triple system is equivalent to a Steinerquasigroup (idempotent,commutative and satisfying (xy)y = x for allx andy). A Hall triple system is equivalent to a Steiner quasigroup which isdistributive, that is, satisfiesa(xy) = (ax)(ay) for alla,x,y in the quasigroup.^[15]

• LetS be a set of 2n elements. AHowell design, H(s,2n) (on symbol setS) is ans ×s array such that:

1. Each cell of the array is either empty or contains an unordered pair fromS,
2. Each symbol occurs exactly once in each row and column of the array, and
3. Every unordered pair of symbols occurs in at most one cell of the array.

An example of anH(4,6) is

An H(2n − 1, 2n) is aRoom square of side 2n − 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 ans regular graph on 2n vertices, called theunderlying graph of the Howell design.

Cyclic Howell designs are used asHowell movements in duplicate bridge tournaments. The rows of the design represent the rounds, the columns represent the boards, and the diagonals represent the tables.^[16]

• Linear spaces
• An(n,k,p,t)-lotto design is ann-setV of elements together with a set β ofk-element subsets ofV (blocks), so that for anyp-subset P ofV, 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:^[17]

{1,2,3,4,7}       {1,2,5,6,7}       {3,4,5,6,7}.

Lotto designs model anylottery that is run in the following way: Individuals purchasetickets consisting ofk numbers chosen from a set ofn numbers. At a certain point the sale of tickets is stopped and a set ofp numbers is randomly selected from then numbers. These are thewinning numbers. If any sold ticket containst 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.^[18]

A geometric construction of one such design is given inTransylvanian lottery.

• Magic squares
• A(v,k,λ)-Mendelsohn design, or MD(v,k,λ), is av-setV and a collection β of orderedk-tuples of distinct elements ofV (calledblocks), such that each ordered pair (x,y) withx ≠y of elements ofV is cyclically adjacent inλ blocks. The ordered pair (x,y) of distinct elements iscyclically adjacent in a block if the elements appear in the block as (...,x,y,...) or (y,...,x). An MD(v,3,λ) is aMendelsohn triple system, MTS(v,λ). An example of an MTS(4,1) on V = {0,1,2,3} 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 {a,b,c} 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 semisymmetricquasigroup, that is,x ∗x =x (idempotent) andx ∗ (y ∗x) =y (semisymmetric) for allx,y inQ, let β = {(x,y,x ∗y):x,y inQ}. Then (Q, β) is a Mendelsohn triple system MTS(|Q|,1). This construction is reversible.^[19]

• Orthogonal arrays
• Aquasi-3 design is a symmetric design (SBIBD) in which each triple of blocks intersect in eitherx ory points, for fixedx andy called thetriple intersection numbers (x <y). Any symmetric design withλ ≤ 2 is a quasi-3 design withx = 0 andy = 1. The point-hyperplane design ofPG(n,q) is a quasi-3 design withx = (qⁿ⁻² − 1)/(q − 1) andy = λ = (qⁿ⁻¹ − 1)/(q − 1). Ify = λ for a quasi-3 design, the design is isomorphic toPG(n,q) or aprojective plane.^[20]
• At-(v,k,λ) designD isquasi-symmetric with intersection numbersx andy (x <y) if every two distinct blocks intersect in eitherx ory 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 withx = 0 andy = 1. A multiple (repeat all blocks a certain number of times) of a symmetric 2-(v,k,λ) design is quasisymmetric withx =λ andy =k. Hadamard 3-designs (extensions ofHadamard 2-designs) are quasisymmetric.^[21]

Every quasisymmetric block design gives rise to astrongly regular graph (as its block graph), but not all SRGs arise in this way.^[22]

Theincidence matrix of a quasisymmetric 2-(v,k,λ) design withk ≡x ≡y (mod 2) generates a binary self-orthogonalcode (when bordered ifk is odd).^[23]

• Room squares
• Aspherical design is a finite setX of points in a (d − 1)-dimensionalsphere such that, for some integert, the average value onX of every polynomial

${\displaystyle f(x_1,\dots ,x_d)}$

of total degree at mostt is equal to the average value off on the whole sphere, i.e., theintegral off divided by the area of the sphere.

• Turán systems
• Anr ×n tuscan-k rectangle onn symbols hasr rows andn columns such that:

1. each row is a permutation of then symbols and
2. for any two distinct symbolsa andb and for eachm from 1 tok, there is at most one row in whichb ism steps to the right ofa.

Ifr =n andk = 1 these are referred to asTuscan squares, while ifr =n andk =n - 1 they areFlorentine squares. ARoman square is a Tuscan square which is also alatin square (these are also known asrow complete Latin squares). AVatican 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:^[24]

A tuscan square onn symbols is equivalent to a decomposition of the complete graph withn vertices inton hamiltonian directed paths.^[25]

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 usingn sequences corresponding to the rows of ann ×n tuscan-1 square.^[26]

• At-wise balanced design (ort BD) of typet − (v,K,λ) is av-setX together with a family of subsets ofX (calledblocks) whose sizes are in the set K, such that everyt-subset of distinct elements ofX is contained in exactlyλ blocks. If K is a set of positive integers strictly betweent andv, then thet BD isproper. If all thek-subsets ofX for somek are blocks, thet BD is atrivial design.^[27]

Notice that in the following example of a 3-{12,{4,6},1) design based on the setX = {1,2,...,12}, some pairs appear four times (such as 1,2) while others appear five times (6,12 for instance).^[28]

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.^[29]
• AYouden square is ak ×vrectangular array (k <v) ofv 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.^[30] An example of a 4 × 7 Youden square is given by:

The seven blocks (columns) form the order 2biplane (a symmetric (7,4,2)-design).

• Algebraic statistics
• Hypergraph
• Williamson conjecture

• Combinatorial design
• Families of sets
• Design of experiments

• Articles with short description
• Short description matches Wikidata
• CS1 errors: ISBN date