Page 583 - Discrete Mathematics and Its Applications

562 8 / Advanced Counting Techniques

onto function from the set of jobs to the set of employees. Hence, by Theorem 1 it follows that
there are

5
5
5
5
4 − C(4, 1)3 + C(4, 2)2 − C(4, 3)1 = 1024 − 972 + 192 − 4 = 240
ways to assign the jobs so that each employee is assigned at least one job. ▲

Derangements

The principle of inclusion–exclusion will be used to count the permutations of n objects that
leave no objects in their original positions. Consider Example 4.

EXAMPLE 4 The Hatcheck Problem A new employee checks the hats of n people at a restaurant, forgetting
to put claim check numbers on the hats. When customers return for their hats, the checker gives
them back hats chosen at random from the remaining hats. What is the probability that no one
receives the correct hat? ▲

Remark: The answer is the number of ways the hats can be arranged so that there is no hat in
its original position divided by n!, the number of permutations of n hats. We will return to this
example after we find the number of permutations of n objects that leave no objects in their
original position.

A derangement is a permutation of objects that leaves no object in its original position. To
solve the problem posed in Example 4 we will need to determine the number of derangements
of a set of n objects.
EXAMPLE 5 The permutation 21453 is a derangement of 12345 because no number is left in its original
position. However, 21543 is not a derangement of 12345, because this permutation leaves 4
fixed. ▲
Let D n denote the number of derangements of n objects. For instance, D 3 = 2, because the
derangements of 123 are 231 and 312. We will evaluate D n , for all positive integers n, using the
principle of inclusion–exclusion.

THEOREM 2 The number of derangements of a set with n elements is

1 1 1 1
D n = n! 1 − + − + ··· + (−1) n .
1! 2! 3! n!

Proof: Let a permutation have property P i if it fixes element i. The number of derangements
is the number of permutations having none of the properties P i for i = 1, 2,...,n. This means
that

D n = N(P P ...P ).
n
1 2
Using the principle of inclusion–exclusion, it follows that
n
D n = N − N(P i ) + N(P i P j ) − N(P i P j P k ) + ··· + (−1) N(P 1 P 2 ...P n ),
i i<j i<j<k