Mathematics for Computer Science

14.9. Inclusion-Exclusion 583

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

ThenjM\EjD 4 C 2 ,jM\PjD 3 C 2 ,jE\PjD 11 C 2 , andjM\E\PjD 2.
Plugging all this into the formula gives:

jM[E[PjDjMjCjEjCjPjjM\EjjM\PjjE\Pj

CjM\E\Pj

D 60 C 200 C 40  6  5  13 C 2

D 278

14.9.3 Sequences with 42, 04, or 60

In how many permutations of the setf0;1;2;:::;9gdo either 4 and 2, 0 and 4, or
6 and 0 appear consecutively? For example, none of these pairs appears in:

.7;2;9;5;4;1;3;8;0;6/:

The 06 at the end doesn’t count; we need 60. On the other hand, both 04 and 60
appear consecutively in this permutation:

.7;2;5;6;0;4;3;8;1;9/:

LetP 42 be the set of all permutations in which 42 appears. DefineP 60 andP 04
similarly. Thus, for example, the permutation above is contained in bothP 60 and
P 04 , but notP 42. In these terms, we’re looking for the size of the setP 42 [P 04 [
P 60.