Derangements: The "Nothing in its Right Place" Problem
Master the derangement formula and its applications to letter-in-envelope problems with step-by-step JEE approaches.
What are Derangements?
A derangement is a permutation of elements where no element appears in its original position. In combinatorics, it's often called the "nothing in its right place" problem.
Derangement Formula
The number of derangements of n distinct objects is:
$$!n = n! \times \sum_{k=0}^{n} \frac{(-1)^k}{k!}$$
Also written as: $D_n = n! \left(1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \cdots + \frac{(-1)^n}{n!}\right)$
Common Derangement Values:
Problem 1: Classic Letter-in-Envelope
4 letters are placed into 4 envelopes at random. What is the probability that no letter is in its correct envelope?
Solution Approach:
Step 1: Total ways to arrange 4 letters in 4 envelopes = $4! = 24$
Step 2: Number of derangements $!4 = 9$ (from formula)
Step 3: Probability = $\frac{\text{Derangements}}{\text{Total arrangements}} = \frac{9}{24} = \frac{3}{8}$
Problem 2: Partial Derangement
5 students submit their assignments randomly. What is the probability that exactly 2 students get their own assignments back?
Solution Approach:
Step 1: Choose which 2 students get their own assignments: $\binom{5}{2} = 10$ ways
Step 2: The remaining 3 assignments must all go to wrong students: $!3 = 2$
Step 3: Total favorable = $10 \times 2 = 20$
Step 4: Total arrangements = $5! = 120$
Step 5: Probability = $\frac{20}{120} = \frac{1}{6}$
Problem 3: Hat-Check Problem
At a party, n people check their hats. The hats are returned randomly. Show that as n → ∞, the probability that no one gets their own hat approaches $\frac{1}{e}$.
Solution Approach:
Step 1: Probability = $\frac{!n}{n!} = \sum_{k=0}^{n} \frac{(-1)^k}{k!}$
Step 2: As n → ∞, this becomes the Taylor series for $e^{-1}$
Step 3: $\lim_{n \to \infty} \sum_{k=0}^{n} \frac{(-1)^k}{k!} = e^{-1} = \frac{1}{e}$
Step 4: Therefore, the probability approaches $\frac{1}{e} \approx 0.3679$
🧠 Understanding the Derangement Formula
The formula $!n = n! \times \sum_{k=0}^{n} \frac{(-1)^k}{k!}$ comes from the Inclusion-Exclusion Principle:
Step 1: Total permutations: $n!$
Step 2: Subtract permutations with at least 1 fixed point: $\binom{n}{1}(n-1)!$
Step 3: Add back permutations with at least 2 fixed points: $\binom{n}{2}(n-2)!$
Step 4: Continue alternating: $!n = n! - \binom{n}{1}(n-1)! + \binom{n}{2}(n-2)! - \cdots + (-1)^n\binom{n}{n}0!$
Step 5: Simplify: $!n = n!\left(1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \cdots + \frac{(-1)^n}{n!}\right)$
Problems 4-6 Available in Full Version
Includes 3 more advanced derangement problems with recursive formula applications
📝 Quick Self-Test
Try these derangement problems to test your understanding:
1. 6 people randomly take seats. Probability that exactly 3 get their original seats?
2. If $!5 = 44$ and $!6 = 265$, find $!7$ using the recursive formula
3. 8 books are arranged randomly. Expected number of books in correct position?
🚀 Quick Solving Strategies
For Derangements:
- Memorize $!1$ to $!6$ values
- Use recursive formula: $!n = (n-1)[!(n-1) + !(n-2)]$
- For "exactly k fixed" problems: $\binom{n}{k} \times !(n-k)$
- As n grows large, probability → $1/e$
Common Applications:
- Letter-in-envelope problems
- Hat-check problems
- Secret Santa assignments
- Exam paper distribution
Ready to Master All Derangement Problems?
Get complete access to all problems with step-by-step video solutions