Mathematics for Computer Science

14.9. Inclusion-Exclusion 585

The formulas for unions of two and three sets are special cases of this general
rule.
This way of expressing Inclusion-Exclusion is easy to understand and nearly
as precise as expressing it in mathematical symbols, but we’ll need the symbolic
version below, so let’s work on deciphering it now.
We already have a concise notation for the sum of sizes of the individual sets,
namely,
Xn

iD 1

jSij:

A “two-way intersection” is a set of the formSi\Sjfori¤j. We regardSj\Si
as the same two-way intersection asSi\Sj, so we can assume thati < j. Now
we can express the sum of the sizes of the two-way intersections as
X

1 i<jn

jSi\Sjj:

Similarly, the sum of the sizes of the three-way intersections is
X

1 i<j<kn

jSi\Sj\Skj:

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: