0

There are five top hats and five gentlemen. If the five gentlemen pool their top hats and redistribute them at random, what is the probability that none of the gentlemen would have his original top hat?

My original attempt was to directly calculate this using basic combinatorics. The entire number of possible outcomes is $5!$. Now the cases where none of the top hats are matched can be found by $4 \times 4 \times 3 \times 2 \times 1$, where the 4 at the beginning ensures that the first gentleman does not get his top hat.

I understand the probability obtained from the calculation above is wrong, but I do not see why. More importantly, it is not clear to me in what kind of situations I would need to use the exclusion-inclusion principle rather than the straight-forward approach that I used above.

Astaboom
  • 957

1 Answers1

1

You are correct that person number 1 has four choices for hats, but the next person in line might have four choices (if the first person took his) or might only have three choices (if the first person took another). You also can wind up with the last hat belonging to the last person and you are stuck.

A derivation of the correct formula is given in Wikipedia on derangements It is the closest integer to $\frac {5!}e$, which is $44$. For other numbers of people, the series is given in OEIS A000166

Ross Millikan
  • 374,822