Chapter 14 Cardinality Rules616
(f)Finally, explain why (14.21) immediately implies the usual form of the Inclusion-
Exclusion Principle:
jDjD
Xn
iD 1
. 1/iC^1
X
If1;:::;ng
jIjDi
ˇˇ
ˇˇ
ˇ
ˇ
\
j 2 I
Sj
ˇˇ
ˇˇ
ˇ
ˇ
: (14.22)
Homework Problems
Problem 14.53.
Aderangementis a permutation.x 1 ;x 2 ;:::;xn/of the setf1;2;:::;ngsuch that
xi ¤ifor alli. For example,.2;3;4;5;1/is a derangement, but.2;1;3;5;4/
is not because 3 appears in the third position. The objective of this problem is to
count derangements.
It turns out to be easier to start by counting the permutations that arenotde-
rangements. LetSi be the set of all permutations.x 1 ;x 2 ;:::;xn/that are not
derangements becausexiDi. So the set of non-derangements is
[n
iD 1
Si:
(a)What isjSij?
(b)What is
ˇˇ
Si\Sj
ˇˇ
wherei¤j?
(c)What is
ˇ
ˇSi 1 \Si 2 \\Sik
ˇ
ˇwherei 1 ;i 2 ;:::;ikare all distinct?
(d)Use the inclusion-exclusion formula to express the number of non-derangements
in terms of sizes of possible intersections of the setsS 1 ;:::;Sn.
(e)How many terms in the expression in part (d) have the form
ˇ
ˇSi 1 \Si 2 \\Sik
ˇ
ˇ‹
(f)Combine your answers to the preceding parts to prove the number of non-
derangements is:
nŠ