Mathematics for Computer Science

14.11. References 617

(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 14.54.
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: (14.23)

(a)Verify that ifmjk, thenAmAk.

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

[

primesppn

Ap: (14.24)

(c)Explain whyjAmjDbn=mc 1 form 2.

(d)Consider any two relatively prime numbersp;qn. What is the one number
in.Ap\Aq/Ap
q?

(e)LetPbe a finite set of at least two primes. Give a simple formula for

ˇˇ

ˇˇ

ˇˇ

\

p 2 P

Ap

ˇˇ

ˇˇ

ˇˇ:

(f)Use the Inclusion-Exclusion principle to obtain a formula forjC 150 jin terms
the sizes of intersections among the setsA 2 ;A 3 ;A 5 ;A 7 ;A 11. (Omit the intersec-
tions that are empty; for example, any intersection of more than three of these sets
must be empty.)

(g)Use this formula to find the number of primes up to 150.