Mathematics for Computer Science

Chapter 14 Cardinality Rules582

departments? LetMbe the set of math majors,Ebe the set of EECS majors, and
Pbe the set of physics majors. In these terms, we’re asking forjM[E[Pj.
The Sum Rule says that ifM,E, andPare disjoint, then the sum of their sizes
is
jM[E[PjDjMjCjEjCjPj:

However, the setsM,E, andP mightnotbe disjoint. For example, there might
be a student majoring in both math and physics. Such a student would be counted
twice on the right side of this equation, once as an element ofMand once as an
element ofP. Worse, there might be a triple-major^5 countedthreetimes on the
right side!
Our most-complicated counting rule determines the size of a union of sets that
are not necessarily disjoint. Before we state the rule, let’s build some intuition by
considering some easier special cases: unions of just two or three sets.

14.9.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 jjS 1 \S 2 j (14.5)

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 cor-
rected by the final term.

14.9.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 jjS 1 \S 3 jjS 2 \S 3 j

CjS 1 \S 2 \S 3 j:

(^5)... though not at MIT anymore.