Mathematics for Computer Science

15.13. A Magic Trick 505

(a)What isjSij?

(b)What is

ˇˇ

Si\Sj

ˇˇ

wherei¤j?

(c)What is

ˇˇ

Si 1 \Si 2 \


\Sik

ˇˇ

wherei 1 ;i 2 ;:::;ikare all distinct?

(d)Use the inclusion-exclusion formula to express the number of non-derangements
in terms of sizes of possible intersections of the setsS 1 ;:::;Sn.

(e)How many terms in the expression in part (d) have the form

ˇ

ˇSi 1 \Si 2 \


\Sik

ˇ

ˇ?

(f)Combine your answers to the preceding parts to prove the number of non-
derangements is:

nŠ



1

1Š

1

2Š

C

1

3Š

̇

1

nŠ



:

Conclude that the number of derangements is

nŠ



1

1

1Š

C

1

2Š

1

3Š

C


̇

1

nŠ



:

(g)Asngoes to infinity, the number of derangements approaches a constant frac-
tion of all permutations. What is that constant?Hint:

exD 1 CxC

x^2

2Š

C

x^3

3Š

C

Problem 15.32.
How many of the numbers2;:::;nare prime? The Inclusion-Exclusion Principle
offers a useful way to calculate the answer whennis large. Actually, we will use
Inclusion-Exclusion to count the number ofcomposite(nonprime) integers from 2
ton. Subtracting this fromn 1 gives the number of primes.
LetCnbe the set of composites from 2 ton, and letAmbe the set of numbers in
the rangemC1;:::;nthat are divisible bym. Notice that by definition,AmD;
formn. So

CnD

n[ 1

iD 2

Ai: (15.20)

(a)Verify that ifmjk, thenAmAk.

(b)Explain why the right hand side of (15.20) equals

[

primesppn

Ap: (15.21)