Mathematics for Computer Science

Chapter 15 Cardinality Rules504

(d)Prove that

jTjD

X

u 2 D

MT.u/: (15.17)

(e)Now use the previous parts to prove

jDjD

X

;¤If1;:::;ng

.1/jIjC^1

ˇˇ

ˇˇ

ˇ

\

i 2 I

Si

ˇˇ

ˇˇ

ˇ

(15.18)

(f)Finally, explain why (15.18) 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

ˇ

ˇˇ

ˇˇ

ˇ

: (15.19)

Homework Problems

Problem 15.30.
How many paths are there from point.0;0/to.50;50/if every step increments
one coordinate and leaves the other unchanged? How many are there when there
are impassable boulders sitting at points.10;11/and.21;20/? (You do not have
to calculate the number explicitly; your answer may be an expression involving
binomial coefficients.)
Hint:Count the number of paths going through.10;11/, the number through
.21;20/, and use Inclusion-Exclusion.

Problem 15.31.
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: