276
Sets, Combinatorics, and Probability
Unlike earlier problems, the answer to Example 53 cannot easily be obtained
by applying the multiplication principle. Thus, C(n, r) gives us a way to solve new
problems.
example 54
Ten athletes compete in an Olympic event; 3 will be declared winners. How many
sets of winners are possible?
Here, as opposed to Example 49, there is no order to the 3 winners, so we
are simply choosing 3 objects out of 10. This is a combinations problem, not a
permutations problem. The result is C(10, 3) = 10!/(3!7!) = 120. Notice that
there are fewer ways to choose 3 winners (a combinations problem) than to
award gold, silver, and bronze medals to 3 winners (a permutations problem—
Example 49).
Remember that the distinction between permutations and combinations lies
in whether the objects are to be merely selected or both selected and ordered.
If ordering is important, the problem involves permutations; if ordering is not
important, the problem involves combinations. For example, Practice 30 is a permutations problem—2 people are to be selected and ordered, the first as president,
the second as vice-president—whereas Practice 32 is a combinations problem—
3 people are selected but not ordered.
In solving counting problems, C(n, r) can be used in conjunction with the
multiplication principle or the addition principle.
PraCtiCe 32 How many committees of 3 are possible from a group of 12 people?
■
ReminDeR
In a counting problem,
first ask yourself if order
matters. If it does, it’s a
permutations problem. If
not, it’s a combinations
problem.
example 55
A committee of 8 students is to be formed from a class consisting of 19 freshmen
and 34 sophomores.
a. How many committees of 3 freshmen and 5 sophomores are possible?
b. How many committees with exactly 1 freshman are possible?
c. How many committees with at most 1 freshman are possible?
d. How many committees with at least 1 freshman are possible?
Because the ordering of the individuals chosen is not important, these are combinations problems.
For part (a), we have a sequence of two subtasks, selecting freshmen and
selecting sophomores. The multiplication principle should be used. (Thinking of a
sequence of subtasks may seem to imply ordering, but it just sets up the levels of
the decision tree, the basis for the multiplication principle. There is no ordering of
the students.) Because there are C(19, 3) ways to choose the freshmen and C(34, 5)
ways to choose the sophomores, the answer is
C(19, 3) # C(34, 5) =
19!
3!16!
# 34!
5!29!
= (969)(278,256)
Sets, Combinatorics, and Probability
Unlike earlier problems, the answer to Example 53 cannot easily be obtained
by applying the multiplication principle. Thus, C(n, r) gives us a way to solve new
problems.
example 54
Ten athletes compete in an Olympic event; 3 will be declared winners. How many
sets of winners are possible?
Here, as opposed to Example 49, there is no order to the 3 winners, so we
are simply choosing 3 objects out of 10. This is a combinations problem, not a
permutations problem. The result is C(10, 3) = 10!/(3!7!) = 120. Notice that
there are fewer ways to choose 3 winners (a combinations problem) than to
award gold, silver, and bronze medals to 3 winners (a permutations problem—
Example 49).
Remember that the distinction between permutations and combinations lies
in whether the objects are to be merely selected or both selected and ordered.
If ordering is important, the problem involves permutations; if ordering is not
important, the problem involves combinations. For example, Practice 30 is a permutations problem—2 people are to be selected and ordered, the first as president,
the second as vice-president—whereas Practice 32 is a combinations problem—
3 people are selected but not ordered.
In solving counting problems, C(n, r) can be used in conjunction with the
multiplication principle or the addition principle.
PraCtiCe 32 How many committees of 3 are possible from a group of 12 people?
■
ReminDeR
In a counting problem,
first ask yourself if order
matters. If it does, it’s a
permutations problem. If
not, it’s a combinations
problem.
example 55
A committee of 8 students is to be formed from a class consisting of 19 freshmen
and 34 sophomores.
a. How many committees of 3 freshmen and 5 sophomores are possible?
b. How many committees with exactly 1 freshman are possible?
c. How many committees with at most 1 freshman are possible?
d. How many committees with at least 1 freshman are possible?
Because the ordering of the individuals chosen is not important, these are combinations problems.
For part (a), we have a sequence of two subtasks, selecting freshmen and
selecting sophomores. The multiplication principle should be used. (Thinking of a
sequence of subtasks may seem to imply ordering, but it just sets up the levels of
the decision tree, the basis for the multiplication principle. There is no ordering of
the students.) Because there are C(19, 3) ways to choose the freshmen and C(34, 5)
ways to choose the sophomores, the answer is
C(19, 3) # C(34, 5) =
19!
3!16!
# 34!
5!29!
= (969)(278,256)