combination 81





from the remaining n– 1 students. If John is not to be

on the committee, then one must select kstudents from

the pool of n– 1 students that excludes John.)

3.

(There are possible committees of

any size. But this number can also be computed by

deciding, student by student, whether or not to put that

student in the committee. As there are two possibilities

for each student, in or out, there are 2npossible com-

mittees. These counts must be the same.)

4.

(Suppose, in the committee, one student is to be

selected as chair. In a committee of size kthere are k

possible choices for chair. Thus counts the

total number of committees possible, of any size, with

one student selected as chair. But this quantity can also

be computed by selecting some student to be chair

first—there are nchoices for this—and then deciding,

student by student, among the remaining n– 1 students

whether that student should be on the committee. This

yields n2n–1 possibilities.)

Property 1 explains why Pascal’s triangle is sym-

metric. Property 2 shows that each entry in Pascal’s tri-

angle is the sum of the two entries above it, and

property 3 shows that the sum of all the entries in any

row of Pascal’s triangle is a power of two.

In 1778 L

EONHARD

E

ULER

used the notation

for the combinatorial coefficients, which, three years

later, he modified to . In the 19th century, mathe-

maticians started following Euler’s original notation,

dropping the

VINCULUM

for the purposes of easing

typesetting. Many textbooks today use the notation

nCk, or Cnk, or even C(n,k),for the combinatorial

coefficient .

Generalized Coefficients

The generalized combinatorial coefficient ,

where k1,k2,…,krare nonnegative integers summing to

n, is defined to be the number of ways one can select,

from nitems, k1objects to go into one container, k2

objects to go into a second container, and so forth, up

to krobjects to go into an rth container. (Notice that

is the ordinary combinatorial coefficient.)

Mimicking the argument presented above, note that

one can arrange nitems in a row by first selecting

which k1items are to go into the first part of the row

and ordering them, which k2items are to go in the

next portion of the row and ordering them, and so on.

This shows that , yielding

the formula:

Generalized combinatorial coefficients show, for

example, that there are

ways to rearrange the letters CHEESES: Of the seven

slots for letters, one must choose which slot is assigned

for the letter C, which one for the letter H, which three

for the letter E, and which two for letter S.

The generalized combinatorial coefficients also

appear in generalizations to the

BINOMIAL THEOREM

.

For example, we have the trinomial theorem:

where the sum is taken over all triples k1,k2,k3that

sum to n. The proof is analogous to that of the ordi-

nary binomial theorem.

Multi-Choosing

The quantity , read as “nmulti-choose k,” counts

the number of ways to select kobjects from a collection