A relatively easy problem in probability is given $n$ letters randomly put in ­$n$ envelopes, how many letters, on average, end up at the correct destination. The nice thing about this problem is when an average is asked, there is little respect needed for correlations between random variables. That is, assume that $n = 2$. If one letter is mailed correctly, then the other must be correct, and vice versa. But in the world of averages, all we need to recognize is that the one letter has a $\frac{1}{2}$ chance of making it, and since they both have a $\frac{1}{2}$ chance of making it, the expectation is $2E\left( X \right) = 2\left( \frac{1}{2} \right) = 1$. For the general case, the answer is similarly 1.

A relatively challenging problem is what is the probability that $r$ out of $n$ letters are mailed correctly. For example, in the two letter case, there is this very odd kink in the probability curve where $P_{n}\left( r = 1 \right) = 0$ whereas $P_{n}\left( r = 0 \right) = P_{n}\left( r = 2 \right) = \frac{1}{2}$ (by the way, we know that this last equation must be true since $E_{n}\left( r \right) = 1$ as per the first paragraph.)

Another initial observation is that the key variable should be $n - r$, the number of incorrectly mailed letters since every problem can be a combination problem where $r$ are chosen correctly with probability $\frac{1}{r!}$ and $n - r$ are chosen incorrectly with probability $P_{n - r}\left( 0 \right)$:

\[P_{n}\left( r \right) = \begin{pmatrix} n \\ r \\ \end{pmatrix}\frac{1}{r!}\ P_{n - r}\left( 0 \right)\]

So what is $P_{n - r}\left( 0 \right)$? What’s the probability that given $n - r$ letters and $n - r$ envelopes, that none are sent to the correct address? This is where I went down a bit of a rabbit hole and thought about “cycles”: what if letter 1 went to person 2, letter 2 went to person 3, and letter $n$ went to person 1 – how many ways are there to do that? $\left( n - r - 1 \right)!$ ways out of the total $n!$ ways, which is $\frac{1}{n - r}$. So $P_{n - r}\left( 0 \right) = \frac{1}{n - r}$? Unfortunately not. It’s not a complete count because there can be more than 1 cycle: letter 1 went to person 2; letter 2 went to person 1; letter 3 started a new cycle, going to person 4, letter 4 went to person 5, and letter $n$ went to person 3.

So the answer is not so simple, and actually, it’s kind of its own thing that we’ve stubbled onto:

\[P_{n - r}\left( 0 \right) = \frac{!(n - r)}{\left( n - r \right)!}\]

where $!(n - r)$ is known as the derangement numbers, and clearly from the notation, is closely related to factorials. Yes, there’s a mathematical notation for the number of ways to send no letters to the right person. This problem was solved around 1700, and you can read about it here, which makes the math sadly baroque. The punchline is that $P_{n - r}\left( 0 \right)$ does not have a closed form solution and tends towards $\frac{1}{e}$.

But the cool discovery in this midst is the relationship between derangement numbers and partitions. The probability of no letter being mailed to the correct person can be represented as a sum all the different possible cycles (except ones that have a cycle size of 1). For example, if there are 5 people, the biggest cycle is 5, but you can also have 2 people, plus 3 people. As before the probability no one gets the correct letter in a cycle of size $s$ is $\frac{1}{s}$ So in the five person case, the answer is

\[\frac{1}{5} + \frac{1}{3}*\frac{1}{2} = \frac{11}{30}\]

And we note that

\[\frac{!5}{5!} = \frac{44}{120} = \frac{11}{30}\]

By the way $11/30$ is $0.367$ which is pretty close to $1/e$ already.

So there is clearly a recursive relationship - $P_{5} = \frac{1}{5} + P_{3}P_{2}$. (I’m abusing notation a little here, omitting the $(0)$) The starting conditions are $P_{0} = 1$ and $P_{0} = 0$. You can from there derive all the derangement numbers. Unfortunately, partitions are even more intractable than derangement numbers, so if we found out something new (which we haven’t) it’s more likely useful going the other way – that is to use the derangement numbers to figure out how many partitions there are.

There’s a much nicer recursion. Consider when a $n$th letter and $n$th person are added. How do we make sure that no one is matched? Well one easy way is if we switch a new letter with one of the older letters (of which there are $n - 1$). Then we can ensure that no one is matched. But consider when previously we had 1 match, we could switch that matched letter with the new letter, and get no matches. That is we can go from state $r=1$ down to $r=0$, and we want the count of all $r=0$ So we want:

\[P_{n}\left( r \right) = P_{n - 1}\left( 0 \right)\left( n - 1 \right) + P_{n - 1}\left( 1 \right)\]

And using a previous formula, we know

\[P_{n - 1}\left( 1 \right) = \begin{pmatrix} n - 1 \\ 1 \\ \end{pmatrix}\ P_{n - 2}\left( 0 \right) = \left( n - 1 \right)\ P_{n - 2}\left( 0 \right)\]

So

\[P_{n} = \left( n - 1 \right)(P_{n - 1} + P_{n - 2})\]

You probably need to convince yourself that this is correct. What if there used to be 2 correct, and we swapped the new letter with one pair, and the new person with the other pair? In the process of doing that, you would have created the situation where only 1 is correct (that is to get to $r=0$, you must pass through $r=1$ or $r=0$), and so that is appropriated counted for in $P_{n - 1}\left( 1 \right)$.

From here, a mathematician can expand this into the various usable forms of derangement numbers, including the one that shows it converges to $\frac{1}{e}$.

When I first did this problem, I was hopeful I had found something cool. I emailed the conclusion related to partitions and derangements to a mathematician named Walter Stromquist, who adjudicated my first paper, and this was his response:

Every permutation has a cycle structure. How many permutations of size n have… n1 cycles of length 1 n2 cycles of length 2 … nk cycles of length k? The answer is n! / ( 1^n1 * 2^n2 * … * k^nk * n1! * n2! * … * ni! ). So if you add up these expressions for every possible sequence n1,…,nk you get the whole number of permutations, n!. So:

n! = sum over all sequences n1, n2, ..., nk such that
        n1 + 2n2 + 3n3 + ... + knk = n
     of
          n! / ( 1^n1 * 2^n2 * ... * k^nk * n1! * n2! * ... * ni! ).

Your formula is different, because you’re just looking at the derangements, so you leave out the terms in which n1 > 0.

I’m in a train and can’t look things up, so I’m not sure, but I think this formula played a big role in a paper in MathMag a few years ago, by James Sellers and a coauthor.

So he was able to tell I derived it from cycles, and so clearly there’s nothing novel to this finding. I prefer his first response before the lengthy one:

That’s interesting! I’ll think about and write back.