Example 6: Derangements

Click here to open an associated Mathcad worksheet:

At the bohemian jazz parties frequented by aficionados of the number  e, the espresso flows freely, and at the end of the evening, party-goers are just as likely to go home in someone else's overcoat as they are in their own. After such a party, what are the chances that at least one person goes home wearing the right coat?

To find out, we first have to calculate the total number of ways that the coats can be put on at random. We then throw out all of the ways that are all wrong, with absolutely no one getting the correct coat. Mathematicians call these "all wrong" matchings derangements. What's left should then be the number of ways in which at least one guest goes home in the right coat.

Imagine, for example, a party with ten guests. How many different ways can the ten coats be put on at random? Mathematicians would ask: How many permutations of the ten coats are there?

The coats at these parties are always piled in a great heap somewhere. The first guest to leave pulls a coat at random from the ten coats in the pile. The next guest to leave will then have nine possible ways to make a random choice. And so on. The last guest, presumably the host, must curl up in whatever coat remains. So, apparently, there are  (10)(9)(8)(7) ... (3)(2)(1)  ways for all of the coats to be chosen. This is  10!, and it is a very big number:  3,628,800  different permutations!

How many of these possibilities are all wrong? We could look through all of them and check, but we would spend a good part of our life doing so. (Try it, though, for 2, 3, or 4 guests, to see how the number can be found systematically.) Computers are much better at doing these kinds of long, repetitive calculations. A computer will quickly tell us that  1,334,961  of the possibilities result in absolutely no one going home in the correct coat.

Now notice: If we divide the total number of possibilities by the number of all-wrong possibilities we get:

It's  e  again! This is what makes these parties such fun.

Amazingly, this ratio stays about the same no matter how big the party gets! The chances of no one getting the right coat are always about one in  e. The chances of someone getting the right coat are therefore about  1 – 1/e , which is about  0.632, or almost two thirds. With this number comfortably above  50%, the host of the party can always sleep peacefully.