Inclusion Exclusion Principle - Algebra, CSIR-NET Mathematical Sciences | Mathematics for IIT JAM, GATE, CSIR NET, UGC NET PDF Download

 Page 1


Lecture 9
The Principle of
Inclusion/Exclusion
These notes are based on a pair of lectures originally written by (Manchester’s own)
Prof. Nige Ray.
Reading:
The Principle of Inclusion/Exclusion appears in the ?rst year module Foundations
of Pure Mathematics, but it is also a standard technique in Combinatorics and so
is discussed in many other books
1
. The Wikipedia article, which gives a version of
the proof in Section 9.2.2 below, is also a good place to start.
9.1 Introduction: a familiar example
Supposewehavesome?nite“universal”setU andtwosubsets,X
1
? U andX
2
? U.
If the subsets are disjoint then it’s easy to work out the number of elements in their
union:
X
1
\ X
2
=;) |X
1
[ X
2
| = |X
1
|+ |X
2
|.
The case where the subsets have a non-empty intersection provides the simplest in-
stanceoftheresultwe’regoingtodeveloptoday,thePrincipleofInclusion/Exclusion.
You may already know a similar result from Probability.
Lemma 9.1 (Inclusion/Exclusion for two sets). If X
1
and X
2
are ?nite sets then
|X
1
[ X
2
| = |X
1
|+ |X
2
| |X
1
\ X
2
|. (9.1)
Note that this formula, which is illustrated in Figure 9.1, works even X
1
\ X
2
=; ,
as then |X
1
\ X
2
|=0.
Proof. To prove this result, note that the sum |X
1
|+ |X
2
| counts each member of
the intersectionX
1
\ X
2
twice, once as a member ofX
1
and then again as a member
1
See, for example, Dossey, Otto, Spence, and Vanden Eynden (2006), Discrete Mathematics or,
for a short, clear account, Anderson (1974), A First Course in Combinatorial Mathematics.
Page 2


Lecture 9
The Principle of
Inclusion/Exclusion
These notes are based on a pair of lectures originally written by (Manchester’s own)
Prof. Nige Ray.
Reading:
The Principle of Inclusion/Exclusion appears in the ?rst year module Foundations
of Pure Mathematics, but it is also a standard technique in Combinatorics and so
is discussed in many other books
1
. The Wikipedia article, which gives a version of
the proof in Section 9.2.2 below, is also a good place to start.
9.1 Introduction: a familiar example
Supposewehavesome?nite“universal”setU andtwosubsets,X
1
? U andX
2
? U.
If the subsets are disjoint then it’s easy to work out the number of elements in their
union:
X
1
\ X
2
=;) |X
1
[ X
2
| = |X
1
|+ |X
2
|.
The case where the subsets have a non-empty intersection provides the simplest in-
stanceoftheresultwe’regoingtodeveloptoday,thePrincipleofInclusion/Exclusion.
You may already know a similar result from Probability.
Lemma 9.1 (Inclusion/Exclusion for two sets). If X
1
and X
2
are ?nite sets then
|X
1
[ X
2
| = |X
1
|+ |X
2
| |X
1
\ X
2
|. (9.1)
Note that this formula, which is illustrated in Figure 9.1, works even X
1
\ X
2
=; ,
as then |X
1
\ X
2
|=0.
Proof. To prove this result, note that the sum |X
1
|+ |X
2
| counts each member of
the intersectionX
1
\ X
2
twice, once as a member ofX
1
and then again as a member
1
See, for example, Dossey, Otto, Spence, and Vanden Eynden (2006), Discrete Mathematics or,
for a short, clear account, Anderson (1974), A First Course in Combinatorial Mathematics.
U
X
1
X
2
U
X
1
X
1
n X
2
X
2
Figure 9.1: In the example at left X
1
\ X
2
=; , so |X
1
[ X
2
| = |X
1
|+|X
2
|, but in the
example at right X
1
\ X
2
6=; and so |X
1
[ X
2
| = |X
1
|+|X
2
| |X
1
\ X
2
| < |X
1
|+|X
2
|.
U
X
1
\ X
2
X
1
n X
2
X
2
\ X
1
Figure 9.2: Here X
1
\X
2
and X
1
\ X
2
are shown in shades of blue, while X
2
\X
1
is
in yellow.
of X
2
. Subtracting |X
1
\ X
2
| corrects for this double-counting. Alternatively, for
those who prefer proofs that look more like calculations, begin by de?ning
X
1
\X
2
= {x2 U | x2 X
1
, butx/ 2 X
2
}.
Then, as is illustrated in Figure 9.2, X
1
=(X
1
\X
2
)[ (X
1
\ X
2
). Further, the sets
X
1
\X
2
and X
1
\ X
2
are disjoint by construction, so
|X
1
| = |X
1
\X
2
|+ |X
1
\ X
2
| or |X
1
\X
2
| = |X
1
| |X
1
\ X
2
|. (9.2)
Similarly, X
1
\X
2
and X
2
are disjoint and X
1
[ X
2
=(X
1
\X
2
)[ X
2
so
|X
1
[ X
2
| = |X
1
\X
2
|+ |X
2
|
= |X
1
| |X
1
\ X
2
|+ |X
2
|
= |X
1
|+ |X
2
| |X
1
\ X
2
|
where, in passing from the ?rst line to the second, we have used (9.2). The last line
is the result we were trying to prove, so we are ?nished.
9.2 Principle and proof
Before moving to the general case, let’s consider one more small example, this
time with three subsets X
1
, X
2
and X
3
: we can handle this case by clever use
Page 3


Lecture 9
The Principle of
Inclusion/Exclusion
These notes are based on a pair of lectures originally written by (Manchester’s own)
Prof. Nige Ray.
Reading:
The Principle of Inclusion/Exclusion appears in the ?rst year module Foundations
of Pure Mathematics, but it is also a standard technique in Combinatorics and so
is discussed in many other books
1
. The Wikipedia article, which gives a version of
the proof in Section 9.2.2 below, is also a good place to start.
9.1 Introduction: a familiar example
Supposewehavesome?nite“universal”setU andtwosubsets,X
1
? U andX
2
? U.
If the subsets are disjoint then it’s easy to work out the number of elements in their
union:
X
1
\ X
2
=;) |X
1
[ X
2
| = |X
1
|+ |X
2
|.
The case where the subsets have a non-empty intersection provides the simplest in-
stanceoftheresultwe’regoingtodeveloptoday,thePrincipleofInclusion/Exclusion.
You may already know a similar result from Probability.
Lemma 9.1 (Inclusion/Exclusion for two sets). If X
1
and X
2
are ?nite sets then
|X
1
[ X
2
| = |X
1
|+ |X
2
| |X
1
\ X
2
|. (9.1)
Note that this formula, which is illustrated in Figure 9.1, works even X
1
\ X
2
=; ,
as then |X
1
\ X
2
|=0.
Proof. To prove this result, note that the sum |X
1
|+ |X
2
| counts each member of
the intersectionX
1
\ X
2
twice, once as a member ofX
1
and then again as a member
1
See, for example, Dossey, Otto, Spence, and Vanden Eynden (2006), Discrete Mathematics or,
for a short, clear account, Anderson (1974), A First Course in Combinatorial Mathematics.
U
X
1
X
2
U
X
1
X
1
n X
2
X
2
Figure 9.1: In the example at left X
1
\ X
2
=; , so |X
1
[ X
2
| = |X
1
|+|X
2
|, but in the
example at right X
1
\ X
2
6=; and so |X
1
[ X
2
| = |X
1
|+|X
2
| |X
1
\ X
2
| < |X
1
|+|X
2
|.
U
X
1
\ X
2
X
1
n X
2
X
2
\ X
1
Figure 9.2: Here X
1
\X
2
and X
1
\ X
2
are shown in shades of blue, while X
2
\X
1
is
in yellow.
of X
2
. Subtracting |X
1
\ X
2
| corrects for this double-counting. Alternatively, for
those who prefer proofs that look more like calculations, begin by de?ning
X
1
\X
2
= {x2 U | x2 X
1
, butx/ 2 X
2
}.
Then, as is illustrated in Figure 9.2, X
1
=(X
1
\X
2
)[ (X
1
\ X
2
). Further, the sets
X
1
\X
2
and X
1
\ X
2
are disjoint by construction, so
|X
1
| = |X
1
\X
2
|+ |X
1
\ X
2
| or |X
1
\X
2
| = |X
1
| |X
1
\ X
2
|. (9.2)
Similarly, X
1
\X
2
and X
2
are disjoint and X
1
[ X
2
=(X
1
\X
2
)[ X
2
so
|X
1
[ X
2
| = |X
1
\X
2
|+ |X
2
|
= |X
1
| |X
1
\ X
2
|+ |X
2
|
= |X
1
|+ |X
2
| |X
1
\ X
2
|
where, in passing from the ?rst line to the second, we have used (9.2). The last line
is the result we were trying to prove, so we are ?nished.
9.2 Principle and proof
Before moving to the general case, let’s consider one more small example, this
time with three subsets X
1
, X
2
and X
3
: we can handle this case by clever use
U
X
1
X
2
X
1
X
2
X
3
Figure 9.3: In the diagram above all of the intersections appearing in Eqn. (9.3) are
nonempty.
of Lemma 9.1 from the previous section. If we regard (X
1
[ X
2
)asasinglesetand
X
3
as a second set, then Eqn. (9.1) says
|(X
1
[ X
2
)[ X
3
| = |(X
1
[ X
2
)|+ |X
3
| |(X
1
[ X
2
)\ X
3
|
=(|X
1
|+ |X
2
| |X
1
\ X
2
|)+ |X
3
| |(X
1
[ X
2
)\ X
3
|
= |X
1
|+ |X
2
|+ |X
3
| |X
1
\ X
2
| |(X
1
[ X
2
)\ X
3
|
Focusing on the ?nal term, we can use standard relations about unions and inter-
sections to say
(X
1
[ X
2
)\ X
3
=(X
1
\ X
3
)[ (X
2
\ X
3
).
Then, applying Eqn. (9.1) to the pair of sets (X
1
\ X
3
)and(X
2
\ X
3
), we obtain
|(X
1
[ X
2
)\ X
3
| = |(X
1
\ X
3
)[ (X
2
\ X
3
)|
= |X
1
\ X
3
|+ |X
2
\ X
3
| |(X
1
\ X
3
)\ (X
2
\ X
3
)|
= |X
1
\ X
3
|+ |X
2
\ X
3
| |X
1
\ X
2
\ X
3
|
where, in going from the second line to the third, we have used
(X
1
\ X
3
)\ (X
2
\ X
3
)= X
1
\ X
2
\ X
3
.
Finally, putting all these results together, we obtain the analogue of Eqn. (9.1)
for three subsets:
|(X
1
[ X
2
)[ X
3
| = |X
1
|+ |X
2
|+ |X
3
| |X
1
\ X
2
| |(X
1
[ X
2
)\ X
3
|
= |X
1
|+ |X
2
|+ |X
3
| |X
2
\ X
3
|
 (|X
1
\ X
3
|+ |X
2
\ X
3
| |(X
1
\ X
2
\ X
3
|)
=(|X
1
|+ |X
2
|+ |X
3
|)
 (|X
1
\ X
2
|+ |X
1
\ X
3
|+ |X
2
\ X
3
|)
+ |X
1
\ X
2
\ X
3
|. (9.3)
Figure 9.3 helps make sense of this formula and prompts the following observations:
Page 4


Lecture 9
The Principle of
Inclusion/Exclusion
These notes are based on a pair of lectures originally written by (Manchester’s own)
Prof. Nige Ray.
Reading:
The Principle of Inclusion/Exclusion appears in the ?rst year module Foundations
of Pure Mathematics, but it is also a standard technique in Combinatorics and so
is discussed in many other books
1
. The Wikipedia article, which gives a version of
the proof in Section 9.2.2 below, is also a good place to start.
9.1 Introduction: a familiar example
Supposewehavesome?nite“universal”setU andtwosubsets,X
1
? U andX
2
? U.
If the subsets are disjoint then it’s easy to work out the number of elements in their
union:
X
1
\ X
2
=;) |X
1
[ X
2
| = |X
1
|+ |X
2
|.
The case where the subsets have a non-empty intersection provides the simplest in-
stanceoftheresultwe’regoingtodeveloptoday,thePrincipleofInclusion/Exclusion.
You may already know a similar result from Probability.
Lemma 9.1 (Inclusion/Exclusion for two sets). If X
1
and X
2
are ?nite sets then
|X
1
[ X
2
| = |X
1
|+ |X
2
| |X
1
\ X
2
|. (9.1)
Note that this formula, which is illustrated in Figure 9.1, works even X
1
\ X
2
=; ,
as then |X
1
\ X
2
|=0.
Proof. To prove this result, note that the sum |X
1
|+ |X
2
| counts each member of
the intersectionX
1
\ X
2
twice, once as a member ofX
1
and then again as a member
1
See, for example, Dossey, Otto, Spence, and Vanden Eynden (2006), Discrete Mathematics or,
for a short, clear account, Anderson (1974), A First Course in Combinatorial Mathematics.
U
X
1
X
2
U
X
1
X
1
n X
2
X
2
Figure 9.1: In the example at left X
1
\ X
2
=; , so |X
1
[ X
2
| = |X
1
|+|X
2
|, but in the
example at right X
1
\ X
2
6=; and so |X
1
[ X
2
| = |X
1
|+|X
2
| |X
1
\ X
2
| < |X
1
|+|X
2
|.
U
X
1
\ X
2
X
1
n X
2
X
2
\ X
1
Figure 9.2: Here X
1
\X
2
and X
1
\ X
2
are shown in shades of blue, while X
2
\X
1
is
in yellow.
of X
2
. Subtracting |X
1
\ X
2
| corrects for this double-counting. Alternatively, for
those who prefer proofs that look more like calculations, begin by de?ning
X
1
\X
2
= {x2 U | x2 X
1
, butx/ 2 X
2
}.
Then, as is illustrated in Figure 9.2, X
1
=(X
1
\X
2
)[ (X
1
\ X
2
). Further, the sets
X
1
\X
2
and X
1
\ X
2
are disjoint by construction, so
|X
1
| = |X
1
\X
2
|+ |X
1
\ X
2
| or |X
1
\X
2
| = |X
1
| |X
1
\ X
2
|. (9.2)
Similarly, X
1
\X
2
and X
2
are disjoint and X
1
[ X
2
=(X
1
\X
2
)[ X
2
so
|X
1
[ X
2
| = |X
1
\X
2
|+ |X
2
|
= |X
1
| |X
1
\ X
2
|+ |X
2
|
= |X
1
|+ |X
2
| |X
1
\ X
2
|
where, in passing from the ?rst line to the second, we have used (9.2). The last line
is the result we were trying to prove, so we are ?nished.
9.2 Principle and proof
Before moving to the general case, let’s consider one more small example, this
time with three subsets X
1
, X
2
and X
3
: we can handle this case by clever use
U
X
1
X
2
X
1
X
2
X
3
Figure 9.3: In the diagram above all of the intersections appearing in Eqn. (9.3) are
nonempty.
of Lemma 9.1 from the previous section. If we regard (X
1
[ X
2
)asasinglesetand
X
3
as a second set, then Eqn. (9.1) says
|(X
1
[ X
2
)[ X
3
| = |(X
1
[ X
2
)|+ |X
3
| |(X
1
[ X
2
)\ X
3
|
=(|X
1
|+ |X
2
| |X
1
\ X
2
|)+ |X
3
| |(X
1
[ X
2
)\ X
3
|
= |X
1
|+ |X
2
|+ |X
3
| |X
1
\ X
2
| |(X
1
[ X
2
)\ X
3
|
Focusing on the ?nal term, we can use standard relations about unions and inter-
sections to say
(X
1
[ X
2
)\ X
3
=(X
1
\ X
3
)[ (X
2
\ X
3
).
Then, applying Eqn. (9.1) to the pair of sets (X
1
\ X
3
)and(X
2
\ X
3
), we obtain
|(X
1
[ X
2
)\ X
3
| = |(X
1
\ X
3
)[ (X
2
\ X
3
)|
= |X
1
\ X
3
|+ |X
2
\ X
3
| |(X
1
\ X
3
)\ (X
2
\ X
3
)|
= |X
1
\ X
3
|+ |X
2
\ X
3
| |X
1
\ X
2
\ X
3
|
where, in going from the second line to the third, we have used
(X
1
\ X
3
)\ (X
2
\ X
3
)= X
1
\ X
2
\ X
3
.
Finally, putting all these results together, we obtain the analogue of Eqn. (9.1)
for three subsets:
|(X
1
[ X
2
)[ X
3
| = |X
1
|+ |X
2
|+ |X
3
| |X
1
\ X
2
| |(X
1
[ X
2
)\ X
3
|
= |X
1
|+ |X
2
|+ |X
3
| |X
2
\ X
3
|
 (|X
1
\ X
3
|+ |X
2
\ X
3
| |(X
1
\ X
2
\ X
3
|)
=(|X
1
|+ |X
2
|+ |X
3
|)
 (|X
1
\ X
2
|+ |X
1
\ X
3
|+ |X
2
\ X
3
|)
+ |X
1
\ X
2
\ X
3
|. (9.3)
Figure 9.3 helps make sense of this formula and prompts the following observations:
• Elements of X
1
[ X
2
[ X
3
that belong to exactly one of the X
j
are counted
exactly once by the sum (|X
1
|+ |X
2
|+ |X
3
|) and do not contribute to any of
the terms involving intersections.
• Elements of X
1
[ X
2
[ X
3
that belong to exactly two of the X
j
are double-
countedbythesum, (|X
1
|+ |X
2
|+ |X
3
|), butthisdouble-countingiscorrected
by the term involving two-fold intersections.
• Finally, elements of X
1
[ X
2
[ X
3
that belong to all three of the sets are
triple-counted by the initial sum (|X
1
|+ |X
2
|+ |X
3
|). This triple-counting is
then completely cancelled by the term involving two-fold intersections. Then,
?nally, this cancellation is repaired by the ?nal term, which counts each such
element once.
9.2.1 The general case
The Principle of Inclusion/Exclusion generalises the results in Eqns. (9.1) and (9.3)
to unions of arbitrarily many subsets.
Theorem 9.2 (The Principle of Inclusion/Exclusion). If U is a ?nite set and
{X
j
}
n
j=1
is a collection of n subsets, then





n
[
j=1
X
j





= |X
1
[ ···[ X
n
|
= |X
1
|+···+ |X
n
|
 |X
1
\ X
2
| ··· |X
n 1
\ X
n
|
+|X
1
\ X
2
\ X
3
|+···+ |X
n 2
\ X
n 1
\ X
n
|
.
.
.
+( 1)
m 1
X
1? i
1
? ···? im? n
|X
i
1
\ ···\ X
im
|
.
.
.
+( 1)
n 1
|X
1
\ ···\ X
n
| (9.4)
or, more concisely,
|X
1
[ ···[ X
n
| =
X
I? {1,...,n},I6=; ( 1)
|I| 1





\
i2 I
X
i





(9.5)
One can prove this in at least two ways:
• by induction, with a calculation that is essentially the same as the one used
to obtain then=3case—Eqn.(9.3)—fromthe n=2one—Eqn.(9.1);
• by showing that eachx2 X
1
[ ···[ X
n
contributes exactly one to the sum on
the right hand side of Eqn. (9.5).
The ?rst approach is straightforward, if a bit tedious, and so is left as an exercise,
but the second is more interesting and so it’s the one we’ll study here.
Page 5


Lecture 9
The Principle of
Inclusion/Exclusion
These notes are based on a pair of lectures originally written by (Manchester’s own)
Prof. Nige Ray.
Reading:
The Principle of Inclusion/Exclusion appears in the ?rst year module Foundations
of Pure Mathematics, but it is also a standard technique in Combinatorics and so
is discussed in many other books
1
. The Wikipedia article, which gives a version of
the proof in Section 9.2.2 below, is also a good place to start.
9.1 Introduction: a familiar example
Supposewehavesome?nite“universal”setU andtwosubsets,X
1
? U andX
2
? U.
If the subsets are disjoint then it’s easy to work out the number of elements in their
union:
X
1
\ X
2
=;) |X
1
[ X
2
| = |X
1
|+ |X
2
|.
The case where the subsets have a non-empty intersection provides the simplest in-
stanceoftheresultwe’regoingtodeveloptoday,thePrincipleofInclusion/Exclusion.
You may already know a similar result from Probability.
Lemma 9.1 (Inclusion/Exclusion for two sets). If X
1
and X
2
are ?nite sets then
|X
1
[ X
2
| = |X
1
|+ |X
2
| |X
1
\ X
2
|. (9.1)
Note that this formula, which is illustrated in Figure 9.1, works even X
1
\ X
2
=; ,
as then |X
1
\ X
2
|=0.
Proof. To prove this result, note that the sum |X
1
|+ |X
2
| counts each member of
the intersectionX
1
\ X
2
twice, once as a member ofX
1
and then again as a member
1
See, for example, Dossey, Otto, Spence, and Vanden Eynden (2006), Discrete Mathematics or,
for a short, clear account, Anderson (1974), A First Course in Combinatorial Mathematics.
U
X
1
X
2
U
X
1
X
1
n X
2
X
2
Figure 9.1: In the example at left X
1
\ X
2
=; , so |X
1
[ X
2
| = |X
1
|+|X
2
|, but in the
example at right X
1
\ X
2
6=; and so |X
1
[ X
2
| = |X
1
|+|X
2
| |X
1
\ X
2
| < |X
1
|+|X
2
|.
U
X
1
\ X
2
X
1
n X
2
X
2
\ X
1
Figure 9.2: Here X
1
\X
2
and X
1
\ X
2
are shown in shades of blue, while X
2
\X
1
is
in yellow.
of X
2
. Subtracting |X
1
\ X
2
| corrects for this double-counting. Alternatively, for
those who prefer proofs that look more like calculations, begin by de?ning
X
1
\X
2
= {x2 U | x2 X
1
, butx/ 2 X
2
}.
Then, as is illustrated in Figure 9.2, X
1
=(X
1
\X
2
)[ (X
1
\ X
2
). Further, the sets
X
1
\X
2
and X
1
\ X
2
are disjoint by construction, so
|X
1
| = |X
1
\X
2
|+ |X
1
\ X
2
| or |X
1
\X
2
| = |X
1
| |X
1
\ X
2
|. (9.2)
Similarly, X
1
\X
2
and X
2
are disjoint and X
1
[ X
2
=(X
1
\X
2
)[ X
2
so
|X
1
[ X
2
| = |X
1
\X
2
|+ |X
2
|
= |X
1
| |X
1
\ X
2
|+ |X
2
|
= |X
1
|+ |X
2
| |X
1
\ X
2
|
where, in passing from the ?rst line to the second, we have used (9.2). The last line
is the result we were trying to prove, so we are ?nished.
9.2 Principle and proof
Before moving to the general case, let’s consider one more small example, this
time with three subsets X
1
, X
2
and X
3
: we can handle this case by clever use
U
X
1
X
2
X
1
X
2
X
3
Figure 9.3: In the diagram above all of the intersections appearing in Eqn. (9.3) are
nonempty.
of Lemma 9.1 from the previous section. If we regard (X
1
[ X
2
)asasinglesetand
X
3
as a second set, then Eqn. (9.1) says
|(X
1
[ X
2
)[ X
3
| = |(X
1
[ X
2
)|+ |X
3
| |(X
1
[ X
2
)\ X
3
|
=(|X
1
|+ |X
2
| |X
1
\ X
2
|)+ |X
3
| |(X
1
[ X
2
)\ X
3
|
= |X
1
|+ |X
2
|+ |X
3
| |X
1
\ X
2
| |(X
1
[ X
2
)\ X
3
|
Focusing on the ?nal term, we can use standard relations about unions and inter-
sections to say
(X
1
[ X
2
)\ X
3
=(X
1
\ X
3
)[ (X
2
\ X
3
).
Then, applying Eqn. (9.1) to the pair of sets (X
1
\ X
3
)and(X
2
\ X
3
), we obtain
|(X
1
[ X
2
)\ X
3
| = |(X
1
\ X
3
)[ (X
2
\ X
3
)|
= |X
1
\ X
3
|+ |X
2
\ X
3
| |(X
1
\ X
3
)\ (X
2
\ X
3
)|
= |X
1
\ X
3
|+ |X
2
\ X
3
| |X
1
\ X
2
\ X
3
|
where, in going from the second line to the third, we have used
(X
1
\ X
3
)\ (X
2
\ X
3
)= X
1
\ X
2
\ X
3
.
Finally, putting all these results together, we obtain the analogue of Eqn. (9.1)
for three subsets:
|(X
1
[ X
2
)[ X
3
| = |X
1
|+ |X
2
|+ |X
3
| |X
1
\ X
2
| |(X
1
[ X
2
)\ X
3
|
= |X
1
|+ |X
2
|+ |X
3
| |X
2
\ X
3
|
 (|X
1
\ X
3
|+ |X
2
\ X
3
| |(X
1
\ X
2
\ X
3
|)
=(|X
1
|+ |X
2
|+ |X
3
|)
 (|X
1
\ X
2
|+ |X
1
\ X
3
|+ |X
2
\ X
3
|)
+ |X
1
\ X
2
\ X
3
|. (9.3)
Figure 9.3 helps make sense of this formula and prompts the following observations:
• Elements of X
1
[ X
2
[ X
3
that belong to exactly one of the X
j
are counted
exactly once by the sum (|X
1
|+ |X
2
|+ |X
3
|) and do not contribute to any of
the terms involving intersections.
• Elements of X
1
[ X
2
[ X
3
that belong to exactly two of the X
j
are double-
countedbythesum, (|X
1
|+ |X
2
|+ |X
3
|), butthisdouble-countingiscorrected
by the term involving two-fold intersections.
• Finally, elements of X
1
[ X
2
[ X
3
that belong to all three of the sets are
triple-counted by the initial sum (|X
1
|+ |X
2
|+ |X
3
|). This triple-counting is
then completely cancelled by the term involving two-fold intersections. Then,
?nally, this cancellation is repaired by the ?nal term, which counts each such
element once.
9.2.1 The general case
The Principle of Inclusion/Exclusion generalises the results in Eqns. (9.1) and (9.3)
to unions of arbitrarily many subsets.
Theorem 9.2 (The Principle of Inclusion/Exclusion). If U is a ?nite set and
{X
j
}
n
j=1
is a collection of n subsets, then





n
[
j=1
X
j





= |X
1
[ ···[ X
n
|
= |X
1
|+···+ |X
n
|
 |X
1
\ X
2
| ··· |X
n 1
\ X
n
|
+|X
1
\ X
2
\ X
3
|+···+ |X
n 2
\ X
n 1
\ X
n
|
.
.
.
+( 1)
m 1
X
1? i
1
? ···? im? n
|X
i
1
\ ···\ X
im
|
.
.
.
+( 1)
n 1
|X
1
\ ···\ X
n
| (9.4)
or, more concisely,
|X
1
[ ···[ X
n
| =
X
I? {1,...,n},I6=; ( 1)
|I| 1





\
i2 I
X
i





(9.5)
One can prove this in at least two ways:
• by induction, with a calculation that is essentially the same as the one used
to obtain then=3case—Eqn.(9.3)—fromthe n=2one—Eqn.(9.1);
• by showing that eachx2 X
1
[ ···[ X
n
contributes exactly one to the sum on
the right hand side of Eqn. (9.5).
The ?rst approach is straightforward, if a bit tedious, and so is left as an exercise,
but the second is more interesting and so it’s the one we’ll study here.
9.2.2 Proof
The key idea is to think of the the elements of X
1
[ ···[ X
n
individually and
ask what each one contributes to the sum in Eqn. (9.5). Suppose that an element
x 2 X
1
[ ···[ X
n
belongs to exactly ` of the subsets, with 1 ? ` ? n: we will
prove that x makes a net contribution of 1. For the sake of concreteness, we’ll say
x2 X
i
1
,...,X
i
`
where i
1
,...,i
`
are distinct elements of {1,...,n}.
• As we’ve assumed that x belongs to exactly ` of the subsets X
j
, it contributes
atotalof ` to the ?rst row, |X
1
|+···+ |X
n
|, of the long sum in Eqn. (9.4).
• Further, x contributes a total of 
`
2

to the sum in the row involving two-way
intersections
 |X
1
\ X
2
| ··· |X
n 1
\ X
n
|.
To see this, note that if x2 X
j
\ X
k
then both j and k must be members of
the set {i
1
,...,i
`
}.
• Similar arguments show that if k? `, then x contributes a total of
( 1)
k 1
?
`
k
?
=( 1)
k 1
?
`!
k!(` k)!
?
to the sum in the row of Eqn. (9.4) that involves k-fold intersections.
• Finally, fork> ` there are no k-fold intersections that contain x and so x
makes a contribution of zero to the corresponding rows in Eqn. (9.4).
Putting these observations together we see that x make a net contribution of
` ?
`
2
?
+
?
`
3
?
 ... +( 1)
` 1
?
`
`
?
(9.6)
This sum can be made to look more familiar by considering the following application
of the Binomial Theorem:
0= (1 1)
`
=
`
X
j=0
( 1)
j
(1)
` j
?
`
j
?
=1 `+
?
`
2
?
 ?
`
3
?
+ ... +( 1)
`
?
`
`
?
.
Thus
0= 1 ?
` ?
`
2
?
+
?
`
3
?
 ... +( 1)
` 1
?
`
`
?
or
` ?
`
2
?
+
?
`
3
?
 ... +( 1)
` 1
?
`
`
?
=1.
The left hand side here is the same as the sum in Eqn. (9.6) and so we’ve established
that any x which belongs to exactly ` of the subsets X
j
makes a net contribution of 1
to the sum on the right hand side of Eqn. (9.5). And as every x2 X
1
[ ···[ X
n
must
belongtoatleastoneoftheX
j
, thisestablishesthePrincipleofInclusion/Exclusion.