720 (14-6) Chapter 14 Counting and Probability

25. How many different ways are there to seat 7 students in a 30. Use the fundamental counting principle to find the number
row? 5,040 of subsets of the set a, b, c, d, e, f . 64
31. How many ways are there to mark the answers to a test that
consists of 10 true-false questions followed by 10 multiple-
choice questions with 5 options each? 1  1010
32. A fraternity votes on whether to accept each of 5 pledges.
How many different outcomes are possible for the vote?
32
33. Make a list of all of the ways to arrange the letters in the
word MILK. How many arrangements should be in your
list? 24
FIGURE FOR EXERCISE 25 34. Make a list of all of the permutations of the letters A, B, C,
D, and E taken 3 at a time. How many permutations should
26. A supply boat must stop at 9 oil rigs in the Gulf of Mexico.
be in your list? 60
How many different routes are possible? 362,880
27. How many different license plates can be formed by using Evaluate each expression.
3 digits followed by a single letter followed by 3 more 35. P(8, 3) 36. P(17, 4) 37. P(52, 0) 38. P(34, 1)
digits? How many if the single letter can occur anywhere 336 57,120 1 34
except last?
26,000,000, 156,000,000 P(10, 4) P(8, 3) P(12, 3) P(15, 6)
39.  40.  41.  42. 
28. How many different license plates can be formed by using 4! 3! 3! 6!
any 3 letters followed by any 3 digits? How many if we 210 56 220 5005
allow either the 3 digits or the 3 letters to come first? 14! 18! 98! 87!
17,576,000, 35,152,000 43.  44.  45.  46. 
3! 11! 17! 1! 95! 3! 83! 4!
29. Make a list of all of the subsets of the set a, b, c. How 364 18 152,096 2,225,895
many are there? 8

14.2 C O M B I N A T I O N S
In the preceding section we learned the fundamental counting principle and applied
In this it to finding the number of permutations of n objects taken r at a time. We will now
section learn how to count the number of combinations of n objects taken r at a time.
● Combinations of n Things r Combinations of n Things r at a Time
at a Time
● Permutations, Consider the problem of awarding 2 identical scholarships to 2 students among
Combinations, or Neither 4 finalists: Ahmadi, Butler, Chen, and Davis. Since the scholarships are identical,
● Labeling we do not count Ahmadi and Butler as different from Butler and Ahmadi. We can
easily list all possible choices of 2 students from the 4 possibilities A, B, C, and D:
A, B A, C A, D B, C B, D C, D
It is convenient to use set notation to list these choices because in set notation we
have A, B  B, A. Actually, we want the number of subsets or combinations of
size 2 from a set of 4 elements. This number is referred to as the number of combi-
nations of 4 things taken 2 at a time, and we use the notation C(4, 2) to represent it.
We have C(4, 2)  6.
If we had a first and second prize to give to 2 of 4 finalists, then
P(4, 2)  4  3  12 is the number of ways to award the prizes. If the prizes are
identical, then we do not count AB as different from BA, or AC as different from
CA, and so on. So we divide P(4, 2) by 2!, the number of permutations of the 2 prize
winners, to get C(4, 2).
 14.2 Combinations (14-7) 721

tip In general, the number of subsets of size r taken from a set of size n can be found
study by dividing P(n, r) by r!:
If you haven’t been studying P(n, r)
with a group during the se- C(n, r)  
mester, form a study group for
r!
n!
the final exam. You might Since P(n, r)  (n  r)! , we can write this expression as follows:
 
even ask your instructor to n!
meet with your study group. 
P(n, r) (n  r)! n!
Instructors love to help stu- C(n, r)      
dents who are eager to learn. r! r! (n  r)!r!
The notation  r is also used for C(n, r). We summarize these results in the follow-
n

ing theorem.

Combinations of n Things r at a Time

The number of combinations of n things taken r at a time (or the number of
subsets of size r from a set of n elements) is given by the formula


