82 combinatorial coefficient

of nitems, where order is not important, but repetition

is allowed. For example, there are 10 ways to multi-

choose two objects from the set A, B, C, and D,

namely: AB, AC, AD, BC, BD, CD, and AA, BB, CC,

and DD. Thus . One can show that a multi-

choose coefficient equals an ordinary combinatorial co-

efficient:

combinatorial coefficient See

COMBINATION

.

combinatorics (combinatorial analysis) The branch

of mathematics concerned with the theory and prac-

tices of counting elements of sets and the construction

of specified arrangements of objects, along with the

study of

COMBINATION

s and

PERMUTATION

s, is called

combinatorics.

GRAPH THEORY

is also regarded as an

aspect of combinatorics.

The technique of “double counting,” that is, count-

ing the same set of objects in two different ways, is a

common practice in combinatorics used to yield inter-

esting results. For example, counting the dots in an n×n

square array along diagonals as opposed to across the

rows gives the surprising formula:

1 + 2 + 3 + … + (n– 1) + n+ (n– 1) + … + 3 + 2 + 1 = n2

Counting the number of subsets of a set of nele-

ments, either by summing the number of subsets con-

taining, in turn, 0, 1, 2, up to nelements, or by noting

that each subset is decided by making nchoices

between two options—whether or not each element in

turn is to be in the subset—yields the formula:

E

ULER

’

S THEOREM

can be considered a result in combi-

natorial geometry.

See also

DISCRETE

;

FIGURATE NUMBERS

.

commensurable Two quantities having a common

measure, meaning that they can be measured in terms of

whole numbers of a common unit, are said to be com-

mensurable. For example, the quantities one month and

one week are commensurable because they can both be

measured in terms of a whole number of days. In

GEOM

-

ETRY

, two line segments are said to be commensurable if

there is another segment whose measure goes evenly,

without remainder, into the measures of each segment.

For instance, segments of lengths 20 and 12 in. are com-

mensurable for they can each be evenly divided into

lengths of 1 (or 2 or 4) in. In general, two segments of

lengths a and b units are commensurable if the ratio a/b

is a

RATIONAL NUMBER

. As √

–

2 is irrational, segments of

length 1 and √

–

2 (respectively, the side-length and the

diagonal of a unit square) are incommensurable.

A study of the E

UCLIDEAN ALGORITHM

shows that

if given two commensurable line segments of lengths a

and b, say, then repeatedly subtracting the shorter

length from the longer to produce a new pair of lengths

eventually produces two line segments equal in length.

This final shared measure is the largest length that

divides evenly into the two original segments. (If aand

bare whole-number measurements, then the length of

the final measure is the

GREATEST COMMON DIVISOR

of

aand b.) If, on the other hand, one can demonstrate

that the process of repeatedly erasing the shorter line

segment from the longer will continue indefinitely

without ever producing two line segments equal in

length, then the original two segments cannot be com-

mensurable. Around 425

B

.

C

.

E

. Greek mathematician

T

HEODORUS OF

C

YRENE

used precisely this observa-

tion to prove the irrationality of √

–

2.

In

NUMBER THEORY

, two real numbers aand bare

said to be commensurable if their ratio is rational. For

instance, the numbers √

–

48 and √

–

3/2 are commensu-

rable. No one to this day knows whether or not πand

eare commensurable. The numbers log5(3) and log5(7)

are incommensurable. (If for some whole

numbers pand q, then 7q= 3p, which is absurd since

every power of 7 is 1 more than a multiple of 3.)

common denominator Two or more fractions are

said to have a common denominator if the denomi-

nator of each fraction is the same. For example, the

fractions and have a common denominator of

12. It is a straightforward matter to add and subtract

3

12

5

12