Section 4.4 Permutations and Combinations
277
For part (b), we again have a sequence of subtasks: selecting the single freshman and then selecting the rest of the committee from among the sophomores.
There are C(19, 1) ways to select the single freshman and C(34, 7) ways to select
the remaining 7 members from the sophomores. By the multiplication principle,
the answer is
C(19, 1) # C(34, 7) =
19!
1!(19 − 1)!
#
34!
7!(34 − 7)!
= 19(5,379,616)
For part (c), we get at most 1 freshman by having exactly 1 freshman or by
having 0 freshmen. Because these are disjoint events, we use the addition principle. The number of ways to select exactly 1 freshman is the answer to part (b).
The number of ways to select 0 freshmen is the same as the number of ways to
select the entire 8-member committee from among the 34 sophomores, C(34, 8).
Thus the answer is
C(19, 1) # C(34, 7) + C(34, 8) = some big number
We can attack part (d) in several ways. One way is to use the addition principle, thinking of the disjoint possibilities as exactly 1 freshman, exactly 2 freshmen,
and so on, up to exactly 8 freshmen. We could compute each of these numbers and
then add them. However, it is easier to do the problem by counting all the ways the
committee of 8 can be selected from the total pool of 53 people and then eliminating (subtracting) the number of committees with 0 freshmen (all sophomores).
Thus the answer is
C(53, 8) − C(34, 8)
ReminDeR
“At least” counting problems are often best solved
by subtraction.
The factorial function grows large quickly. A number like 100! cannot be
computed on most calculators (or on most computers unless double−precision
arithmetic is used), but expressions like
100!
25!75!
can nevertheless be computed by first canceling common factors.
eliminating duplicates
We mentioned earlier that counting problems can often be solved in different ways.
Unfortunately, it is also easy to find so-called solutions that sound eminently reasonable but are incorrect. Usually they are wrong because they count something
more than once (or sometimes they overlook counting something entirely).
example 56
Consider again part (d) of Example 55, the number of committees with at least 1
freshman. A bogus solution to this problem goes as follows: Think of a sequence
of two subtasks, choosing a freshman and then choosing the rest of the committee.
277
For part (b), we again have a sequence of subtasks: selecting the single freshman and then selecting the rest of the committee from among the sophomores.
There are C(19, 1) ways to select the single freshman and C(34, 7) ways to select
the remaining 7 members from the sophomores. By the multiplication principle,
the answer is
C(19, 1) # C(34, 7) =
19!
1!(19 − 1)!
#
34!
7!(34 − 7)!
= 19(5,379,616)
For part (c), we get at most 1 freshman by having exactly 1 freshman or by
having 0 freshmen. Because these are disjoint events, we use the addition principle. The number of ways to select exactly 1 freshman is the answer to part (b).
The number of ways to select 0 freshmen is the same as the number of ways to
select the entire 8-member committee from among the 34 sophomores, C(34, 8).
Thus the answer is
C(19, 1) # C(34, 7) + C(34, 8) = some big number
We can attack part (d) in several ways. One way is to use the addition principle, thinking of the disjoint possibilities as exactly 1 freshman, exactly 2 freshmen,
and so on, up to exactly 8 freshmen. We could compute each of these numbers and
then add them. However, it is easier to do the problem by counting all the ways the
committee of 8 can be selected from the total pool of 53 people and then eliminating (subtracting) the number of committees with 0 freshmen (all sophomores).
Thus the answer is
C(53, 8) − C(34, 8)
ReminDeR
“At least” counting problems are often best solved
by subtraction.
The factorial function grows large quickly. A number like 100! cannot be
computed on most calculators (or on most computers unless double−precision
arithmetic is used), but expressions like
100!
25!75!
can nevertheless be computed by first canceling common factors.
eliminating duplicates
We mentioned earlier that counting problems can often be solved in different ways.
Unfortunately, it is also easy to find so-called solutions that sound eminently reasonable but are incorrect. Usually they are wrong because they count something
more than once (or sometimes they overlook counting something entirely).
example 56
Consider again part (d) of Example 55, the number of committees with at least 1
freshman. A bogus solution to this problem goes as follows: Think of a sequence
of two subtasks, choosing a freshman and then choosing the rest of the committee.