Mathematics for Computer Science

Chapter 14 Cardinality Rules614

is called acword. A password can be a cword which does not contain any of the
subwords “fails”, “failed”, or “drop.”
For example, the following two words are passwords: adefiloprs, srpolifeda,
but the following three cwords are not: adropeflis,failedrops,dropefails.
(a)How many cwords contain the subword “drop”?

(b)How many cwords contain both “drop” and “fails”?

(c)Use the Inclusion-Exclusion Principle to find a simple arithmetic formula in-
volving factorials for the number of passwords.

Problem 14.51.
We want to count step-by-step paths between points in the plane with integer coor-
dinates. Only two kinds of step are allowed: a right-step which increments thex
coordinate, and an up-step which increments theycoordinate.

(a)How many paths are there from.0;0/to.20;30/?

(b)How many paths are there from.0;0/to.20;30/that go through the point
.10;10/?

(c)How many paths are there from.0;0/to.20;30/that donotgo through either
of the points.10;10/and.15;20/?

Hint:LetPbe the set of paths from.0;0/to.20;30/,N 1 be the paths inPthat go
through.10;10/andN 2 be the paths inPthat go through.15;20/.

Problem 14.52.
Let’s develop a proof of the Inclusion-Exclusion formula using high school algebra.

(a)Most high school students will get freaked by the following formula, even
though they actually know the rule it expresses. How would you explain it to them?

Yn

iD 1

. 1 xi/D

X

If1;:::;ng

.1/jIj

Y

j 2 I

xj: (14.15)

Hint:Show them an example.