n n!
C(n, r)    for 0  r  n.
r (n  r)!r!

E X A M P L E 1 Combinations of n things r at a time

In how many ways can a committee of 4 people be chosen from a group of 12?
Solution
Choosing 4 people from a group of 12 is the same as choosing a subset of size 4
from a set of 12 elements. So the number of ways to choose the committee is the
number of combinations of 12 things taken 4 at a time:
12! 12  11  10  9  8  7  6  5  4  3  2  1
C(12, 4)      495
8! 4! 876543214321 ■

E X A M P L E 2 Finding a binomial coefficient

calculator What is the coefficient of a4b2 in the binomial expansion of (a  b)6?
Solution
Write (a  b)6  (a  b)(a  b)(a  b)(a  b)(a  b)(a  b). The terms of the
close-up product come from all of the different ways there are to select either a or b from
You can use factorial nota- each of the 6 factors and to multiply the selections. The number of ways to pick
6!
tion to calculate C (12, 4) or 4 factors for the selection of a is C(6, 4)     15. From the remaining 2 we
2! 4!
your calculator’s bulit-in for-
mula for combinations. With select b. So in the binomial expansion of (a  b)6 we find the term 15a4b2. ■
factorial notation you must
use parentheses around the Note that as in Example 2, the coefficients of the terms in any binomial expan-
denominator. sion are combinations. The coefficient of arbnr in (a  b)n is C(n, r).

Permutations, Combinations, or Neither

How do you know when to use the permutation formula and when to use the com-
bination formula? The key to answering this question is understanding what each
formula counts. In either case we are choosing from a group of distinct objects.
Compare the following examples.
722 (14-8) Chapter 14 Counting and Probability

E X A M P L E 3 Permutations of n things r at a time

How many ways are there to choose a president, a vice-president, and a treasurer
from a group of 9 people, assuming no one holds more than one office?
Solution
There are 9 choices for the president, 8 choices for the vice-president, and
7 choices for the treasurer. The number of ways to make these choices is
P(9, 3)  9  8  7  504. ■

Note that in Example 3 we are not just counting the number of ways to select 3
people from 9. In the number P(9, 3) every permutation of the 3 people selected is
counted.

E X A M P L E 4 Combinations of n things r at a time

How many ways are there to choose 3 people to receive a $100 prize from a group
of 9, assuming no one receives more than one prize?
Solution
Since each person chosen from the 9 is given the same treatment, the number of
choices is the same as the number of subsets of size 3 from a set of 9 elements.
9! 987
C(9, 3)      84.
6! 3! 3  2  1 ■

Note that in Example 4 we do not count different arrangements of the 3 people

selected. The next example is neither a permutation nor a combination.

E X A M P L E 5 The fundamental counting principle

How many ways are there to answer a 9-question multiple-choice test in which each
question has 3 possible answers?
Solution
There are 3 outcomes to the event of choosing the first answer, 3 outcomes to the
event of choosing the second answer, and so on. By the fundamental counting
principle there are 39  19,683 ways to answer the 9 questions. ■

Note that in choosing the answer to each question in Example 5 we may repeat
answers, so we are not choosing from a set of distinct objects as in permutations and
combinations. In the next example we use both the fundamental counting principle
and the permutation formula.

E X A M P L E 6 The fundamental counting principle and permutations

Josephine has 4 different mathematics books, 3 different art books, and 5 different
music books that she plans to display on a shelf. If she plans to keep each type of
book together and put the types in the order mathematics–art–music, then how
many different arrangements are possible?
 14.2 Combinations (14-9) 723

Solution
helpful hint
First observe that the mathematics books can be arranged in P(4, 4)  4!  24
You cannot solve counting ways, the art books in P(3, 3)  3!  6 ways, and the music books in
problems by picking out the P(5, 5)  5!  120 ways. Now we use the fundamental counting principle to get
numbers in the problem and 24  6  120  17,280 as the number of ways to arrange the books on the shelf.
performing a computation to
■
get the answer. This approach
to Example 5 will lead you to
Labeling
wrong answers, such as 9
! 3
,9 ,
3! 6!
or 3  9. You must think about In a labeling problem we count the number of ways to put labels on distinct
the problem. objects.

E X A M P L E 7 The fundamental counting principle and combinations

Twelve students have volunteered to help clean up a small oil spill. The project di-
rector needs 3 bird washers, 4 rock wipers, and 5 sand cleaners. In how many ways
can these jobs (labels) be assigned to these 12 students?
Solution
Since the 3 bird washers all get the same label, the number of ways to select the
3 students is C(12, 3). The number of ways to select 4 rock wipers from the re-
maining 9 students is C(9, 4). The number of ways to select the 5 sand cleaners from
the remaining 5 students is C(5, 5). By the fundamental counting principle the num-
ber of ways to make all 3 selections is
12! 9! 5! 12!
C(12, 3)  C(9, 4)  C(5, 5)          27,720.
9! 3! 5! 4! 0! 5! 3! 4! 5! ■
Note that in Example 7 there were 12 distinct objects to be labeled with 3 labels
of one type, 4 labels of another type, and 5 labels of a third type, and the number of
12!
ways to assign those labels was found to be  . Instead of using combinations
3! 4! 5!
and the fundamental counting principle as in Example 7, we can use the following
theorem.

Labeling
In a labeling problem n distinct objects are each to be given a label with
each object getting exactly one label. If there are r1 labels of the first
type, r2 labels of the second type, . . . , and rk labels of the kth type, where
r1  r2  . . .  rk  n, then the number of ways to assign the labels to the
n!
objects is  
r ! r ! . . . r !.
1 2 k

E X A M P L E 8 A labeling problem
How many different arrangements are there for the 11 letters in the word
MISSISSIPPI?
Solution
This problem is a labeling problem if we think of the 11 positions for the letters as
11 distinct objects to be labeled. There are 1 M-label, 4 S-labels, 4 I-labels, and
2 P-labels. So the number of ways to arrange the letters in MISSISSIPPI is
11!
  34,650. ■
1! 4! 4! 2!
724 (14-10) Chapter 14 Counting and Probability

E X A M P L E 9 Coefficients in a trinomial expansion

What is the coefficient of a3b2c in the expansion of (a  b  c)6?
Solution
The terms of the product (a  b  c)6 come from all of the different ways there are
to select a, b, or c from each of the 6 distinct factors and to multiply the selections.
The number of ways to pick 3 factors from which we select a, 2 factors from which
6! 654321
3! 2! 1!  3  2  1  2  1  1 
we select b, and 1 factor from which we select c is    60.
So in the expansion we have the term 60a b c.3 2
■

The coefficients of the terms in an expansion such as that of Example 9 are called
multinomial coefficients. Determining the coefficients is a labeling problem.
We may think of permutation and combination problems as being very different,
but they are both labeling problems. For example, to find the number of subsets of
size 3 from a set of size 5, we are assigning 3 I-labels and 2 O-labels (I for in and
5!
3! 2!  C(5, 3). To find the
O for out) to the 5 distinct objects of the set. Note that  

number of ways to give a First, Second, and Third prize to 3 of 10 people, we are
assigning 1 F-label, 1 S-label, 1 T-label, and 7 N-labels (N for no prize) to the
10!
10 distinct people. Note that 1! 1! 1! 7!  P(10, 3).


WARM-UPS
True or false? Explain your answer.
1. The number of ways to choose 2 questions to answer out of 3 questions on
an essay test is C(3, 2). True
2. The number of ways to choose 1 question to omit out of 3 questions on an
essay test is C(3, 1). True
3. C(12, 4)  C(4, 12) False
4. P(10, 6) C(10, 6) False
5. There are P(10, 3) ways to label randomly 3 of the top 10 restaurants in
Philadelphia as “superior.” False
6. There are 16 ways to select 4 of 20 students to stay after school.
20
True
7. P(9, 4)  (4!)  C(9, 4) True
 5
