274
Sets, Combinatorics, and Probability
PraCtiCe 30 In how many ways can a president and vice-president be selected from a group of
20 people?
■
PraCtiCe 31 In how many ways can 6 people be seated in a row of 6 chairs?
■
Counting problems can have other counting problems as subtasks.
Combinations
Sometimes we want to select r objects from a set of n objects, but we don’t care
how they are arranged. Then we are counting the number of combinations of r
distinct objects chosen from n distinct objects, denoted by C(n, r). For each such
combination, there are r! ways to permute the r chosen objects. By the multiplication principle, the number of permutations of r distinct objects chosen from
n objects is the product of the number of ways to choose the objects, C(n, r),
multiplied by the number of ways to arrange the objects chosen, r! Thus,
C(n, r) # r! = P(n, r)
or
C(n, r) =
P(n, r)
r!
=
n!
r!(n − r)!
for 0 ≤ r ≤ n
Other notations for C(n, r) are
n C r ,     C
n
r ,     a
n
r
b
example 50
A library has 4 books on operating systems, 7 on programming, and 3 on data
structures. Let’s see how many ways these books can be arranged on a shelf, given
that all books on the same subject must be together.
We can think of this problem as a sequence of subtasks. First we consider
the subtask of arranging the 3 subjects. There are 3! outcomes to this subtask,
that is, 3! different orderings of subject matter. The next subtasks are arranging
the books on operating systems (4! outcomes), then arranging the books on
programming (7! outcomes), and finally arranging the books on data structures
(3! outcomes). Thus, by the multiplication principle, the final number of arrangements of all the books is (3!)(4!)(7!)(3!) = 4,354,560.
example 51
The value of C(7, 3) is
7!
3!(7 − 3)!
=
7!
3!4!
=
7 # 6 # 5 # 4 # 3 # 2 # 1
3 # 2 # 1 # 4 # 3 # 2 # 1
=
7 # 6 # 5
3 # 2 # 1
= 7 # 5 = 35
From Example 45, the value of P(7, 3) is 210, and C(7, 3) # (3!) = 35(6) = 210 =
P(7, 3).