Mathematics for Computer Science

Chapter 15 Cardinality Rules472

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\PjCjM\E\Pj

D 60 C 200 C 40  6  5  13 C 2

D 278

15.10.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.
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: