Proving recurrence relation on the cardinal of the derangements

Question

Let $$f_n = |\{\pi \in S_n \space | \space \forall 1 \leq i \leq n : \pi(i) \neq i \}|$$

Prove that $f_1 = 0, f_2 = 1$, and $f_n = (n-1)(f_{n-1} + f_{n-2})$. Furthermore, prove that this recurrence relation implies $$f_n = n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}$$

As long as I understood, it says that we are interested about permutations of $n$ numbers, such that none of the numbers are in their original position. I tested it for first non-trivial and hand-testable value of $n$ which is $n=3$. I have two permutation that satisfy the condition, and they are $(312)$ and $(231)$. Plugging the numbers into $f_n$ yields $f_3 = 2\cdot(f_2 + f_1) = 2 \cdot (1 + 0) = 2$, so clearly the identity holds. But how can I prove it for arbitrary n? I tried to do something like induction, but I got stuck. And how can I prove the recurrence relation?

Answer 1

A permutation having the property you describe is named a derangement.

First, let's prove that for all $n \ge 0$, $$f_{n+2}=(n+1)(f_{n+1}+f_n).$$ We denote $$\begin{cases} E_{n+1} &= \{1 & 2 \ \dots \ k-1 \ & k & k+1 \ \dots \ n+1\}\\ G_{n+1} &= \{1 & 2 \ \dots \ k-1 \ & n+2 & k+1 \ \dots \ n+1\} \end{cases}$$ and $$R_n=\{\pi \in S_n \space | \space \forall 1 \leq i \leq n : \pi(i) \neq i \}.$$

Consider the elements $\sigma \in R_{n+2}$ such that $\sigma(n+2)=k <n+2$.

We have two cases.

1. Either $\sigma(k)=n+2$ in which case the images of $\{k,n+2\}$ under $\sigma$ are defined and it remains to define the images under $\sigma$ of the other $n$ elements. You have $f_n$ ways to do so. As also $1 \le k \le n+1$ you have on total $(n+1)f_n$ such permutations.
2. Either $\sigma(k) \neq n+2$. Then the restriction of $\sigma$ to $E_{n+1}$ is a map from $E_{n+1}$ to $G_{n+1}$. You have $f_{n+1}$ ways to define such a map. And again as $1 \le k \le n+1$, a total of $(n+1)f_{n+1}$ such permutations.

As both both cases are mutually exclusive and the only possible, we get the expected relation $$f_{n+2}=(n+1)(f_{n+1}+f_n)$$

$f_n = n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}$ can then be proved by induction.

Answer 2

Suppose that $\pi$ is a derangement of $[n]=\{1,\ldots,n\}$. There are two possibilities.

The simpler one is that there is some $k\in[n-1]$ such that $\pi(n)=k$ and $\pi(k)=n$. (In other words, $\pi$ interchanges $k$ and $n$.) Then the restriction of $\pi$ to the set $A_k=[n-1]\setminus\{k\}$ is a derangement of $A_k$. Conversely, I can start with any derangement $\tau$ of $A_k$ and extend it to a unique derangement $\pi$ of $[n]$ by setting $\pi(i)=\tau(i)$ for $i\in A_k$, $\pi(n)=k$, and $\pi(k)=n$. $|A_k|=n-2$, so there are $f_{n-2}$ derangements of $A_k$ and therefore also $f_{n-2}$ derangements of $[n]$ that interchange $n$ and $k$. Finally, there are $n-1$ possible choices for $k$, so there are $(n-1)f_{n-2}$ derangements of $[n]$ that interchange $n$ with some $k\in[n-1]$.

Now we have to count the derangements of $[n]$ that don’t simply interchange $n$ with some $k\in[n-1]$. Let $\pi$ be such a derangement, and let $k=\pi(n)$. We’re assuming that $n\ne\pi(k)$, so there is an $\ell\in[n-1]$ such that $\ell\ne k$ and $\pi(\ell)=n$. In other words, part of the operation of $\pi$ looks like the following diagram:

$$\ldots\overset{\pi}\longrightarrow\ell\overset{\pi}\longrightarrow n\overset{\pi}\longrightarrow k\overset{\pi}\longrightarrow\ldots\;.\tag{1}$$

We can build a derangement $\tau$ of $[n-1]$ by simply cutting $n$ out of the picture and closing up the gap:

$$\ldots\overset{\tau}\longrightarrow\ell\overset{\tau}\longrightarrow k\overset{\tau}\longrightarrow\ldots\;.\tag{2}$$

That is, $\tau(i)=\pi(i)$ if $i\ne\ell$, and $\tau(\ell)=k$. Now suppose that we start with some derangement $\tau$ of $[n-1]$. How many different derangements of $[n]$ will produce $\tau$ when we ‘cut out $n$’? Pick any $\ell\in[n-1]$, and let $k=\tau(\ell)$. Now insert $n$ between $\ell$ and $k$ by defining a derangement $pi$ of $[n]$ as follows: $\pi(i)=\tau(i)$ if $i\ne\ell$, $\pi(\ell)=n$, and $\pi(n)=k$. This just reverses the operation that took us from diagram $(1)$ to diagram $(2)$. There are $n-1$ possible choices for $\ell$, and each one of them yields a different derangement $\pi$ of $[n]$, so there are $n-1$ different derangements of $[n]$ that yield $\tau$ when we ‘cut out $n$’. And there are $f_{n-1}$ possible derangements $\tau$ of $[n-1]$, so there are altogether $(n-1)f_{n-1}$ derangements of $[n]$ that do not interchange $n$ with some $k\in[n-1]$.

Putting the pieces together, we see that

$$f_n=(n-1)f_{n-1}+(n-1)f_{n-2}=(n-1)(f_{n-1}+f_{n-2})\;.$$

We can now use this recurrence relation (together with the initial values $f_1=0$ and $f_2=1$) to prove by induction on $n$ that

$$f_n=n!\sum_{k=0}^n\frac{(-1)^k}{k!}\;.\tag{3}$$

To get the induction started, you need to check that $(3)$ is true for $n=1$ and $n=2$; I’ll leave that to you. For the induction step, suppose that $n\ge 2$, and that

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

for all positive integers $m<n$; that’s your induction hypothesis. Then

$$\begin{align*} f_n&=(n-1)(f_{n-1}+f_{n-2})\\ &=(n-1)\left((n-1)!\sum_{k=0}^{n-1}\frac{(-1)^k}{k!}+(n-2)!\sum_{k=0}^{n-2}\frac{(-1)^k}{k!}\right)\\ &=(n-1)\left((n-1)!\cdot\frac{(-1)^{n-1}}{(n-1)!}+(n-1)!\sum_{k=0}^{n-2}\frac{(-1)^k}{k!}+(n-2)!\sum_{k=0}^{n-2}\frac{(-1)^k}{k!}\right)\\ &=(n-1)\left((-1)^{n-1}+\sum_{k=0}^{n-2}\big((n-1)!+(n-2)!\big)\frac{(-1)^k}{k!}\right)\;. \end{align*}$$

Now use the fact that $(n-1)!+(n-2)!=n(n-2)!$ (along with a bit more algebra) to simplify this and show that it really is equal to the righthand side of $(3)$.