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/ Apq?
(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.