80 combination

Three points A, B, and Cin three-dimensional

space are collinear if the triangle they form has zero

area. Equivalently, the three points are collinear if the

angle between the

VECTORS

→

AB and →

AC is zero, and

consequently the

CROSS PRODUCT

→

AB ×→

AC equals

the zero vector.

The collinearity of points in a plane is a topic of

interest to geometers. In the mid-1700s, L

EONHARD

E

ULER

discovered that several interesting points con-

structed from triangles are collinear, yielding his

famous E

ULER LINE

. In 1893 British mathematician

James Sylvester (1814–97) posed the question of

whether it is possible to arrange three or more points in

a plane, not all on a line, so that any line connecting

two of the points from the collection passes through a

third point as well. Forty years later Tibor Gallai

(1912–92) proved that there is no such arrangement.

Two or more distinct

PLANE

s are said to be

collinear if they intersect in a common straight line. In

this case, the vectors normal to each plane all lie in a

plane perpendicular to the common line. Thus one can

determine whether or not a collection of planes is

collinear by noting whether or not the cross products

of pairs of normal vectors are all parallel.

See also

GRADIENT

;

NORMAL TO A PLANE

.

combination (selection, unordered arrangement) Any

set of items selected from a given set of items without

regard to their order is called a combination. Repetition

of choices is not permitted. For example, there are six

distinct combinations of two letters selected from the

sequence A,B,C,D, namely: AB, AC, AD, BC, BD, and

CD. (The selection BA, for example, is deemed the

same as AB, and the choice AA is not permitted.)

The number of combinations of kitems selected

from a set of ndistinct objects is denoted . The

number , for instance, equals six. The quantity

is called a combinatorial coefficient and is read as

“nchoose k.” Given their appearance in the

BINOMIAL

THEOREM

, these numbers are also called binomial

coefficients.

One develops a formula for by counting the

number of ways to arrange ndistinct objects in a

row. There are, of course, n! different ways to do

this. (See

FACTORIAL

.) Alternatively, we can imagine

selecting which kobjects are to be arranged in the

first kpositions along the row (there are ways

to do this), ordering those kitems (there are k! differ-

ent ways to do this), and then arranging the remain-

ing n– kobjects for the latter part of the row (there

are (n– k)! different ways to accomplish this). This

yields different ways to arrange nobjects

in a row. Since this quantity must equal n!, we have

the formula for the combinatorial

coefficient.

It is appropriate to define 0! as equal to one. In

this way, the formula just established holds even for

k= n. (There is just one way to select nobjects from

a collection of nitems, and so should equal

one.) It then follows that . (There is just

one way to select no objects.) Mathematicians set

to be zero if kis negative or greater than n.

The combinatorial coefficients appear as the entries

of P

ASCAL

’

S TRIANGLE

. They also satisfy a number of

identities. We list just four, which we shall phrase in

terms of the process of selecting kstudents to be in a

committee from a class of nstudents.

1.

(Selecting kstudents to be in a committee is the same as

selecting n– kstudents not to be in the committee.)

2.

(Any committee formed either includes, or excludes, a

particular student John, say. If John is to be on the

committee, then one must select k– 1 more students