272
Sets, Combinatorics, and Probability
S e c t i o n 4 . 4 PermutationS and CombinationS
Permutations
Example 26 in Section 4.2 discussed the problem of counting all possibilities for
the last four digits of a telephone number with no repeated digits. In this problem,
the number 1259 is not the same as the number 2951 because the order of the
four digits is important. An ordered arrangement of objects is called a permutation. Each of these numbers is a permutation of 4 distinct objects chosen from
a set of 10 distinct objects (the digits). How many such permutations are there?
The answer, found by using the multiplication principle, is 10 # 9 # 8 # 7—there are
10 choices for the first digit, then 9 for the next digit because repetitions are not allowed, 8 for the next digit, and 7 for the fourth digit. The number of permutations
of r distinct objects chosen from n distinct objects is denoted by P(n, r). Therefore
the solution to the problem of the four-digit number without repeated digits can be
expressed as P(10, 4).
A formula for P(n, r) can be written using the factorial function. For a positive
integer n, n factorial is defined as n(n − 1)(n − 2) c 1 and denoted by n!; also, 0!
is defined to have the value 1. From the definition of n!, we see that
n! = n(n − 1)!
and that for r < n,
n!
(n − r)!
=
n(n − 1) c (n − r + 1)(n − r)!
(n − r)!
= n(n − 1) c (n − r + 1)
Using the factorial function,
P(10, 4) = 10 # 9 # 8 # 7
=
10 # 9 # 8 # 7 # 6 # 5 # 4 # 3 # 2 # 1
6 # 5 # 4 # 3 # 2 # 1
=
10!
6!
=
10!
(10 − 4)!
In general, P(n, r) is given by the formula
P(n, r) =
n!
(n − r)!
for 0 ≤ r ≤ n
example 45
The value of P(7, 3) is
7!
(7 − 3)!
=
7!
4!
=
7 # 6 # 5 # 4 # 3 # 2 # 1
4 # 3 # 2 # 1
= 7 # 6 # 5 = 210
example 46
Three somewhat special cases that can arise when computing P(n, r) are the two
“boundary conditions” P(n, 0) and P(n, n), and also P(n, 1). According to the
formula,
Sets, Combinatorics, and Probability
S e c t i o n 4 . 4 PermutationS and CombinationS
Permutations
Example 26 in Section 4.2 discussed the problem of counting all possibilities for
the last four digits of a telephone number with no repeated digits. In this problem,
the number 1259 is not the same as the number 2951 because the order of the
four digits is important. An ordered arrangement of objects is called a permutation. Each of these numbers is a permutation of 4 distinct objects chosen from
a set of 10 distinct objects (the digits). How many such permutations are there?
The answer, found by using the multiplication principle, is 10 # 9 # 8 # 7—there are
10 choices for the first digit, then 9 for the next digit because repetitions are not allowed, 8 for the next digit, and 7 for the fourth digit. The number of permutations
of r distinct objects chosen from n distinct objects is denoted by P(n, r). Therefore
the solution to the problem of the four-digit number without repeated digits can be
expressed as P(10, 4).
A formula for P(n, r) can be written using the factorial function. For a positive
integer n, n factorial is defined as n(n − 1)(n − 2) c 1 and denoted by n!; also, 0!
is defined to have the value 1. From the definition of n!, we see that
n! = n(n − 1)!
and that for r < n,
n!
(n − r)!
=
n(n − 1) c (n − r + 1)(n − r)!
(n − r)!
= n(n − 1) c (n − r + 1)
Using the factorial function,
P(10, 4) = 10 # 9 # 8 # 7
=
10 # 9 # 8 # 7 # 6 # 5 # 4 # 3 # 2 # 1
6 # 5 # 4 # 3 # 2 # 1
=
10!
6!
=
10!
(10 − 4)!
In general, P(n, r) is given by the formula
P(n, r) =
n!
(n − r)!
for 0 ≤ r ≤ n
example 45
The value of P(7, 3) is
7!
(7 − 3)!
=
7!
4!
=
7 # 6 # 5 # 4 # 3 # 2 # 1
4 # 3 # 2 # 1
= 7 # 6 # 5 = 210
example 46
Three somewhat special cases that can arise when computing P(n, r) are the two
“boundary conditions” P(n, 0) and P(n, n), and also P(n, 1). According to the
formula,