Chapter 15 Cardinality Rules458
(^8) 0Z0Z0Z0s
(^7) Z0Z0Z0Z0
(^6) 0Z0Z0Z0Z
(^5) Z0Z0Z0Z0
(^4) 0Z0Z0Z0Z
(^3) Z0Z0Z0Z0
(^2) 0Z0Z0Z0Z
(^1) s0Z0Z0Z0
a b c d e f g h
(a) valid
(^8) 0Z0Z0Z0Z
(^7) Z0Z0Z0Z0
(^6) 0Z0s0Z0Z
(^5) Z0Z0Z0Z0
(^4) 0Z0Z0Z0Z
(^3) Z0Z0Z0Z0
(^2) 0Z0Z0Z0Z
(^1) Z0ZrZ0Z0
a b c d e f g h
(b) invalid
Figure 15.2 Two ways to place 2 rooks (R) on a chessboard. The configuration
in (b) is invalid because the rooks are in the same column.
But now there’s a snag. Consider the sequences:
.1;1;8;8/ and .8;8;1;1/
The first sequence maps to a configuration with a rook in the lower-left corner and
a rook in the upper-right corner. The second sequence maps to a configuration with
a rook in the upper-right corner and a rook in the lower-left corner. The problem is
that those are two different ways of describing thesameconfiguration! In fact, this
arrangement is shown in Figure 15.2(a).
More generally, the functionfmaps exactly two sequences toeveryboard con-
figuration; that isf is a 2-to-1 function. Thus, by the quotient rule,jAjD 2 jBj.
Rearranging terms gives:
jBjD
jAj
2
D
.87/^2
2
:
On the second line, we’ve computed the size ofAusing the General Product Rule
just as in the earlier chess problem.
15.4.2 Knights of the Round Table
In how many ways can King Arthur arrange to seat hisndifferent knights at his
round table? Two seatings are considered to be the samearrangementif they yield
the same sequence of knights starting at knight number 1 and going clockwise
around the table. For example, the following two seatings determine the same
arrangement: