Page 430 - Discrete Mathematics and Its Applications

6.3 Permutations and Combinations 409

By Theorem 1 we know that if n is a positive integer, then P (n, n) = n!. We will illustrate
this result with some examples.
EXAMPLE 4 How many ways are there to select a first-prize winner, a second-prize winner, and a third-prize
winner from 100 different people who have entered a contest?

Solution: Because it matters which person wins which prize, the number of ways to pick the
three prize winners is the number of ordered selections of three elements from a set of 100
elements, that is, the number of 3-permutations of a set of 100 elements. Consequently, the
answer is
▲
P(100, 3) = 100 · 99 · 98 = 970,200.

EXAMPLE 5 Suppose that there are eight runners in a race. The winner receives a gold medal, the second-
place finisher receives a silver medal, and the third-place finisher receives a bronze medal. How
many different ways are there to award these medals, if all possible outcomes of the race can
occur and there are no ties?

Solution: The number of different ways to award the medals is the number of 3-permutations
of a set with eight elements. Hence, there are P(8, 3) = 8 · 7 · 6 = 336 possible ways to award
the medals. ▲

EXAMPLE 6 Suppose that a saleswoman has to visit eight different cities. She must begin her trip in a specified
city, but she can visit the other seven cities in any order she wishes. How many possible orders
can the saleswoman use when visiting these cities?

Solution: The number of possible paths between the cities is the number of permutations of
seven elements, because the first city is determined, but the remaining seven can be ordered
arbitrarily. Consequently, there are 7!= 7 · 6 · 5 · 4 · 3 · 2 · 1 = 5040 ways for the saleswoman
to choose her tour. If, for instance, the saleswoman wishes to find the path between the cities
with minimum distance, and she computes the total distance for each possible path, she must
consider a total of 5040 paths! ▲

EXAMPLE 7 How many permutations of the letters ABCDEFGH contain the string ABC ?

Solution: Because the letters ABC must occur as a block, we can find the answer by finding the
number of permutations of six objects, namely, the block ABC and the individual letters D, E,
F, G, and H. Because these six objects can occur in any order, there are 6!= 720 permutations
of the letters ABCDEFGH in which ABC occurs as a block. ▲

Combinations

We now turn our attention to counting unordered selections of objects. We begin by solving a
question posed in the introduction to this section of the chapter.

EXAMPLE 8 How many different committees of three students can be formed from a group of four students?

Solution: To answer this question, we need only find the number of subsets with three elements
from the set containing the four students. We see that there are four such subsets, one for
each of the four students, because choosing three students is the same as choosing one of the
four students to leave out of the group. This means that there are four ways to choose the
three students for the committee, where the order in which these students are chosen does not
matter. ▲