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}\).