Count the derangements of five items

Question

Five people put their gifts in a bag and each draws one back out uniformly at random (all $5! = 120$ orderings equally likely).

In how many arrangements does no one draw their own gift, and what is the probability of that?

Accepted Answer

By the formula. The number of derangements is Dn = n!\sum{k=0}^{n}\frac{(-1)^k}{k!}. For n = 5: D5 = 120\left(1 - 1 + \frac12 - \frac16 + \frac1{24} - \frac1{120}ight) = 120 \cdot \frac{44}{120} = 44. By the recurrence (a nice cross-check), Dn = (n-1)(D{n-1} + D{n-2}) with D1 = 0,\ D2 = 1: D3 = 2(1 + 0) = 2,\quad D4 = 3(2 + 1) = 9,\quad D5 = 4(9 + 2) = 44. So there are \boxed{44} no-match arrangements, and P(	ext{no one gets their own}) = \frac{D5}{5!} = \frac{44}{120} = \frac{11}{30} \approx 0.3667. That is already within 0.001 of the limiting value 1/e \approx 0.3679, showing how fast th…

Count the derangements of five items

Your answer

More Probability questions