Gregersen E. (editor) The Britannica Guide to Statistics and Probability

Подождите немного. Документ загружается.

7 The Britannica Guide to Statistics and Probability 7

210

example. Hence the number D

of derangements can be

shown to be approximated by n !/ e

This number was ﬁ rst obtained by Euler. If n persons

check their hats in a restaurant, and the waiter loses the

checks and returns the hats at random, then the chance

that no one receives his own hat is D

/ n ! = e

-1

approximately.

It is surprising that the approximate answer is indepen-

dent of n . To six places of decimals e

-1

= 0.367879. When n =

6 the error of approximation is less than 0.0002.

If n is expressed as the product of powers of its prime

factors p

, p

, · · · p

, if the objects are the integers less than

or equal to n , and if A

is the property of being divisible

by p

, then Sylvester’s formula gives, as the number of

integers less than n and prime to it, a function of n , writ-

ten ϕ( n ), composed of a product of n and k factors of the

type (1 - 1/ p

)

211

Combinatorics 7

The function ϕ( n ) is the Euler function.

Polya’s Theorem

It is required to make a necklace of n beads out of an inﬁ -

nite supply of beads of k different colours. The number of

different necklaces, c ( n , k ), that can be made is given by

the reciprocal of n times a sum of terms of the type ϕ( n )

n / d

, in which the summation is over all divisors d of n and ϕ

is the Euler function

Though the problem of the necklaces appears to be

frivolous, the formula given above can be used to solve a

difﬁ cult problem in the theory of Lie algebras, of some

importance in modern physics.

The general problem of which the necklace problem is

a special case was solved by the Hungarian-born American

mathematician George Polya in a famous 1937 memoir in

which he established connections between groups, graphs,

and chemical bonds. It has been applied to enumeration

problems in physics, chemistry, and mathematics.

The Möbius Inversion Theorem

In 1832 the German astronomer and mathematician

August Ferdinand Möbius proved that if f and g are func-

tions deﬁ ned on the set of positive integers, such that f

evaluated at x is a sum of values of g evaluated at divisors of

x , then inversely g at x can be evaluated as a sum involving

f evaluated at divisors of x

7 The Britannica Guide to Statistics and Probability 7

212

In 1964 the American mathematician Gian-Carlo

Rota obtained a powerful generalization of this theorem,

providing a fundamental unifying principle of enumera-

tion. One consequence of Rota’s theorem is the following:

If f and g are functions deﬁ ned on subsets of a ﬁ nite set A ,

such that f ( A ) is a sum of terms g ( S ), in which S is a subset

of A , then g ( A ) can be expressed in terms of f

Special Problems

Despite the general methods of enumeration already

described, there are many problems in which they do not

apply and therefore require special treatment. Two such

problems include the Ising problem and the self-avoiding

random walk.

213

Combinatorics 7

The Ising Problem

A rectangular m × n grid is made up of unit squares, each

coloured either red or green. How many different colour

patterns are there if the number of boundary edges

between red squares and green squares is prescribed?

This problem, although easy to state, proved difﬁ-

cult to solve. A complete and rigorous solution was not

achieved until the early 1960s. The importance of the

problem lies in the fact that it is the simplest model that

exhibits the macroscopic behaviour expected from cer-

tain natural assumptions made at the microscopic level.

Historically, the problem arose from an early attempt,

made in 1925, to formulate the statistical mechanics of

ferromagnetism. The three-dimensional analogue of the

Ising problem remains unsolved in spite of persistent

attacks.

Self-Avoiding Random Walk

A random walk consists of a sequence of n steps of unit

length on a ﬂat rectangular grid, taken at random either in

the x- or the y-direction, with equal probability in each of

the four directions. What is the number R

of random

walks that do not touch the same vertex twice? This prob-

lem has deﬁed solution, except for small values of n,

though a large amount of numerical data has been amassed.

pRobleMs of choice

Systems of Distinct Representatives

Subsets S

, S

, · · · , Sn of a ﬁnite set S are said to possess a set

of distinct representatives if x

, x

, · · · , x

can be found, such

that x

∊ S

, i = 1, 2, · · · , n, x

≠ x

for i ≠ j. It is possible that S

and S

, i ≠ j, may have exactly the same elements and are

7 The Britannica Guide to Statistics and Probability 7

214

distinguished only by the indices i, j. In 1935 American

mathematician, M. Hall, Jr., proved that a necessary and

sufﬁcient condition for S

, S

, · · · , S

to possess a system of

distinct representatives is that, for every kn, any k of the n

subsets contain between them at least k distinct elements.

For example, the sets S

= (1, 2, 2), S

= (1, 2, 4), S

= (1, 2,

5), S

= (3, 4, 5, 6), S

