ReasoningAbility.com

Derangement Problem

Derangement is a permutation of elements where no element appears in its original position. For example, arranging n letters into n envelopes so that no letter goes into its correct envelope. The number of derangements of n items is denoted as !n (subfactorial) or D(n).

10Worksheets
200+Practice Questions
HardDifficulty
3-4 hoursHours to Master

What You'll Learn

Introduction & Overview Why This Matters How to Solve Pro Tips & Tricks
Shortcut Methods Common Mistakes Practice Worksheets Exam Importance

Introduction to Derangement Problem

Derangement is a permutation of elements where no element appears in its original position. For example, arranging n letters into n envelopes so that no letter goes into its correct envelope. The number of derangements of n items is denoted as !n (subfactorial) or D(n).

Prerequisites

Basic permutation Inclusion-Exclusion Principle Recursive formulas Factorial concept
Why This Matters: Derangement problems appear in 1-2 questions in advanced exams like CAT. They test understanding of inclusion-exclusion principle and recursive reasoning.

How to Solve Derangement Problem Problems

1

Step 1: Identify that the problem requires no element in its original position

2

Step 2: Use derangement formula: !n = n! × [1 - 1/1! + 1/2! - 1/3! + ... + (-1)ⁿ/n!]

3

Step 3: Or use recurrence: !n = (n-1) × (!(n-1) + !(n-2))

4

Step 4: Know base values: !0 = 1, !1 = 0, !2 = 1

5

Step 5: Calculate step by step for the given n

6

Step 6: For partial derangements (exactly k fixed points), use rencontres numbers

7

Step 7: Verify the answer is reasonable (approximately n!/e for large n)

Pro Strategy: For small n (≤ 7), use the recurrence relation. For larger n, use the inclusion-exclusion formula. Remember that derangements grow approximately as n!/e, where e ≈ 2.71828.

Example Problem

Example: In how many ways can 4 letters be placed into 4 envelopes so that no letter goes into its correct envelope? Solution: Step 1: This is a derangement problem with n = 4 Step 2: Using recurrence: !4 = (4-1) × (!3 + !2) Step 3: !2 = 1, !3 = (3-1) × (!2 + !1) = 2 × (1 + 0) = 2 Step 4: !4 = 3 × (2 + 1) = 3 × 3 = 9 Answer: 9 ways

Pro Tips & Tricks

  • !n = round(n!/e) for n ≥ 1 (nearest integer)
  • Recurrence: !n = (n-1)[!(n-1) + !(n-2)]
  • Base values: !0 = 1, !1 = 0, !2 = 1, !3 = 2, !4 = 9, !5 = 44, !6 = 265, !7 = 1854
  • Probability of derangement = !n/n! ≈ 1/e ≈ 0.3679 for large n
  • For partial derangement (exactly k fixed points): C(n,k) × !(n-k)
  • Derangement problems are also called 'hat-check problem'

Shortcut Methods to Solve Faster

!3 = 2
!4 = 9
!5 = 44
!6 = 265
!7 = 1854
!n ≈ n!/e for large n

Common Mistakes to Avoid

Confusing derangement with total permutations (n!)
Using the recurrence incorrectly (forgetting base cases)
Not understanding that !n is different from factorial n
Applying derangement formula when some fixed points are allowed

Exam Importance

Derangement Problem is an important topic for various competitive exams. Here's how frequently it appears:

SSC CGL
0-1 questions
BANKING PO
0-1 questions
RAILWAYS RRB
0-1 questions
CAT
1-2 questions
INSURANCE
0-1 questions

Ready to Master Derangement Problem?

Start with Worksheet 1 and work your way up to expert level! Each worksheet includes:

20 practice questions
Detailed solutions
Step-by-step explanations
Start Practicing Now