Problem #74 HARD
The Forgetful Professor
Google Netflix Probability Derangements
Problem Statement
A professor writes n letters and n envelopes. He seals each letter into an envelope completely at random — each letter equally likely to go into any envelope. What is the probability that no letter ends up in its correct envelope? This event is called a derangement. Find the exact probability for n=4 and determine what value this probability approaches as n becomes very large.
Answer & Quick Explanation
Think you've got it? Click below to check your answer.
For n=4: D(4) = 9 derangements, probability = 9/24 = 3/8 = 0.375. As n→∞: probability → 1/e ≈ 0.36788. Formula: P(derangement) = Σ (-1)^k/k! for k=0 to n = 1 - 1 + 1/2! - 1/3! + ... which converges to e^(-1).
Detailed Editorial Solution
Want to see the step-by-step breakdown? Click below to reveal the editorial.
Use inclusion-exclusion to count derangements. Let A_i be the event that letter i is in envelope i. We want P(no A_i occurs). By inclusion-exclusion: D(n) = n! × (1 - 1/1! + 1/2! - 1/3! + ... + (-1)^n/n!).
Step 1: Total permutations of n letters: n! For n=4: 4! = 24.
Step 2: Inclusion-exclusion formula: D(n) = n!(1 - 1 + 1/2! - 1/3! + 1/4! - ... ± 1/n!).
Step 3: For n=4: D(4) = 24(1 - 1 + 1/2 - 1/6 + 1/24) = 24(0 + 0.5 - 0.1667 + 0.0417) = 24 × 0.375 = 9.
Step 4: Verify by listing: with 4 items, derangements of (1,2,3,4) are permutations where position i ≠ i. Enumerate: (2,1,4,3), (2,3,4,1), (2,4,1,3), (3,1,4,2), (3,4,1,2), (3,4,2,1), (4,1,2,3), (4,3,1,2), (4,3,2,1). Count = 9.
Step 5: Probability for n=4: D(4)/4! = 9/24 = 3/8 = 0.375.
Step 6: As n→∞: the series 1 - 1 + 1/2! - 1/3! + 1/4! - ... is the Taylor expansion of e^(-1). So P(derangement) → 1/e ≈ 0.36788. Already for n=4 the probability (0.375) is within 2% of the limit.
Key Insight:
The derangement probability converges to 1/e with startling speed. By n=10, the probability is already accurate to 8 decimal places. This means: for any reasonably large n, roughly 36.8% of all random permutations are derangements. The appearance of e here — through the Taylor series — is a deep connection between combinatorics and analysis.