Mathematics for Computer Science

15.4. The Division Rule 459

"!

# k^1

k 2

k 3

k 4

"!

# k^3

k 4

k 1

k 2

So a seating is determined by the sequence of knights going clockwise around
the table starting at the top seat. This means seatings are formally the same as the
set,A, of all permutations of the knights. An arrangement is determined by the
sequence of knights going clockwise around the table starting after knight number
1, so it is formally the same as the set,B, of all permutations of knights 2 through
n. We can map each permutation inAto an arrangement in setBby seating the
first knight in the permutation at the top of the table, putting the second knight to
his left, the third knight to the left of the second, and so forth all the way around
the table. For example:

.k 2 ;k 4 ;k 1 ;k 3 / !

"!

# k^1

k 3

k 2

k 4

This mapping is actually ann-to-1 function fromAtoB, since allncyclic shifts of
the original sequence map to the same seating arrangement. In the example,nD 4
different sequences map to the same seating arrangement:

.k 2 ;k 4 ;k 1 ;k 3 /

.k 4 ;k 1 ;k 3 ;k 2 /

.k 1 ;k 3 ;k 2 ;k 4 /

.k 3 ;k 2 ;k 4 ;k 1 /

!

"!

# k^1

k 3

k 2

k 4

Therefore, by the division rule, the number of circular seating arrangements is:

jBjD

jAj

n

D

nŠ

n

D.n1/Š

Note thatjAjDnŠsince there arenŠpermutations ofnknights.