Mathematics for Computer Science

15.10. Inclusion-Exclusion 475

We’ll be able to find the size of this union using Inclusion-Exclusion because the
intersections of theCp’s are easy to count. For example,Cp\Cq\Cris the set
of nonnegative integers less thannthat are divisible by each ofp,qandr. But
since thep;q;rare distinct primes, being divisible by each of them is the same
as being divisible by their product. Now observe that ifkis a positive divisor of
n, then exactlyn=knonnegative integers less thannare divisible byk, namely,
0;k;2k;:::;..n=k/1/k. So exactlyn=pqrnonnegative integers less thannare
divisible by all three primesp,q,r. In other words,

jCp\Cq\CrjD

n

pqr

:

Reasoning this way about all the intersections among theCp’s and applying
Inclusion-Exclusion, we get

jSjD

ˇˇ

ˇˇ

ˇ

[m

iD 1

Cpi

ˇˇ

ˇˇ

ˇ

D

Xm

iD 1

ˇ

ˇCpi

ˇ

ˇ

X

1 i<jm

ˇ

ˇCpi\Cpj

ˇ

ˇ

C

X

1 i<j<km

ˇ

ˇCpi\Cpj\Cpk

ˇ

ˇ


C.1/m^1

ˇˇ

ˇˇ

ˇ

\m

iD 1

Cpi

ˇˇ

ˇˇ

ˇ

D

Xm

iD 1

n

pi

X

1 i<jm

n

pipj

C

X

1 i<j<km

n

pipjpk

C.1/m^1

n

p 1 p 2 


pn

Dn

0

@

Xm

iD 1

1

pi

X

1 i<jm

1

pipj

C

X

1 i<j<km

1

pipjpk

C.1/m^1

1

p 1 p 2 


pn

1

A

But.n/DnjSjby definition, so

.n/Dn

0

@ 1

Xm

iD 1

1

pi

C

X

1 i<jm

1

pipj

X

1 i<j<km

1

pipjpk

C


C.1/m

1

p 1 p 2 


pn

1

A

Dn

Ym

iD 1



1

1

pi



: (15.3)

Yikes! That was pretty hairy. Are you getting tired of all that nasty algebra? If
so, then good news is on the way. In the next section, we will show you how to