Page 429 - Discrete Mathematics and Its Applications

408 6 / Counting

EXAMPLE 2 LetS ={1, 2, 3}.Theorderedarrangement3,1,2isapermutationofS.Theorderedarrangement
3, 2 is a 2-permutation of S. ▲

The number of r-permutations of a set with n elements is denoted by P (n, r). We can find
P (n, r) using the product rule.

EXAMPLE 3 Let S ={a, b, c}. The 2-permutations of S are the ordered arrangements
a, b; a, c; b, a; b, c; c, a; and c, b. Consequently, there are six 2-permutations of this set
with three elements. There are always six 2-permutations of a set with three elements. There
are three ways to choose the first element of the arrangement. There are two ways to choose the
second element of the arrangement, because it must be different from the first element. Hence,
by the product rule, we see that P(3, 2) = 3 · 2 = 6. the first element. By the product rule, it
follows that P(3, 2) = 3 · 2 = 6. ▲

We now use the product rule to find a formula for P (n, r) whenever n and r are positive integers
with 1 ≤ r ≤ n.

THEOREM 1 If n is a positive integer and r is an integer with 1 ≤ r ≤ n, then there are

P (n, r) = n(n − 1)(n − 2) ··· (n − r + 1)

r-permutations of a set with n distinct elements.

Proof: We will use the product rule to prove that this formula is correct. The first element of the
permutation can be chosen in n ways because there are n elements in the set. There are n − 1
ways to choose the second element of the permutation, because there are n − 1 elements left
in the set after using the element picked for the first position. Similarly, there are n − 2 ways
to choose the third element, and so on, until there are exactly n − (r − 1) = n − r + 1 ways to
choose the rth element. Consequently, by the product rule, there are

n(n − 1)(n − 2) ··· (n − r + 1)

r-permutations of the set.

Note that P (n, 0) = 1 whenever n is a nonnegative integer because there is exactly one
way to order zero elements. That is, there is exactly one list with no elements in it, namely the
empty list.
We now state a useful corollary of Theorem 1.

n!
COROLLARY 1 If n and r are integers with 0 ≤ r ≤ n, then P (n, r) = .
(n − r)!

Proof: When n and r are integers with 1 ≤ r ≤ n, by Theorem 1 we have

n!
P(n, r) = n(n − 1)(n − 2) ··· (n − r + 1) =
(n − r)!
n! n!
Because = = 1 whenever n is a nonnegative integer, we see that the formula
(n − 0)! n!
n!
P(n, r) = also holds when r = 0.
(n − r)!