The Art and Craft of Problem Solving

6.1 INTRODUCTION TO COUNTING 191

In general, the number of ways you can select a subset of r distinct elements from

a set of n distinct elements, where the order of selection doesn' t matter, is

(n) P(n, r) n!

r

= -

r

-

!

- =

(n - r)!r!·

(1)

This is called a combination. If the order does matter, then the number of ways is

P(n,r) and it is called a permutation.

For example, the number of different ways to pick a three-person committee out of
a 30 -person class is e3^0 ). However, if the committee members have specific roles, such
as president, vice-president, and secretary, then there are P(30, 3) different committees
(since the committee where Joe is president, Karen is VP, Tina is secretary is not the
same as the committee where Joe is secretary, Tina is VP, Karen is president).
Incidentally, it makes sense to define binomial coefficients involving the number
zero. For example, (^10 °) = 1, because there is only one way to choose a committee with

no people. This interpretation will be consistent with the formula in (1) if we define O!

to equal 1.

The interpretation of the binomial coefficient as a permutation divided by a fac­

torialleads to a nice computational shortcut. Notice that it is much easier to compute

(V) as

11. 10 ·9· 8

= 11. 5. 3. 2 = 330

1·2·3· 4

than it would be to compute 11 !/( 4! 7 !).

Combinatorial Arguments

Keeping a flexible point of view is a powerful strategy. This is especially true with
counting problems where often the crux move is to count the same thing in two differ­
ent ways. To help develop this flexibility, you should practice creating "combinatorial

arguments." This is just fancy language for a story that rigorously describes in English

how you count something. Here are a few examples that illustrate the method. First we
state something algebraically, then the combinatorial story that corresponds to it. Pay
attention to the building blocks of "algebra to English" translation, and in particular,
make sure you understand when and why multiplication rather than addition happens,
and vice versa.

7x6

12 + 6 + 5

If there are seven choices of pasta and six choices

of sauces, there are 7 x 6 ways of choosing a pasta

dinner with a sauce.

If the things you are counting fall into three mutu­

ally exclusive classes, with 12 in the first, six in the

second, five in the third class, then the total number

of things you are counting is 12 + 6 + 5.

If you are eating a five-course dinner, with seven

choices per course, you can order 75 different din­

ners.