Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2003/ia/paper-2/9f/solution

The inclusion-exclusion principle gives
For the coat problem, all permutations are equally likely. If a specified set of people gets its own coats, the other coats can be assigned in ways, so that intersection has probability . Taking the complement of the union of correct-coat events gives the derangement probability
To have exactly fixed coats, choose their recipients and derange all remaining coats. Thus the fixed point count of a uniform random permutation has
and zero probability outside this range. The empty permutation has , so the formula includes ; it also gives zero for , since a lone remaining coat cannot be misplaced.
For fixed , , and the exponential series gives
These are the probabilities of a Poisson distribution of mean one. The limit is for fixed , not for increasing with .

New to topics? Read the docs here!