Page 581 - Discrete Mathematics and Its Applications

560 8 / Advanced Counting Techniques

The Sieve of Eratosthenes

In Section 4.3 we showed how to use the sieve of Eratosthenes to find all primes less than a
specified positive integer n. Using the principle of inclusion–exclusion, we can find the number
of primes not exceeding a specified positive integer with the same reasoning as is used in the
sieve of Eratosthenes. Recall that a composite integer is divisible by a prime not exceeding
its square root. So, to find the number of primes not exceeding 100, first note that compos-
ite integers not exceeding 100 must have a prime factor not exceeding 10. Because the only
primes not exceeding 10 are 2, 3, 5, and 7, the primes not exceeding 100 are these four primes
and those positive integers greater than 1 and not exceeding 100 that are divisible by none
of 2, 3, 5, or 7. To apply the principle of inclusion–exclusion, let P 1 be the property that an
integer is divisible by 2, let P 2 be the property that an integer is divisible by 3, let P 3 be the
property that an integer is divisible by 5, and let P 4 be the property that an integer is divisible
by 7. Thus, the number of primes not exceeding 100 is

4 + N(P P P P ).
1 2 3 4
Because there are 99 positive integers greater than 1 and not exceeding 100, the principle of
inclusion–exclusion shows that

N(P P P P ) = 99 − N(P 1 ) − N(P 2 ) − N(P 3 ) − N(P 4 )

1 2 3 4
+ N(P 1 P 2 ) + N(P 1 P 3 ) + N(P 1 P 4 ) + N(P 2 P 3 ) + N(P 2 P 4 ) + N(P 3 P 4 )
− N(P 1 P 2 P 3 ) − N(P 1 P 2 P 4 ) − N(P 1 P 3 P 4 ) − N(P 2 P 3 P 4 )
+ N(P 1 P 2 P 3 P 4 ).
The number of integers not exceeding 100 (and greater than 1) that are divisible by all the primes
in a subset of {2, 3, 5, 7} is 100/N
, where N is the product of the primes in this subset. (This
follows because any two of these primes have no common factor.) Consequently,

100 100 100 100

N(P P P P ) = 99 − − − −
1 2 3 4
2 3 5 7

100 100 100 100 100 100
+ + + + + +
2 · 3 2 · 5 2 · 7 3 · 5 3 · 7 5 · 7

100 100 100 100 100
− − − − +
2 · 3 · 5 2 · 3 · 7 2 · 5 · 7 3 · 5 · 7 2 · 3 · 5 · 7
= 99 − 50 − 33 − 20 − 14 + 16 + 10 + 7 + 6 + 4 + 2 − 3 − 2 − 1 − 0 + 0
= 21.

Hence, there are 4 + 21 = 25 primes not exceeding 100.

The Number of Onto Functions

The principle of inclusion–exclusion can also be used to determine the number of onto functions
from a set with m elements to a set with n elements. First consider Example 2.
EXAMPLE 2 How many onto functions are there from a set with six elements to a set with three elements?

Solution: Suppose that the elements in the codomain are b 1 ,b 2 , and b 3 . Let P 1 ,P 2 , and P 3 be
the properties that b 1 ,b 2 , and b 3 are not in the range of the function, respectively. Note that