Mathematics for Computer Science

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Š



1

1Š

1

2Š

C

1

3Š

̇

1

nŠ



:

Conclude that the number of derangements is

nŠ



1

1

1Š

C

1

2Š

1

3Š

C


̇

1

nŠ



: