Chapter 15 Cardinality Rules456
(^8) 0Z0Z0Z0Z
(^7) Z0Z0m0Z0
(^6) 0Z0Z0Z0Z
(^5) Z0Z0Z0Z0
(^4) 0a0Z0Z0Z
(^3) Z0Z0Z0Z0
(^2) 0Z0Z0o0Z
(^1) Z0Z0Z0Z0
a b c d e f g h
(a) valid
(^8) 0Z0Z0Z0Z
(^7) Z0Z0Z0Z0
(^6) 0Z0ZpZ0Z
(^5) Z0Z0Z0Z0
(^4) 0Z0Z0Z0Z
(^3) Z0a0ZnZ0
(^2) 0Z0Z0Z0Z
(^1) Z0Z0Z0Z0
a b c d e f g h
(b) invalid
Figure 15.1 Two ways of placing a pawn (p), a knight (N), and a bishop (B) on
a chessboard. The configuration shown in (b) is invalid because the bishop and the
knight are in the same row.
cPis one of 8 columns
rNis one of 7 rows (any one butrP)
cNis one of 7 columns (any one butcP)
rBis one of 6 rows (any one butrPorrN)
cBis one of 6 columns (any one butcPorcN)
Thus, the total number of configurations is.8 7 6/^2.
15.3.3 Permutations
Apermutationof a setSis a sequence that contains every element ofSexactly
once. For example, here are all the permutations of the setfa;b;cg:
.a;b;c/ .a;c;b/ .b;a;c/
.b;c;a/ .c;a;b/ .c;b;a/
How many permutations of ann-element set are there? Well, there arenchoices
for the first element. For each of these, there aren 1 remaining choices for the
second element. For every combination of the first two elements, there aren 2
ways to choose the third element, and so forth. Thus, there are a total of
n.n 1/.n 2/ 3 2 1 DnŠ
permutations of ann-element set. In particular, this formula says that there are