= (3, 4, 5, 6) satisfy the conditions of the

theorem, and a set of distinct representatives is x

= 1, x

2, x

= 5, x

= 3, x

= 4. Conversely, the sets T

= (1, 2), T

= (1,

3), T

= (1, 4), T

= (2, 3), T

= (2, 4), T

= (1, 2, 5) do not possess

a system of distinct representatives because T

, T

possess between them only four elements.

The following theorem resulting from König is closely

related to Hall’s theorem and can be easily deduced from

it. Conversely, Hall’s theorem can be deduced from

König’s: If the elements of rectangular matrix are 0s and

1s, then the minimum number of lines that contain all of

the 1s is equal to the maximum number of 1s that can be

chosen with no two on a line.

Ramsey’s Numbers

If X = {1, 2, . . . , n}, and if T, the family of all subsets of

X containing exactly r distinct elements, is divided into

two mutually exclusive families α and β, the following

conclusion that was originally obtained by the British

mathematician Frank Plumpton Ramsey follows. He

proved that for r ≥ 1, p ≤ r, q ≤ r there exists a number N

(p,

q) depending solely on p, q, r such that if n > N

(p, q), there

is either a subset A of p elements all of the r subsets of

which are in the family α or there is a subset B of q ele-

ments all of the r subsets of which are in the family β.

The set X can be a set of n persons. For r = 2, T is the

family of all pairs. If two persons have met each other,

then the pair can belong to the family α. If two persons

215

Combinatorics 7

have not met, then the pair can belong to the family β. If

these things are assumed, then, by Ramsey’s theorem, for

any given p ≥ 2, q ≥ 2 there exists a number N

(p, q) such

that if n > N

(p, q), then among n persons invited to a party

there will be either a set of p persons all of whom have met

each other or a set of q persons no two of whom have met.

Although the existence of N

(p, q) is known, actual val-

ues are known only for a few cases. Because N

(p, q) = N

(q,

p), it is possible to take p ≤ q. It is known that N

(3, 3) = 6,

(3, 4) = 9, N

(3, 5) = 14, N

(3, 6) = 18, N

(4, 4) = 18. Some

bounds are also known; for example, 35 ≤ N

(4, 6) ≤ 41.

A consequence of Ramsey’s theorem is the following

result obtained in 1935 by the Hungarian mathematicians

Paul Erdös and George Szekeres. For a given integer n

there exists an integer N = N(n), such that a set of any N

points on a plane, no three on a line, contains n points

forming a convex n-gon.

design TheoRy

BIB (Balanced Incomplete Block) Designs

A design is a set of T = {1, 2, . . . , υ} objects called treatments

and a family of subsets B

, B

, . . . , B

of T, called blocks,

such that the block B

contains exactly k

treatments, all

distinct. The number k

is called the size of the block B

and the ith treatment is said to be replicated r

times if it

occurs in exactly r

blocks. Speciﬁc designs are subject to

further constraints. The name design comes from statisti-

cal theory in which designs are used to estimate effects of

treatments applied to experimental units.

A BIB design is a design with υ treatments and b blocks

in which each block is of size k, each treatment is repli-

cated r times, and every pair of distinct treatments occurs

together in λ blocks. The design is said to have the

7 The Britannica Guide to Statistics and Probability 7

216

parameters (υ, b , r , k , λ). Some basic relations are easy to

establish

These conditions are necessary but not sufﬁ cient for

the existence of the design. The design is said to be proper if

k < υ—that is, the blocks are incomplete. For a proper BIB

design Fisher’s inequality b ≥ υ, or equivalently r ≥ k , holds.

A BIB design is said to be symmetric if υ = b , and con-

sequently r = k . Such a design is called a symmetric (υ, k , λ)

design, and λ(υ − 1) = k ( k − 1). A necessary condition for the

existence of a symmetric (υ, k , λ) design is given by the

following:

A. If υ is even, k − λ is a perfect square.

B. If υ is odd, a certain Diophantine equation

has a solution in integers not all zero.

For example, the designs (υ, k , λ) = (22, 7, 2) and (46, 10,

2) are ruled out by (A) and the design (29, 8, 2) by (B).

Because necessary and sufﬁ cient conditions for the exis-

tence of a BIB design with given parameters are unknown,

it is often a difﬁ cult problem to decide whether a design

with given parameters (satisfying the known necessary

conditions) really exists.

Methods of constructing BIB designs depend on the

use of ﬁ nite ﬁ elds, ﬁ nite geometries, and number theory.

Some general methods were given in 1939 by the Indian

mathematician Raj Chandra Bose, who has since emi-

grated to the United States.

217

Combinatorics 7

A ﬁ nite ﬁ eld is a ﬁ nite set of marks with two opera-

