15.10. Inclusion-Exclusion 471
15.10.1 Union of Two Sets
For two sets,S 1 andS 2 , theInclusion-Exclusion Ruleis that the size of their union
is:
jS 1 [S 2 jDjS 1 jCjS 2 j jS 1 \S 2 j (15.2)
Intuitively, each element ofS 1 is accounted for in the first term, and each element
ofS 2 is accounted for in the second term. Elements inbothS 1 andS 2 are counted
twice—once in the first term and once in the second. This double-counting is
corrected by the final term.
15.10.2 Union of Three Sets
So how many students are there in the math, EECS, and physics departments? In
other words, what isjM[E[Pjif:
jMjD 60
jEjD 200
jPjD40:The size of a union of three sets is given by a more complicated Inclusion-Exclusion
formula:
jS 1 [S 2 [S 3 jDjS 1 jCjS 2 jCjS 3 j
jS 1 \S 2 j jS 1 \S 3 j jS 2 \S 3 j
CjS 1 \S 2 \S 3 j:Remarkably, the expression on the right accounts for each element in the union of
S 1 ,S 2 , andS 3 exactly once. For example, suppose thatxis an element of all three
sets. Thenxis counted three times (by thejS 1 j,jS 2 j, andjS 3 jterms), subtracted
off three times (by thejS 1 \S 2 j,jS 1 \S 3 j, andjS 2 \S 3 jterms), and then counted
once more (by thejS 1 \S 2 \S 3 jterm). The net effect is thatxis counted just
once.
Ifxis in two sets (say,S 1 andS 2 ), thenxis counted twice (by thejS 1 jand
jS 2 jterms) and subtracted once (by thejS 1 \S 2 jterm). In this case,xdoes not
contribute to any of the other terms, sincex...S 3.
So we can’t answer the original question without knowing the sizes of the various
intersections. Let’s suppose that there are:
4 math - EECS double majors
3 math - physics double majors
11 EECS - physics double majors
2 triple majors