Intuitive explanation for derangements [duplicate]

The recurrence relation for Derangement is as follows:

Let $D_n$ denote the number of derangements of a set $\{1,2,3,\ldots,n\}$. Then,

$$D_n=(n-1)D_{n-1}+(n-1)D_{n-2}.$$

Can someone give an intuitive explanation on how we come to find this result?

Solution 1:

Suppose that $\pi$ is a derangement of $[n]$, and let $m=\pi(n)$. There are two possibilities: $\pi(m)=n$, so that $\pi$ interchanges $m$ and $n$, or $\pi(m)\ne n$.

If $\pi(m)=n$, then $\pi$ deranges $[n-1]\setminus\{m\}$. Conversely, any of the $D_{n-2}$ derangements of $[n-1]\setminus\{m\}$ can be extended to a derangement of $[n]$ that interchanges $m$ and $n$. And there are $n-1$ choices for $m$, so there are $(n-1)D_{n-2}$ derangements of $[n]$ that interchange $n$ and some $m\in[n-1]$.

Now suppose that $\pi(m)\ne n$, and let $k\in[n-1]$ be such that $\pi(k)=m$. Let $\pi'$ be the permutation of $[n-1]$ that is identical to $\pi$ except that $\pi'(k)=m$. (In other words, $\pi$ has a cycle $(\ldots,k,n,m,\ldots)$, and $\pi'$ is formed from $\pi$ by omitting $n$ to leave $(\ldots,k,m,\ldots)$.) Then $\pi'$ is a derangement of $[n-1]$. Conversely, given any derangement $\pi'$ of $[n-1]$, we can pick any $k\in[n-1]$ and insert $n$ between $k$ and $\pi'(k)$ to form a derangement $\pi$ of $[n]$ that agrees with $\pi'$ except at $k$: $\pi(k)=n$, and $\pi(n)=\pi'(k)$. There are $n-1$ choices of $k$, so $[n]$ has $(n-1)D_{n-1}$ derangements of this kind.

It follows that

$$D_n=(n-1)D_{n-1}+(n-1)D_{n-2}\;.$$