Derangements

Derangements are arrangements of some number of objects into positions such that no object goes to its specified position. In the language of permutations, a derangement is a permutation $\sigma$ of $n$ elements with no fixed point; that is, $\sigma(i) \ne i$ for all $i \in \{1,2,\ldots,n\}$.

Letters and Envelopes Problem:

A kid has ‘N’ letters labeled Letter1, Letter2, …, LetterN and the corresponding ‘N’ addressed envelopes labeled Envelope1, Envelope2, ..., EnvelopeN. Then how many ways can the kid put the letters in the wrong envelope? (Letter1 should not go to Envelope1, Letter2 should not go to Envelope2, ...., LetterN should not go to EnvelopeN.)

Case 1: The kid has one envelope and one letter.
Letter1 $\to$ Envelop1
So the answer is 0 (zero). The kid did not have any option to insert the single letter into the wrong envelope. Hence the answer is zero.

Case 2: The kid has two envelopes and two letters.
Letter1 $\to$ Envelop2
Letter2 $\to$ Envelop1
So the answer is 1. If the kid placed the first letter in the wrong envelope, then the second letter automatically goes into the wrong envelope, so the possible choice is 1.

Case N: The kid has 'N' envelops and 'N' letters.
The answer is $!N$ $(“$derangements of $N"),$ where $!N= N!\left[1-\frac1{1!}+\frac1{2!}-\frac1{3!}+\cdots \frac1{N!}\right].$

Let $D(n)$ be the number of derangements for $n$ different objects, then

$$D_n=n!\displaystyle\sum_{r=0}^{n} \dfrac{(-1)^r}{r!}.$$

Let there be $n$ distinct objects with their $n$ distinct respective positions. Then the number of derangements is $n!-N,$ where $N$ is the number of ways of arranging the $n$ objects in such a way that at least one object goes to its right position.

To find $N$, use PIE.

Let $A_r$ be the set of permutations in which the $r^\text{th}$ object goes into its right position. The goal is to find $\displaystyle N=\left|\bigcup_{r=1}^{n} A_r\right|$.

Observe that $|A_i|=(n-1)!$, $|A_i \cap A_j|=(n-2)!,$ and so on.
Then $\displaystyle\sum_{i}|A_i|=\binom{n}{1}(n-1)!$, $\displaystyle\sum_{i<j}|A_i \cap A_j|=\binom{n}{2}(n-2)!,$ and so on.
Now, using PIE,

$$\begin{aligned} N=\left|\displaystyle\bigcup_{r=1}^{n} A_r \right| &=\sum \lvert A_{i_1} \rvert-\sum_{i < j} \lvert A_{i} \cap A_{j} \rvert +\cdots+(-1)^{n+1} \big|A_1 \cap A_2 \cap \ldots \cap A_n\big|\\ &=\sum_{r=1}^{n}(-1)^{r+1} \binom{n}{r}(n-r)! \\ &=\sum_{r=1}^{n} (-1)^{r+1} \dfrac{n!}{r!}. \end{aligned}$$

Therefore, the number of derangements is

$$\begin{aligned} D_n&=n!-N\\ &=n!-\sum_{r=1}^{n} (-1)^{r+1} \dfrac{n!}{r!}\\ &=n!\displaystyle\sum_{r=0}^{n} \dfrac{(-1)^r}{r!}. \ _\square \end{aligned}$$

The above formula can be rewritten recursively as

$$D(n)=nD(n-1)+ (-1)^n.$$

Note that $\frac{D_n}{n!}$ is the $n^\text{th}$ partial sum of the Taylor series for $e^x$ evaluated at $x=-1$, so

$$\lim_{n\to\infty} \frac{D_n}{n!} = \frac1{e}.$$

So, for large $n$, the probability that a permutation of $n$ objects is a derangement is approximately $\frac1{e}$.

In fact, for any positive integer $n,$ $D_n=\left[\frac{n!}{e}\right],$ where the square brackets are the nearest integer function.

Here is another recursive formula for $D(n):$

$$D(n) = (n-1)\big(D(n-1)+D(n-2)\big).$$

Let $a, b, c, \ldots, n$ be $n$ distinct objects with their respective containers $A, B, C, \ldots, N,$ and suppose $a$ goes into $B.$ Then it gives rise to the following two cases:

Case 1: When $b$ goes to $A:$
Leaving out $a$ and $b,$ there are derangements for $n-2$ objects: $D(n-2).$

Case 2: When $b$ goes to any other container:
Leaving out $a,$ the number of these is the same as the number of derangements of $n-1$ objects $($including $b): D(n-1).$
$($If $c$ goes to $B$ in the derangement of $n-1$ objects, this corresponds to the derangement of $n$ objects where $c$ goes to $A$ and $a$ goes to $B.)$

Thus, the total is $D(n-1)+D(n-2).$

But the original assumption was that $a$ goes to $B$. There are $n-1$ choices for $B$, so

$$D(n)=(n-1)\big(D(n-1)+D(n-2)\big). \ _\square$$

Mickey the mailman is very lazy. He has received 10 parcels to 10 different people. However, because he is lazy, he doesn't bother reading the address and delivers them off randomly. In how many ways can Mickey deliver the parcels such that no one gets the right parcel?

---

By the derangements formula, the number of possible derangements is

$$\begin{aligned} 10! \left ( \frac{1}{0!} - \frac{1}{1!} + \cdots + \frac{1}{10!} \right )&= 10! - 10! + \frac{10!}{2!} - \cdots + 1\\ &= 1334961. \end{aligned}$$

Therefore, there are a total of 1334961 ways to deliver the parcels such that no one gets the right parcel. $_\square$

A teacher has six name tags to hand out to her six students. What is the probability that at least one student gets their name tag?

---

Using complementary probability, we see that there are $6! = 720$ ways to give out the name tags. The number of ways where nobody gets their name tag is

$$\begin{aligned} 6! \left ( \frac{1}{0!} - \frac{1}{1!} + \cdots + \frac{1}{6!} \right )&= 6! - 6! + \frac{6!}{2!} - \cdots + 1\\ &= 265. \end{aligned}$$

The probability is $\frac{720 - 265}{720} = \frac{455}{720} = \frac{91}{144}$. $_\square$