Mathematics for Computer Science

15.10. Inclusion-Exclusion 473

AndjP 42 \P 04 j D8Šas well by a similar argument. Finally, note thatjP 60 \
P 04 \P 42 jD7Šby a bijection with the set:

f6042;1;3;5;7;8;9g:

Plugging all this into the formula gives:

jP 42 [P 04 [P 60 jD9ŠC9ŠC9Š8Š8Š8ŠC7Š:

15.10.4 Union ofnSets

The size of a union ofnsets is given by the following rule.

Rule 15.10.1(Inclusion-Exclusion).

jS 1 [S 2 [


[SnjD

the sum of the sizes of the individual sets
minus the sizes of all two-way intersections
plus the sizes of all three-way intersections
minus the sizes of all four-way intersections
plus the sizes of all five-way intersections, etc.
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: