Discrete Mathematics for Computer Science

Permutations and Combinations 439

occur together. After the six books are arranged, the location for the three books on op-

erating systems that are considered as a single "book" to this point of the arrangement

process can be arranged in 3! ways. The number of arrangements is

(# Ways to arrange six books) -(# Ways to arrange the operating systems books)

= 61 • 3!

= 4320

(c) In this case, there are six books to arrange, and for each of these arrangements, the two

artificial intelligence books must follow in some order. The number of such arrange-

ments is

(# Ways to arrange six books) • (# Ways to arrange two artificial intelligence books)

• 6! -2!
  = 1440

75.3 Circular Permutations

The permutations considered to this point assume that the ordering is a linear ordering. A

slight variation of this occurs when one tries to count the number of ways to seat n people

at a round table. Three possible arrangements of five people seated at a round table are

shown in Figure 7.7.

Kevin Henry Cristin

Henry 52Cristin Cristin 52Andrew Kevin52Her

4 3 4 3 4 3
Maure~enn Andrew Kevin Maureen Maureen Andrew

Figure 7.7 Different seating arrangements.

For the seating arrangements shown in Figure 7.7(a) and 7.7(b), each person does not

have the same pair of neighbors. By convention, two seating arrangements are considered

to be equivalent if one arrangement can be transformed into the other by a clockwise rota-

tion of all the people by the same number of seats around the table. The seating arrange-

ments shown in Figure 7.7(b) and 7.7(c) are considered to be the same seating arrangement,

since everyone in the seating arrangement shown in Figure 7.7(b) can be shifted one place

around the table in a clockwise direction to form the seating arrangement shown in Fig-

ure 7.7(c). Thus, for any fixed seating arrangement, n seating arrangements are considered

to be the same; that is, we move all the people i seats in a clockwise direction for any

i e {1,2. n}.