8
8. P(8, 3)  False
9. C(100, 1)  100 True
8!
10. 
1! 1! 1! 5!
 P(8, 3) True

14. 2 EXERCISES
Reading and Writing After reading this section, write out the 2. How many combinations are there for n things taken r at a
answers to these questions. Use complete sentences. time?
1. What is a combination? The number of combinations of n things taken r at a time is
A combination of n things taken r at a time is a subset of n!
.
size r taken from a set of n elements. r!(n  r)!
 14.2 Combinations (14-11) 725

3. What is a labeling problem? 20. In how many different ways can Professor Lee return her
In a labeling problem we want the number of ways of la- examination papers to a class of 12 students if she always
beling n objects with n labels, where some of the labels are returns the best paper first and the worst paper last?
identical. 3,628,800
4. What are multinomial coefficients? 21. How many ways are there to select 5 seats from a 150-seat
The multinomial coefficients are the coefficients of the auditorium to be occupied by 5 plain-clothes officers?
terms when a sum of three or more letters is raised to a 591,600,030
power. 22. For her final exam in Literature 302 Charlotte is allowed to
Solve each problem. See Examples 1 and 2. omit any 5 of the 8 essay questions. How many ways are
there for her to omit the 5 questions? 56
5. How many 5-card poker hands are possible when you are
dealt 5 cards from a deck of 52? 2,598,960 23. How many distinct chords (line segments with endpoints
on the circle) are determined by 3 points lying on a circle?
6. How many 13-card bridge hands are possible when you are By 4 points? By 5 points? By n points?
dealt 13 cards from a deck of 52? 6.3501  1011 3, 6, 10, C(n, 2)
7. How many ways are there to select 3 candidates from the
5 finalists for an in-depth interview? 10
8. How many ways are there to select 12 welders to be laid off
from 30 welders employed at the Ingalls Shipyard?
86,493,225
9. How many ways are there for a health inspector to select 5
restaurants to visit from a list of 20 restaurants? 15,504
10. The water inspector in drought-stricken Marin County ran- 3 points 4 points
domly selects 10 homes for inspection from a list of 25 sus-
pected violators of the rationing laws. How many ways are FIGURE FOR EXERCISE 23
there to pick the 10 homes? 3,268,760 24. How many distinct triangles are determined by 5 points
11. In the Florida Lottery you can win a lot of money for lying on a circle, where the vertices of each triangle are
merely selecting 6 different numbers from the numbers 1 chosen from the 5 points? 10
through 49. How many different ways are there to select the 25. If the outcome of tossing a pair of dice is thought of as an
6 numbers? 13,983,816 ordered pair of numbers, then how many ordered pairs are
12. In the game Fantasy Five you can win by selecting 5 differ- there? 36
ent numbers from the numbers 1 through 39. How many 26. Francene is eligible to take 4 different mathematics classes,
ways are there to select the 5 numbers? 575,757 5 different history classes, 6 different psychology classes,
and 3 different literature classes. If her schedule is to con-
13. What is the coefficient of w3y4 in the expansion of
sist of one class from each category, then how many differ-
(w  y)7? 35
ent schedules are possible for her? 360
14. What is the coefficient of a5z9 in the expansion of (a  z)14 ? 27. The outcome “heads” or “tails” is recorded on each toss of
2002 a coin. If we think of the outcome for 3 tosses as an ordered
Solve each problem. See Examples 3–5. triple, then how many outcomes are there for 3 tosses of a
15. The Dean’s Search Committee must choose 3 candidates coin? 8
from a list of 6 and rank them as first, second, and third. 28. A coin and a die are tossed. How many different outcomes
How many different outcomes are possible? 120 are possible? 12
16. The Provost’s Search Committee must choose 3 candidates 29. Explain why C(n, r)  C(n, n  r).
from a list of 8 and submit the names to the president un- n! n!
C(n, r)   and C(n, n  r)  
ranked. How many different outcomes are possible? 56 (n  r)!r! r!(n  r)!
17. Charlotte must write on any 3 of the 8 essay questions on 30. Is P(n, r)  P(n, n  r)? Explain your answer. no
the final exam in History 201. How many ways are there for Solve each problem. See Example 6.
her to pick the questions? 56
31. Juanita is eligible to take 4 different mathematics classes
18. How many ways are there for Murphy to mark the answers and 5 different history classes. If her schedule is to consist
to 8 multiple-choice questions, each of which has 5 possi- of two classes from each category, then how many different
ble answers? 390,625 schedules are possible for her? 60
19. In how many different ways can Professor Reyes return his 32. A committee consisting of 2 men and 1 woman is to be
examination papers to a class of 12 students? formed from a department consisting of 8 men and 3
479,001,600 women. How many different committees are possible? 84
726 (14-12) Chapter 14 Counting and Probability

