Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

110 ADVANCED COUNTING TECHNIQUES, RECURSION [CHAP. 6

(v) F 1 ∩F 2 ∩F 3 ∩F 4 has no element, that is, is empty. Hence|F 1 ∩F 2 ∩F 3 ∩F 4 |=0. By the Inclusion–

Exclusion Principle Theorem 6.3,

|S|=|F 1 C∩F 2 C∩F 3 C∩F 4 C|= 46 −C( 4 , 1 ) 36 +C( 4 , 2 ) 26 −C( 4 , 3 ) 17

= 4096 − 2916 + 384 − 1 = 795

The above result is true in general. Namely:

Theorem 6.4: Suppose|A|=mand|B|=nwherem≥n. Then the numberNof surjective (onto) functions
fromAontoBis:

N=nm−C(n, 1 )(n− 1 )m+C(n, 2 )(n− 2 )m−···+(− 1 )n−^1 C(n, n− 1 ) 1 m

Derangements

Aderangementis a permutation of objects where each object is not in its original position. For example,
453162 is not a derangement of 123456 since 3 is in its correct position, but 264531 is a derangement of 123456.
(Alternately, a permutationσ:X→Xis a derangement ifσ(i)=ifor everyi∈X={ 1 , 2 ,...,n}.)
LetDndenote the number of derangements ofnobjects. For example, 231 and 312 are the only derangements
of 123. HenceD 3 =2. The following theorem, proved in Problem 6.6, applies.

Theorem 6.5: Dn=n![ 1 − 11 !+ 21 !− 31 !+···+(− 1 )nn^1 !]

The probability (Chapter 7) that a derangement ofnobjects occurs equalsDndivided byn!, the number of
permutations of thenobjects. Thus Theorem 6.5 yields:

Corollary 6.6: Letpbe the probability of a derangement ofnobjects. Then

p= 1 −

1

1!

+

1

2!

−

1

3!

+···+(− 1 )n

1

n!

EXAMPLE 6.4 (Hat Check Problem) Supposen=5 people check in their hats at a restaurant and they are
given back their hats at random. Find the probabilitypthat no person receives his/her own hat.
This is an example of a derangement withn=5. By Corollary 6.6,

p= 1 − 1 + 1 / 2 − 1 / 6 + 1 / 24 − 1 / 120 = 44 / 120 = 11 / 30 ≈ 0. 367

Note that the signs alternate and the terms get very, very small in Corollary 6.6. Figure 6-1 gives the values
ofpfor the first few values ofn. Note that, forn>4,pis very close to the following value (wheree= 2 .718):

e−^1 = 1 − 11 !+ 21 !− 31 !+···+(− 1 )nn^1 !+···≈ 0. 368

Fig. 6-1

6.5Pigeonhole Principle Revisited

The Pigeonhole Principle (with its generalization) is stated with simple examples in Section 5.6. Here we
give examples of more sophisticated applications of this principle.