6.3 THE PRINCIPLE OF INCLUSION-EXCLUSION 209Visualize each set as a rubber disk. The cardinality of the union of the sets corre
sponds to the "map area" of the entire shaded region. However, the shading is in three
intensities. The lightest shading corresponds to a single thickness of rubber, the in
termediate shading means double thickness, and the darkest shading indicates triple
thickness. The map area that we desire is just the single-thickness area. If we merely
add up the areas of the three disks, we have "overcounted"; the light area is OK but the
medium-dark area has been counted twice and the darkest shading area was counted
three times. To rectify this, we subtract the areas of the intersections A n B, A n C, B n C.
But now we have undercounted the darkest area A nB nC -it was originally counted
three times, but now has been subtracted three times. So we add it back, and we are
done. It makes sense that in the general case, we would alternate between adding and
subtracting the different thicknesses.
This argument is attractive, but hard to generalize rigorously to n sets. Let us
attempt a rigorous proof of PIE, one that illustrates a nice counting idea and useful
notation. Let our sets be A l ,A 2 ,' .. ,An and let Sk denote the sum of the cardinalities of
all possible intersections of k of these sets. For example,
and
SI =IAII+IA 21 +"'+IAnl= � IAil
1 ::;1::;1 1S 2 = IAI nA 21 + IAI nA 31 + ... + IAn- 1 nA 1 I 1 = � IAinAjl·
(^1) ::;I<j::;n
Notice the subscript notation. (Take some time to study it carefully, perhaps by writing
out several examples.) The condition I ::; i < j ::; n gives us all G) possible combi
nations of two different indices, with no repeats. For example, IA 3 n A 71 appears just
once in the sum, since IA 7 n A 31 is not allowed. In general,
Sk= � IAi\n Ai 2 n···nAhl·
(^1) ::;i\ <i 2 <··-<h ::;n
With this notation, PIE becomes the statement
IA 1 U A 2 U ... U An I = S 1 - S 2 + S 3 - ... + ( -I )
(^11) - (^1) SII' (4)
To prove this, let x E Al U A 2 U ... U All be an arbitrary element of the union of the
n sets. This element x is counted exactly once by the left-hand side of (4), since the
left-hand side means "the number of elements in the union of the n sets." Thus, if we
can show that the right-hand side of (4) also counts the element x exactly once, we will
be done.^5
Let r be the number of sets that x is a member of. For example, if x E A 3 and no
other set, then r = 1. Certainly, r can range between I and n, inclusive. Let us see how
many times each Sk counts the element x. When S 1 is computed, each element in each
set Ai is counted. Thus the element x is counted exactly r times, once for each set it is
a member of. To compute S 2 , we count the elements in each set of the form Ai nAj,
i ::; j. The only sets that are relevant to us are the r sets that x is a member of. There
(^5) Notice the new counting idea: to see if a combinatorial identity is true, examine how each side of the equation
counts a representative element.