33. In a class of 20 students the teacher randomly assigns 4 A’s, 42. How many different orders are possible for 3 identical
5 B’s, and 11 C’s. In how many ways can these grades be contemporary, 4 identical traditional, and 6 identical
assigned? 21,162,960 colonial homes to march in a parade of homes? 60,060
34. How many ways are there to seat 3 boys and 3 girls in a row 43. Twenty salespeople are getting new cars. How many ways
with no 2 boys and no 2 girls sitting next to each other? are there to assign 6 identical Chevrolets, 5 identical Fords,
72 8 identical Buicks, and 1 Lincoln to them?
35. How many different orders are there for 4 marching bands 698,377,680
and 4 floats to parade if a marching band must lead the pa- 44. Twenty different Fords are being sent to 4 Ford dealers. In
rade and we cannot have 2 bands in a row or 2 floats in a how many ways can Bill Poole Ford get 3 cars, Heritage
row? 576 Ford get 5 cars, Mid-City Ford get 5 cars, and Northside
Ford get 7 cars? 5,587,021,440
45. Nine sofas are to be discounted at Sofa City with discounts
as large as 75% off the manufacturers suggested retail
price. (Sorry, none sold to dealers.) How many ways are
there to mark 4 of the sofas 10% off, 4 of them 15% off, and
1 of them 75% off? 630
46. A combination for a safe is a sequence of 4 numbers with
no repetitions selected from the integers 1 through 99. How
many combinations are possible? Is combination the proper
word to use here? 90,345,024, no

FIGURE FOR EXERCISE 35

36. In how many ways can 8 students be seated in a row if 2 of
them must be seated next to one another? 10,080
Solve each problem. See Examples 7–9.
37. A teacher randomly assigns 6 A’s, 3 B’s, and 7 C’s to a
batch of 16 term papers. In how many different ways can
she do this? 960,960 FIGURE FOR EXERCISE 46
38. The 15 volunteers for the annual Bluegrass Festival are to
be divided into 3 groups of 5 each and assigned to tickets, 47. What is the coefficient of a3b2c5 in the expansion of
parking, and cleanup. In how many ways can these assign- (a  b  c)10? 2520
ments be made? 756,756 48. What is the coefficient of wx 2y 3z 9 in the expansion of
39. Bob, Carol, Ted, and Alice are playing bridge. How many (w  x  y  z)15? 300,300
different ways are there to give each of them 13 cards from 49. What is the coefficient of a3b5 in the expansion of
the deck of 52? Is the answer larger or smaller than the (a  b  c)8? 56
number of seconds in a trillion years?
5.36447  1028, larger 50. What is the coefficient of x 2z 5 in the expansion of
(x  y  z)7? 21
40. Bret, Bart, and Mad Dog are playing poker. How many dif-
ferent ways are there to give each of them 5 cards from a
deck of 52? 3.3913  1018
41. How many different arrangements are there for the letters
in the word TOYOTA? ALGEBRA? STATISTICS?
180, 2,520, 50,400