Six letters into six envelopes: none in the right one

Question

A distracted clerk stuffs six different letters into six addressed envelopes in a completely random order, so all $6! = 720$ arrangements are equally likely.

What is the probability that no letter ends up in its correct envelope?

Accepted Answer

We need a derangement of 6 items. Using inclusion-exclusion to remove arrangements with at least one correct match, D6 = 6!\left(1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!} - \frac{1}{5!} + \frac{1}{6!}ight). A quick way to the count is the recurrence Dn = (n-1)(D{n-1} + D{n-2}) with D4 = 9 and D5 = 44: D6 = 5\,(44 + 9) = 5 	imes 53 = 265. So the probability is \frac{D6}{6!} = \frac{265}{720} = \frac{53}{144} \approx 0.3681. Takeaway. The recurrence Dn = (n-1)(D{n-1} + D{n-2}) builds derangement counts fast, and the resulting probability hugs 1/e \approx 0.368.

Six letters into six envelopes: none in the right one

Your answer

Discussion

Learn the concepts

Related questions