tions, addition and multiplication, subject to the usual

nine laws of addition and multiplication obeyed by ratio-

nal numbers. In particular the marks may be taken to be

the set X of non-negative integers less than a prime p . If

this is so, then addition and multiplication are deﬁ ned by

modiﬁ ed addition and multiplication laws

in which a , b , r , and p belong to X . For example, if p = 7,

then 5 + 4 = 2, 5 · 4 = 6. There exist more general ﬁ nite ﬁ elds

in which the number of elements is p

, p a prime. There is

essentially one ﬁ eld with p

elements, with given p and n .

It is denoted by G F ( p

Finite geometries can be obtained from ﬁ nite ﬁ elds in

which the coordinates of points are now elements of a

ﬁ nite ﬁ eld. A set of k + 1 non-negative integers d

, d

, · · · , d

is said to form a perfect difference set mod υ, if among the

k ( k − 1) differences d

− d

, i ≠ j , i , j = 0, 1, · · · , k , reduced mod

υ, each nonzero positive integer less than υ occurs exactly

the same number of times λ. For example, 1, 4, 5, 9, 3 is a

difference set mod 11, with λ = 2. From a perfect difference

set can be obtained the symmetric (υ, k , λ) design using the

integers 0, 1, 2, · · · , υ − 1. The j th block contains the treat-

ments obtained by reducing mod υ the numbers d

+ j , j

j , · · · , d

+ j , j = 0, 1, · · · , υ − 1.

It can be shown that any two blocks of a symmetric (υ, k ,

λ) design intersect in exactly k treatments. By deleting one

block and all the treatments contained in it, it is possible to

obtain from the symmetric design its residual, which is a

BIB design (unsymmetric) with parameters υ* = υ − k , b * = υ

− 1, r * = k , k * = k − λ, λ* = λ. One may ask whether it is true that

a BIB design with the parameters of a residual can be

7 The Britannica Guide to Statistics and Probability 7

218

embedded in a symmetric BIB design. The truth of this is

rather easy to demonstrate when λ = 1. Hall and W.S. Connor

in 1953 showed that it is also true for λ = 2. The Indian math-

ematician K.N. Bhattacharya in 1944, however, gave a

counterexample for λ = 3 by exhibiting a BIB design with

parameters υ = 16, b = 24, r = 9, k = 6, λ = 3 for which two par-

ticular blocks intersect in four treatments and which for

that reason cannot be embedded in a symmetric BIB design.

A BIB design is said to be resolvable if the set of blocks

can be partitioned into subsets, such that the blocks in

any subset contain every treatment exactly once. For the

case k = 3, this problem was ﬁrst posed during the 19th

century by the British mathematician T.P. Kirkman as a

recreational problem. There are υ girls in a class. Their

teacher wants to take the class out for a walk for a number

of days, the girls marching abreast in triplets. It is required

to arrange the walk so that any two girls march abreast in

the same triplet exactly once. It is easily shown that this is

equivalent to the construction of a resolvable BIB design

with υ = 6t + 3, b = (2t + 1)(3t + 1), r = 3t + 1, k = 3, λ = 1. Solutions

were known for only a large number of special values of t

until a completely general solution was ﬁnally given by the

Indian and American mathematicians Dwijendra K. Ray-

Chaudhuri and R.M. Wilson in 1970.

Pbib (Partially Balanced Incomplete

Block) Designs

Given υ objects 1, 2, · · · , υ, a relation satisfying the follow-

ing conditions is said to be an m-class partially balanced

association scheme:

A. Any two objects are either 1st, or 2nd, · · · , or

mth associates, the relation of association being

symmetrical.

219

Combinatorics 7

B. Each object α has n

i th associates, the number

being independent of α.

C. If any two objects α and β are i th associates, then

the number of objects that are j th associates of

α and k th associates of β is p

and is indepen-

dent of the pair of i th associates α and β.

The constants υ, n

, p

j k

are the parameters of the asso-

ciation scheme. A number of identities connecting these

parameters were given by the Indian mathematicians Bose

and K.R. Nair in 1939, but Bose and the American math-

ematician D.M. Mesner in 1959 discovered new identities

when m > 2.

A PBIB design is obtained by identifying the υ treat-

ments with the υ objects of an association scheme and

arranging them into b blocks satisfying the following

conditions:

A. Each contains k treatments.

B. Each treatment occurs in r blocks.

C. If two treatments are i th associates, they occur

together in λ

blocks.

Two-class association schemes and the corresponding

designs are especially important both from the mathe-

matical point of view and because of statistical applications.

For a two-class association scheme the constancy of υ, n

, and p

ensures the constancy of the other parameters.

Seven relations hold :