Mathematics for Computer Science

Chapter 15 Cardinality Rules474

These sums have alternating signs in the Inclusion-Exclusion formula, with the
sum of thek-way intersections getting the sign.1/k^1. This finally leads to a
symbolic version of the rule:

Rule(Inclusion-Exclusion).
ˇ
ˇ
ˇˇ
ˇ

[n

iD 1

Si

ˇ

ˇ

ˇˇ

ˇ

D

Xn

iD 1

jSij

X

1 i<jn

jSi\Sjj

C

X

1 i<j<kn

jSi\Sj\SkjC

C.1/n^1

ˇ

ˇˇ

ˇˇ

\n

iD 1

Si

ˇ

ˇˇ

ˇˇ:

While it’s often handy express the rule in this way as a sum of sums, it is not
necessary to group the terms by how many sets are in the intersections. So another
way to state the rule is:

Rule(Inclusion-Exclusion-II).
ˇ
ˇ
ˇˇ
ˇ

[n

iD 1

Si

ˇ

ˇ

ˇˇ

ˇ

D

X

;¤If1;:::;ng

.1/jIjC^1

ˇ

ˇ

ˇˇ

ˇ

\

i 2 I

Si

ˇ

ˇ

ˇˇ

ˇ

A proof of these rules using just highschool algebra is given in Problem 15.29.

15.10.5 Computing Euler’s Function

As an example, let’s use Inclusion-Exclusion to derive an explicit formula (15.3)
for Euler’s function,.n/. By definition,.n/is the number of nonnegative inte-
gers less than a positive integernthat are relatively prime ton. But the setSof
nonnegative integers less thannthat arenotrelatively prime tonwill be easier to
count.
Suppose the prime factorization ofnispe 11


pemmfor distinct primespi. This
means that the integers inSare precisely the nonnegative integers less thannthat
are divisible by at least one of thepi’s. LettingCabe the set of nonnegative integers
less thannthat are divisible bya, we have

SD

[m

iD 1

Cpi: