Chapter 14 Cardinality Rules560
(^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 14.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;a;8;h/ and .8;h;1;a/
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 14.2(a).
More generally, the functionfmaps exactly two sequences toeveryboard con-
figuration;fis a 2-to-1 function. Thus, by the quotient rule,jAj D 2 jBj. Rear-
ranging 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.
14.4.2 Knights of the Round Table
In how many ways can King Arthur arrange to seat hisndifferent knights at his
round table? A seating defines who sits where. Two seatings are considered to be
the samearrangementif each knight sits between the same two knights in both