Page 447 - Discrete Mathematics and Its Applications

426 6 / Counting

EXAMPLE 4 Suppose that a cookie shop has four different kinds of cookies. How many different ways can
six cookies be chosen? Assume that only the type of cookie, and not the individual cookies or
the order in which they are chosen, matters.

Solution: The number of ways to choose six cookies is the number of 6-combinations of a set
with four elements. From Theorem 2 this equals C(4 + 6 − 1, 6) = C(9, 6). Because

9 · 8 · 7
C(9, 6) = C(9, 3) = = 84,
1 · 2 · 3

there are 84 different ways to choose the six cookies. ▲

Theorem 2 can also be used to find the number of solutions of certain linear equations where
the variables are integers subject to constraints. This is illustrated by Example 5.

EXAMPLE 5 How many solutions does the equation

x 1 + x 2 + x 3 = 11

have, where x 1 , x 2 , and x 3 are nonnegative integers?

Solution: To count the number of solutions, we note that a solution corresponds to a way of
selecting 11 items from a set with three elements so that x 1 items of type one, x 2 items of type
two, and x 3 items of type three are chosen. Hence, the number of solutions is equal to the number
of 11-combinations with repetition allowed from a set with three elements. From Theorem 2 it
follows that there are

13 · 12
C(3 + 11 − 1, 11) = C(13, 11) = C(13, 2) = = 78
1 · 2

solutions.
The number of solutions of this equation can also be found when the variables are subject
to constraints. For instance, we can find the number of solutions where the variables are inte-
gers with x 1 ≥ 1, x 2 ≥ 2, and x 3 ≥ 3. A solution to the equation subject to these constraints
corresponds to a selection of 11 items with x 1 items of type one, x 2 items of type two, and x 3
items of type three, where, in addition, there is at least one item of type one, two items of type
two, and three items of type three. So, a solution corresponds to a choice of one item of type
one, two of type two, and three of type three, together with a choice of five additional items of
any type. By Theorem 2 this can be done in

7 · 6
C(3 + 5 − 1, 5) = C(7, 5) = C(7, 2) = = 21
1 · 2

ways. Thus, there are 21 solutions of the equation subject to the given constraints. ▲

Example 6 shows how counting the number of combinations with repetition allowed arises
in determining the value of a variable that is incremented each time a certain type of nested loop
is traversed.