Discrete Mathematics for Computer Science

438 CHAPTER 7 Counting and Combinatorics

can be arranged in P(4, 4) ways on the second shelf. Therefore, the total number of

arrangements will be

(# Arrangements of books on two shelves) = (# Arrangements on first shelf)

• (# Arrangements on second shelf)

= P(8,4)- P(4,4)

= (8!/4!) -(4!/0!)

=8!

= 40,320

The solution to part (c) is the same as the one found for part (a). To see that the answer for

part (c) is the same as the answer for part (a) just put the last four books in any arrangement

for (a) on the second shelf. Similarly, for any arrangement for part (c), move the books on

the second shelf up to the first shelf, placing them after the books that are already there. N

In some instances, certain objects must be placed in specified positions. The next ex-

ample shows how such a counting problem can be solved.

Example 3. A collection of eight books consists of two books on artificial intelligence,

three books on operating systems, and three books on data structures.

(a) How many ways can the books be arranged on a shelf so that all books on a single

subject are together?

(b) How many ways can the books be arranged on a shelf so that the three books on

operating systems are together?

(c) How many ways can the books be arranged on a shelf so that the two books on artificial

intelligence occur at the right end of the arrangement?

Solution.

(a) Identify the books on each subject with a single "book". Let BK1 represent the two

books on artificial intelligence, BK2 represent the three books on operating systems,

and BK3 represent the three books on data structures. The problem becomes one of

arranging three "books" called BKI, BK2, and BK3. The first step is to determine the

number of ways these three "books" can be arranged, these books can be arranged

3! ways. The second, third, and fourth steps involve finding the number of ways to

arrange the books represented by BKI, BK2, and BK3, respectively. Wherever the two

books on artificial intelligence occur, they can be arranged in 2! ways. The three books

on operating systems and the three books on data structures can each be arranged in 3!

ways. Therefore, by the Multiplication Principle, the total number of arrangements is

(# Ways to arrange the three categories of books)

• (# Ways to arrange the artificial intelligence books (BK1))
  
  
  • (# Ways to arrange the operating systems books (BK2))
    
    
    • (# Ways to arrange the data structures books (BK3))
      
      
      • 3! • 2! • 3! -3!
        = 432
        (b) This problem can be considered the same as the problem of arranging six "books" on
        a shelf where one "book" represents the three books on operating systems that must