A couple of weeks ago I was at the Millbrae BART station and a young man asked me if I knew how to get to Slim’s in San Francisco. I didn’t, but I had my iPhone on me so I used Google Maps and showed him how to get there. After we got on the train we chatted some more, and he mentioned that he maybe shouldn’t be going to this event at Slim’s, because he had homework to do in probability and statistics. I told him I knew something about that stuff, and he showed me his homework.

One of the problems he hadn’t been able to solve concerned 25 letters and the 25 differently addressed envelopes that they were supposed to go into. The letters are shuffled and randomly stuffed into the envelopes. What are the odds that no letters at all wind up in their proper envelopes?

I told him I thought this was an awfully hard problem to be giving to an introductory class, but we weren’t going anywhere anyway, so we got out pen and paper and we tackled it. We (mostly me) came up with a plausible looking formula for the solution, but when I calculated it, it all reduced to (24/25)²⁵, and I knew that that couldn’t be the correct answer. (That would be the answer if each pairing of a letter to an envelope was a completely independent event from the others; but they aren’t, because each pairing takes a letter and an envelope out of the game, and that I knew that that just had to affect the odds in some way, even though I couldn’t figure out how to figure out exactly how it did. I give myself partial credit, though, for at least recognizing that our answer could not possibly be right.)

When I got back home I did some online research and discovered that there’s a special name for a permutation (that is, a shuffling of ordered objects) that does not leave any object in its correct place in the order: a derangement. It seems inconceivable that I haven’t come across this term before at some point, but I don’t have any memory of it; maybe something I encountered in college and not since.

There’s a very tidy little formula for getting the number of possible derangements of n objects: d_n = n!/e rounded to the nearest integer. And therefore the probability that a random permutation will be a derangement (that every letter ends up in the wrong envelope) is the number of derangements divided by the number of permutations, or d_n/n!. This is very close (just a rounding error away) to (n!/e)/n!, which cancels out neatly to 1/e, which is about 0.368 (or 36.8%), and in fact as n increases, the probability converges toward precisely 1/e very, very rapidly.

It’s neat and counterintuitive, then, to consider that the odds don’t change significantly whether you’ve got 25 envelopes to stuff or 25 trillion.

Thing is, I got all this off a website, and the calculations needed to get that simple-looking formula for d_n are pretty darned long and involved. So I have to wonder what it’s doing on the homework for an introductory class. Maybe it was meant as an exercise in Internet research?