# Derangement Probability

If we randomly shuffle some large sequence, what’s the chance that no item will end up in the same spot it started in?

First off, a “large” sequence means a sequence of length $$n$$ as $$n \to \infty$$, that’ll be handy in a bit.

The probability $$P$$ of some event can be expressed as the number of outcomes in which it happens divided by the total number of possible outcomes. Here, that total is $$n!$$, the number of permutations of the sequence.

A permutation where no item ends up where it started is known as a “derangement”, and the number of derangements of a sequence can be found via the “subfactorial”, denoted $$!n$$. Given this knowledge, we can start sketching a way to find $$P$$:

$P = \frac{\mathrm{derangements}}{\mathrm{permutations}} = \frac{!n}{n!}$

There are lots of expressions for $$!n$$ to choose from, but the easiest to work with here will be ones where we can either cancel the $$n!$$ in the denominator, or easily analyze them in some other way. Given that, let’s see a couple different ways to find our answer.

One promising starting point is this sum, where we can factor out the $$n!$$ immediately:

$!n = n! \sum_{k=0}^n \frac{(-1)^k}{k!}$

$P = \frac{!n}{n!} = \sum_{k=0}^n \frac{(-1)^k}{k!}$

Because we specified we want to know what happens for “large sequences”, we can take $$n \to \infty$$ and find a similarity with a well-known formula. (We can still calculate exact solutions for any given $$n$$ if we want to.)

Given $x \in \mathbb{R}, \: \: \: e^x = \sum_{k=0}^{\infty} \frac{x^k}{k!}$

Since we have $$x = -1$$, we can simplify the sum down to

$P = \frac{!n}{n!} = e^{-1} = \frac{1}{e}$

Now, for the other way. Here’s a closed-form solution1 for subfactorial, where the notation $$[n = 0]$$ means “$$1$$ if $$n$$ is $$0$$, else $$0$$”.

$!n = \bigg\lfloor \frac{n!}{e} + \frac{1}{2} \bigg\rfloor + [n=0]$

Divide out $$n!$$ again. Because we’re taking $$n \to \infty$$, we can drop $$[n=0]$$ without issues

$P = \frac{!n}{n!} = \frac{\bigg\lfloor \frac{n!}{e} + \frac{1}{2} \bigg\rfloor}{n!}$

For large $$n$$, $$\frac{n!}{e}$$ is so much larger than the added $$\frac{1}{2}$$ that it becomes irrelevant to finding our probability, so let’s drop that as well

$P = \frac{!n}{n!} = \frac{\bigg\lfloor \frac{n!}{e} \bigg\rfloor}{n!}$

Not the strongest formal argument here…but again, for very large $$n$$, whether we take the floor to the nearest integer doesn’t really matter either to our final result. Let’s drop that too!

$P = \frac{!n}{n!} = \frac{\frac{n!}{e}}{n!} = \frac{1}{e}$

The chance that your items in a large sequence end up deranged, and not merely permuted, is thus approximately $$\frac{1}{e}$$.

1. I’m getting this form from Concrete Mathematics by Graham, Knuth, and Patashnik (and getting the other one from MathWorld)↩︎