Discrete Mathematics for Computer Science

Permutations and Combinations 437

Using the factorial function, we can express P(n, r) as

P(n, r)= n (n - 1)... (n - r + 1)

(n • (n - 1)... (n - r + 1))((n - r)(n - r - 1)...2.1)

((n - r)(n- r - 1)...2-.1)

n!

(n - r)!

This formula includes the case r = 0. If n = r, then P(n, n) = n! (Remember: 0! = 1.)

7.5.2 Linear Arrangements

An arrangement of n books on a shelf can be associated with a permutation of the integers

1, 2, 3,... n, where each number represents one of the books. The permutation indicates

the order in which the books are stored on the shelf from left to right. Two arrangements
of three books are shown in Figure 7.6.

C J A A C J

(^0) a r
o z t r r t 0 o^0 Za
Mk z k z
n n
g g
Figure 7.6 Arrangements of three books on a shelf.
Example 2.
(a) How many ways can eight different books be arranged on a shelf?
(b) How many ways can four of eight different books be arranged on a shelf?
(c) How many ways can eight different books be arranged on two shelves so that each
shelf contains four books?
Solution.
(a) The answer is the number of ordered ways of arranging the books on the shelf.
That is,
P(8, 8) = 8! = 40,320
(b) The number of ways to arrange four of the eight books is
P (8, 4) = 1680
(c) The answer is the product of the number of ways to put four books on one shelf and
the number of ways to put the remaining books on the second shelf. The number of

ways to arrange four books on the first shelf is P (8, 4), and the four remaining books