Mathematics for Computer Science

Chapter 15 Cardinality Rules470

For example, the hand above is described by the sequence:

.7;K;A;2;};3/$f 7 }; K|; A~; 2; 3}g:

Are there other sequences that correspond to the same hand? There is one more!

We could equally well regard either the 3 }or the 7 }as the extra card, so this

is actually a 2-to-1 mapping. Here are the two sequences corresponding to the

example hand:

.7;K;A;2;};3/ &

f 7 }; K|; A~; 2; 3}g

.3;K;A;2;};7/ %

Therefore, the number of hands with every suit is:

134 
 4 
 12

2

:

15.10 Inclusion-Exclusion

How big is a union of sets? For example, suppose there are 60 math majors, 200

EECS majors, and 40 physics majors. How many students are there in these three

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^4 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.

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