An Initiative by SAARTHI IAS
Maarg Manthan · Topic 22.11

Derangement Problems (CAT-Level)

Quantitative Aptitude › Permutation, Combination and Probability · Topic 22.11

A derangement is an arrangement of n items in which no item is in its original position, as in the classic letters and envelopes problem. The number of derangements of n items is D(n) = n! times the sum of (-1) raised to k divided by k!, with values 0, 1, 2, 9, 44, 265 for n = 1 to 6.

Share:
Derangement Problems (CAT-Level) - Quantitative Aptitude - MaargX UPSC Maarg Manthan

Quick Answer

A derangement is an arrangement of n items in which no item is in its original position, as in the classic letters and envelopes problem. The number of derangements of n items is D(n) = n! times the sum of (-1) raised to k divided by k!, with values 0, 1, 2, 9, 44, 265 for n = 1 to 6.

At a Glance

  • Definition No item in its own place
  • D1 to D6 0, 1, 2, 9, 44, 265
  • Recurrence D(n) = (n-1)[D(n-1) + D(n-2)]
  • Exactly r fixed nCr × D(n-r)
  • Limit of D(n)/n! 1/e, about 0.3679

Where Does It Fit?

This is a CAT-level topic that builds on Permutation of Distinct Objects and Objects with Repetition and Combination and Selection Problems. It uses the idea of the complement from Probability Using the Complementary Event Rule in the form of inclusion and exclusion.

What Is a Derangement?

In short: a derangement is a rearrangement of n distinct objects such that every object ends up away from its original place.

The standard picture is n letters and n addressed envelopes. A derangement is a way of putting every letter in a wrong envelope. The same idea appears in the hat-check problem, where n people take hats at random and nobody gets their own.

n Total arrangements n! Derangements D(n) P(no fixed point) = D(n)/n!
1 1 0 0
2 2 1 1/2
3 6 2 1/3
4 24 9 3/8
5 120 44 11/30
6 720 265 265/720 = 53/144

For n = 3 with letters A, B, C in places 1, 2, 3, the only derangements are BCA and CAB, so D3 = 2.

How Do You Find D(n)?

In short: use the alternating sum from inclusion and exclusion, or use the recurrence if you already know the two previous values.

Formulas

  • D(n) = n! [1 – 1/1! + 1/2! – 1/3! + … + (-1)n/n!]
  • D(n) = (n – 1) [D(n – 1) + D(n – 2)]
  • D(n) is the nearest integer to n!/e.
  • Alternating sum for n = 4: 24 × (1 – 1 + 1/2 – 1/6 + 1/24) = 24 – 24 + 12 – 4 + 1 = 9.
  • Recurrence: D3 = 2 × (D2 + D1) = 2 × (1 + 0) = 2, and D4 = 3 × (2 + 1) = 9.
  • Nearest integer: 5!/e = 120/2.71828 = 44.15, so D5 = 44; 6!/e = 264.87, so D6 = 265.

The proportion D(n)/n! quickly approaches 1/e, about 0.3679, so for n of 6 or more, the chance that nobody gets the right item is almost the same.

What Are Partial Derangements?

In short: when exactly r items must be in the right place, choose which r are fixed and derange the remaining n – r.

Exactly r correct

  • Number of arrangements with exactly r fixed items = nCr × D(n – r).
  • At least one fixed item = n! – D(n).
Case Calculation Result
4 letters, exactly 1 correct 4C1 × D3 = 4 × 2 8
5 letters, exactly 2 correct 5C2 × D3 = 10 × 2 20
5 letters, exactly 3 correct 5C3 × D2 = 10 × 1 10
4 letters, at least 1 correct 24 – 9 15

It is impossible to have exactly n – 1 items correct, because the last item must then also be in its own place.

Solved Examples

Example 1

Question: In how many ways can 4 letters be placed in 4 addressed envelopes so that no letter is in its own envelope?

  1. This is a derangement of 4 items.
  2. D4 = 3 × (D3 + D2) = 3 × (2 + 1) = 9.

Answer: 9 ways.

Example 2

Question: In how many ways can 5 letters be placed in 5 envelopes so that exactly 2 are in the correct envelopes?

  1. Choose the 2 correct letters in 5C2 = 10 ways.
  2. The other 3 must be deranged: D3 = 2.
  3. Multiply: 10 × 2.

Answer: 20 ways.

Example 3

Question: Four people leave their hats and take one at random. Find the probability that nobody gets their own hat.

  1. Favourable outcomes = D4 = 9.
  2. Total outcomes = 4! = 24.
  3. P = 9/24.

Answer: 3/8.

Example 4

Question: Use the recurrence to find D5.

  1. D(n) = (n – 1)[D(n – 1) + D(n – 2)].
  2. D5 = 4 × (D4 + D3) = 4 × (9 + 2).

Answer: D5 = 44.

Example 5

Question: In how many ways can 6 letters be placed in 6 envelopes so that exactly 4 are correct?

  1. Choose the 4 correct letters in 6C4 = 15 ways.
  2. The remaining 2 must be deranged: D2 = 1.
  3. Multiply: 15 × 1.

