Derangments

If you ain't one of those normies who go to Youtube to see cat videos, you've probably already checked out Numberphile's latest video about derangments. The video is embedded right here.

But in the video, James Grime gave out the result without proving it, and it's outrageous! (He actually proves it in Numberphile 2)

So in this article, we will prove that result together.

🙋But my Internet connection is too slow to watch youtube!!

Ok, here's a quick overview of the derangements problem. You invite 3 to your house. Each one of them carries an identical TI-84 (yes, nerds' party!). They put their calculators on the table, and retrieve them when the party ends. If no one gets back his/ her own calculator, we call that situation a derangement. So what's the probability that we will get a derangement?
Visual illustration, please!!

Here's a invalid derangement because although Alice and Bob don't get back their Ti-84, Claire gets back her own calculator. In general, we want to ask the same question for $n$ people instead of only $3$. 

🙋I'm not sure where to start?

Let's start by telling me how many arrangements there are in total.

🙋You mean the number of just any arrangements without any restriction?

Yes.

🙋Isn't it just $n!$ ? In this case, it's $3!$ because Alice has 3 choices of which calculator to take, Bob has 2 choices, and Claire takes whatever is left. (if you're not sure what's going on, please check out the article on permutation.)

Correct. So we'll count the number of invalid derangements and subtract it from the total number of arrangements $n!$ to get the valid ones. What makes an arrangement invalid?

🙋At least one person gets his/her calculator back!

What does the phrase "at least" mean to you?

🙋It means using Sieve Method! (if you're not sure what's going on, please check out the article on Sieve Method.)

Correct. For mathematical expediency, let's dehumanize your friends a bit and label them from $1$ to $n$. Now let $A_i$ be the event that the guy $i$ gets back his own calculator, then the event that at least one guy will get back his own calculator will be $A_1 \cup A_2 \cup ... \cup A_n$, right? So by the Sieve method, we'll get a bunch of intersections. Let's consider a typical intersection. Consider the event that $k$ people get back their own calculators, in how many ways can it happen? Well, we have $\binom{n}{k}$ ways to choose those $k$ guys. Then, after giving $k$ guys back their own calculators, we still have $n-k$ guys and $n-k$ calculators to arrange. Now, we can arrange without any restriction, so we have $(n-k)!$ ways to arrange. So together, the number of ways to arrange so that $k$ people will get back their own calculators is $\binom{n}{k}(n-k)!$. Let the $k$ runs through $1$ to $n$ to get the Sieve method:
$ \mid A_1 \cup A_2 \cup ... \cup A_n \mid =\displaystyle \sum_{k=1}^n (-1)^{k-1} \binom{n}{k}(n-k)!$
$= \displaystyle \sum_{k=1}^n (-1)^{k-1}\frac{n!}{k!}$
So the probability of having a derangement is:
$\displaystyle \frac{n!-\mid A_1 \cup A_2 \cup ... \cup A_n \mid}{n!}= 1-$$\displaystyle \sum_{k=1}^n (-1)^{k-1}\frac{1}{k!}=\sum_{i=0}^n(-1)^i\frac{1}{i!}$.

🙋Wait, didn't I see $e$ in Numberphile's video?

Yes. You'll see the $e$ if you're familiar with Taylor expansion (Cal BC let me see your hands up !) Let me refresh your memory:
$e^x = \displaystyle \sum_{i=0}^{\infty} \frac{x^i}{i!}$
Looks familiar? Plug $x=-1$ in, and we show that with $n$ big enough, the probability of having a derangement is approximately $\displaystyle \frac{1}{e}$ or $37$%.