Block design

Block design

In combinatorial mathematics, a block design (more fully, a balanced incomplete block design) is a particular kind of set system, which has long-standing applications to experimental design (an area of statistics) as well as purely combinatorial aspects.

Given a finite set "X" (of elements called points) and integers "k", "r", λ ≥ 1, we define a 2-design "B" to be a set of "k"-element subsets of "X", called blocks, such that the number "r" of blocks containing "x" in "X" is independent of "x", and the number λ of blocks containing given distinct points "x" and "y" in "X" is also independent of the choices.

Here "v" (the number of elements of "X", called points), "b" (the number of blocks), "k", "r", and λ are the parameters of the design. (Also, "B" may not consist of all "k"-element subsets of "X"; that is the meaning of "incomplete".) The design is called a ("v", "k", λ)-design or a ("v", "b", "r", "k", λ)-design. The parameters are not all independent; "v", "k", and λ determine "b" and "r", and not all combinations of "v", "k", and λ are possible. The two basic equations connecting these parameters are

: bk = vr, ,

: lambda(v-1) = r(k-1). ,

A fundamental theorem, Fisher's inequality, named after Ronald Fisher, is that "b" ≥ "v" in any block design. The case of equality is called a symmetric design; it has many special features.

Examples of block designs include the lines in finite projective planes (where "X" is the set of points of the plane and λ = 1), and Steiner triple systems ("k" = 3). The former is a relatively simple example of a symmetric design.

Projective planes

Projective planes are a special case of block designs, where we have scriptstyle v ,>, 0 points and, as they are symmetric designs, scriptstyle b ,=, v (which is the limit case of Fisher's inequality), from the first basic equation we get

:k = r, ,

and since scriptstyle lambda ,=, 1 by definition, the second equation gives us

:v-1 = k(k-1).,

Now, given an integer scriptstyle n ,geq, 1, called the "order of the projective plane", we can put "k" = "n" + 1 and, from the displayed equation above, we have scriptstyle v ,=, (n+1)n ,+, 1 ,=, n^2 ,+, n ,+, 1 points in a projective plane of order "n".

Since a projective plane is symmetric, we have that scriptstyle b ,=, v, which means that scriptstyle b ,=, n^2 ,+, n ,+, 1 also. The number "b" is usually called the number of "lines" of the projective plane.

This means, as a corollary, that in a projective plane, the number of lines and the number of points are always the same. For a projective plane, "k" is the number of lines and it is equal to "n" + 1, where "n" is the order of the plane. Similarly, "r" = "n" + 1 is the number of lines to which the a given point is incident.

For "n" = 2 we get a projective plane of order 2, also called the Fano plane, with "v" = 4 + 2 + 1 = 7 points and 7 lines. In the Fano plane, each line has "n" + 1 = 3 points and each point belongs to "n" + 1 = 3 lines.

Generalization: "t"-designs

Given any integer "t" ≥ 2, a "t"-design "B" is a class of "k"-element subsets of "X" (the set of points), called blocks, such that the number "r" of blocks that contain any point "x" in "X" is independent of "x", and the number λ of blocks that contain any given "t"-element subset "T" is independent of the choice of "T". The numbers "v" (the number of elements of "X"), "b" (the number of blocks), "k", "r", λ, and "t" are the parameters of the design. The design may be called a "t"-("v","k",λ)-design. Again, these four numbers determine "b" and "r" and the four numbers themselves cannot be chosen arbitrarily. The equations are

: b_i = lambda left.inom{v-i}{t-i} ight/ inom{k-i}{t-i} ext{ for } i = 0,1,ldots,t,

where "bi" is the number of blocks that contain any "i"-element set of points.

There are no known examples of non-trivial "t"-("v","k",1)-designs with scriptstyle t >, 5.

The term "block design" by itself usually means a 2-design.

ee also

* Randomized block design

References

* van Lint, J.H., and R.M. Wilson (1992), "A Course in Combinatorics". Cambridge, Eng.: Cambridge University Press.
*


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Block design test — Block design is a subtest on many intelligence tests that tests visuospatial and motor skills. The testee is required to take blocks that have all white sides, all red sides, and red and white sides and arrange them according to a pattern. They… …   Wikipedia

  • Randomized block design — In the statistical theory of the design of experiments, blocking is the arranging of experimental units in groups (blocks) that are similar to one another. Typically, a blocking factor is a source of variability that is not of primary interest to …   Wikipedia

  • Block — may refer to: * A way of controlling train movement in railway signalling * Postage stamp block, an attached group of postage stampsObjects* A large concrete or stone brick * Block (sailing), a single or multiple pulley used on sailboats *… …   Wikipedia

  • Design theory — can refer to any theory relating to design in general. Design theory may also refer to: Engineering and industrial design C K theory Design science C K theory Mathematics Combinatorial design Block design Symmetric design Design of experiments… …   Wikipedia

  • randomized block design — noun see randomized block …   New Collegiate Dictionary

  • Design of experiments — In general usage, design of experiments (DOE) or experimental design is the design of any information gathering exercises where variation is present, whether under the full control of the experimenter or not. However, in statistics, these terms… …   Wikipedia

  • Block diagram — is a diagram of a system, in which the principal parts or functions are represented by blocks connected by lines, that show the relationships of the blocks. [http://pascal.computer.org/sev display/index.action SEVOCAB: Software and Systems… …   Wikipedia

  • Block suballocation — is a feature of some computer file systems which allows large blocks or allocation units to be used while making efficient use of slack space at the end of large files, space which would otherwise be lost for other use to internal fragmentation.… …   Wikipedia

  • Design House Stockholm — Type Privately held Industry Design, retail Founded January 29, 1992[1] …   Wikipedia

  • Block booking — is a system of selling multiple films to a theater as a unit. Block booking was the prevailing practice among Hollywood s major studios from the turn of the 1930s through the late 1940s, when it was outlawed by a Supreme Court decision. Under… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”