Page 585 - Discrete Mathematics and Its Applications

564 8 / Advanced Counting Techniques

TABLE 1 The Probability of a Derangement.
n 2 3 4 5 6 7
D n /n! 0.50000 0.33333 0.37500 0.36667 0.36806 0.36786

It is now simple to find D n for a given positive integer n. For instance, using Theorem 2, it
follows that

1 1 1 1 1

D 3 = 3! 1 − + − = 6 1 − 1 + − = 2,
1! 2! 3! 2 6
as we have previously remarked.
The solution of the problem in Example 4 can now be given.

Solution: The probability that no one receives the correct hat is D n /n!. By Theorem 2, this
probability is

D n 1 1 n 1
= 1 − + − ··· + (−1) .
n! 1! 2! n!
The values of this probability for 2 ≤ n ≤ 7 are displayed in Table 1.
Using methods from calculus it can be shown that

1 1 1
e −1 = 1 − + − ··· + (−1) n + ··· ≈ 0.368.
1! 2! n!

Because this is an alternating series with terms tending to zero, it follows that as n grows without
bound, the probability that no one receives the correct hat converges to e −1 ≈ 0.368. In fact,
this probability can be shown to be within 1/(n + 1)! of e −1 .

Exercises

1. Suppose that in a bushel of 100 apples there are 20 that 4. Find the number of solutions of the equation x 1 + x 2 +
have worms in them and 15 that have bruises. Only those x 3 + x 4 = 17, where x i , i = 1, 2, 3, 4, are nonnegative
apples with neither worms nor bruises can be sold. If there integers such that x 1 ≤ 3, x 2 ≤ 4, x 3 ≤ 5, and x 4 ≤ 8.
are 10 bruised apples that have worms in them, how many 5. Find the number of primes less than 200 using the prin-
of the 100 apples can be sold? ciple of inclusion–exclusion.
2. Of 1000 applicants for a mountain-climbing trip in the 6. An integer is called squarefree if it is not divisible by
Himalayas, 450 get altitude sickness, 622 are not in good the square of a positive integer greater than 1. Find the
enough shape, and 30 have allergies. An applicant qual- number of squarefree positive integers less than 100.
ifies if and only if this applicant does not get altitude 7. How many positive integers less than 10,000 are not the
sickness, is in good shape, and does not have allergies. If second or higher power of an integer?
there are 111 applicants who get altitude sickness and are
not in good enough shape, 14 who get altitude sickness 8. How many onto functions are there from a set with seven
and have allergies, 18 who are not in good enough shape elements to one with five elements?
and have allergies, and 9 who get altitude sickness, are 9. How many ways are there to distribute six different toys
not in good enough shape, and have allergies, how many to three different children such that each child gets at least
applicants qualify? one toy?
3. How many solutions does the equation x 1 + x 2 + x 3 = 10. In how many ways can eight distinct balls be distributed
13 have where x 1 , x 2 , and x 3 are nonnegative integers less into three distinct urns if each urn must contain at least
than 6? one ball?