Answer: 15 ways.

Shortcuts and Tricks

  • Memorise D1 to D6: 0, 1, 2, 9, 44, 265.
  • Use D(n) = (n – 1)[D(n – 1) + D(n – 2)] when the earlier values are known.
  • For exactly r correct, write nCr × D(n – r).
  • For at least one correct, use n! – D(n).
  • D(n) is the nearest integer to n!/e, which gives a fast check.

Common Mistakes

  • Using n! – 1 or (n – 1)! as the number of derangements. The correct values are 0, 1, 2, 9, 44, 265.
  • Forgetting to choose which items are fixed before deranging the rest.
  • Assuming exactly n – 1 items can be correct. It is impossible, since the last item must also match.
  • Using the recurrence with wrong starting values, such as D1 = 1. The correct start is D1 = 0 and D2 = 1.
  • Mixing up at least one fixed point with exactly one fixed point.

Practice Questions

  1. What is D3?
  2. Use the recurrence to find D6.
  3. Probability that nobody gets their own letter when 3 letters go into 3 envelopes at random?
  4. In how many ways can 5 letters be put in 5 envelopes so that exactly 3 are correct?
  5. In how many ways can 5 letters be put in 5 envelopes so that at least one is correct?
  6. In how many ways can 5 letters be put in 5 envelopes so that exactly 1 is correct?

Answers: 1) 2; 2) 265; 3) 1/3; 4) 10; 5) 76; 6) 45.

Why Is This Topic Important?

  • CAT use A classic counting idea in CAT permutation questions.
  • Concept Shows inclusion and exclusion in action.
  • Link Extends Permutation of Distinct Objects and Objects with Repetition to restricted arrangements.
  • Probability Connects counting to the hat-check probability of about 0.368.

What Comes Next?

The next topic is Probability of At Least One Event Occurring Among Several. It returns to ordinary probability and uses independence to handle several events together.

Key Terms and Formulas

  • Derangement Arrangement with no item in its own place
  • Fixed point An item that stays in its original place
  • Subfactorial Another name for the number of derangements, written !n
  • Inclusion-exclusion Counting by adding and subtracting overlapping cases
  • Partial derangement Arrangement with exactly r items in place

Exam Corner

Points to Remember

  • D1 to D6 are 0, 1, 2, 9, 44, 265.
  • D(n) = (n-1)[D(n-1) + D(n-2)].
  • Exactly r fixed: nCr × D(n-r).
  • At least one fixed: n! – D(n).
  • D(n)/n! tends to 1/e, about 0.3679.

Do Not Confuse With

  • Derangement vs permutation A derangement is a permutation with no fixed point.
  • Exactly r vs at least r correct Exactly r uses nCr × D(n – r); at least r needs a sum over cases.
  • D(n) vs n!/e D(n) is exact; n!/e is only close to it and must be rounded.
  • D(n) vs (n-1)! They are different; D4 = 9 while 3! = 6.

Memory Hook

Nobody home: 0, 1, 2, 9, 44, 265.

GS Relevance

Derangements for CAT level quantitative aptitude: formula, recurrence, partial derangements, and letters-envelopes and hat problems.

Frequently Asked Questions

What is a derangement in permutations?

A derangement is an arrangement of n distinct items in which no item stays in its original position. The number of derangements of n items is written D(n), with values 0, 1, 2, 9, 44 and 265 for n from 1 to 6.

What is the formula for the number of derangements?

The number of derangements of n items is n factorial times the sum of minus one to the power k over k factorial, for k from 0 to n. It also satisfies D(n) equals n minus 1 times the sum of D(n minus 1) and D(n minus 2).

How many ways can 4 letters go into 4 envelopes with none correct?

There are 9 ways to place 4 letters into 4 addressed envelopes so that no letter is in its own envelope. This is D4, found from the recurrence D4 = 3 times the sum of D3 and D2, which is 3 times 3.

How do you count arrangements with exactly r correct items?

To count arrangements with exactly r correct items, choose which r items are fixed in nCr ways and derange the other n minus r items in D(n minus r) ways. The answer is the product nCr times D(n minus r).

What is the probability that nobody gets the correct item?

The probability that nobody gets the correct item is D(n) divided by n factorial. It equals 1/3 for n = 3, 3/8 for n = 4 and 11/30 for n = 5, and it approaches 1/e, about 0.3679, as n grows.

PYQ Practice — Statement Analysis

1 The number of derangements of 4 items is 9.
True

D4 = 3 x (D3 + D2) = 3 x 3 = 9.

2 It is possible to have exactly n - 1 items in their correct places in an arrangement of n items.
False

If n - 1 items are correct, the last item must also be correct, so exactly n - 1 is impossible.

3 D5 equals 44.
True

D5 = 4 x (D4 + D3) = 4 x 11 = 44.

4 As n becomes large, D(n) divided by n factorial approaches 1/e.
True

The ratio tends to about 0.3679.

Share: