Alvin's database of friends contains n entries, but due to

QUESTION:

Alvin's database of friends contains n entries, but due to a software glitch, the addresses correspond to the names in a totally random fashion. Alvin writes a holiday card to each of his friends and sends it to the (software-corrupted) address. What is the probability that at least one of his friends will get the correct card? Hint: Use the inclusion-exclusion formula. Solution. Let Ak be the event that the kth card is sent to the correct address. We have for any k, j, i, etc., and P(Ak) = .!. = (n - I)! , n n! 1 1 (n - 2) ' P(Ak n Aj) = P(Ak)P(AJ I Ak) = - . -- = , ' . n n - 1 n. 1 1 1 (n - 3)! P(Ak n A) n Ai) = - . --. -- = n n - I' 1 n -2 n. Applying the inclusion-exclusion formula, P (Uk=IAk) = L P(Ai) - L P(Ail n Ai2 ) iESI (i1 ,i2)es2 + we obtain the desired probability P(Uk=I Ak) = ( n ) (n - I)! _ ( n) (n - 2)! + ( n ) (n - 3)! _ ... + (-lr-l 1 n! 2 n! 3 n! n! = 1 - + -"'+(-lr-l 2! 3! n! ' When n is large, this probability can be approximated by 1 - e-l.