Mathematics for Computer Science

Chapter 14 Cardinality Rules584

First, we must determine the sizes of the individual sets, such asP 60. We can use
a trick: group the 6 and 0 together as a single symbol. Then there is an immediate
bijection between permutations off0;1;2;:::9gcontaining 6 and 0 consecutively
and permutations of:
f60;1;2;3;4;5;7;8;9g:

For example, the following two sequences correspond:

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

There are9Špermutations of the set containing 60, sojP 60 j D9Šby the Bijection
Rule. Similarly,jP 04 jDjP 42 jD9Šas well.
Next, we must determine the sizes of the two-way intersections, such asP 42 \
P 60. Using the grouping trick again, there is a bijection with permutations of the
set:
f42;60;1;3;5;7;8;9g:

Thus,jP 42 \P 60 jD8Š. Similarly,jP 60 \P 04 jD8Šby a bijection with the set:

f604;1;2;3;5;7;8;9g:

AndjP 42 \P 04 j D8Šas well by a similar argument. Finally, note thatjP 60 \
P 04 \P 42 jD7Šby a bijection with the set:

f6042;1;3;5;7;8;9g:

Plugging all this into the formula gives:

jP 42 [P 04 [P 60 jD9ŠC9ŠC9Š8Š8Š8ŠC7Š:

14.9.4 Union ofnSets

The size of a union ofnsets is given by the following rule.

Rule 14.9.1(Inclusion-Exclusion).

jS 1 [S 2 [


[SnjD

the sum of the sizes of the individual sets

minus the sizes of all two-way intersections

plus the sizes of all three-way intersections

minus the sizes of all four-way intersections

plus the sizes of all five-way intersections, etc.