# Recursive derangement proof clarification

I saw a proof of a recursive definition of $$D_n$$ = the number of derangements of a set of size $$n$$.

A combinatorial proof of the recurrence for $$D_n$$:

Here's a combinatorial proof of $$D_n = (n-1)(D_{n-1} + D_{n-2})$$ for $$n \geq 2$$ due to Euler.

For any derangement $$(j_1, j_2, \ldots, j_n)$$, we have $$j_n \neq n$$. Let $$j_n = k$$, where $$k \in \{1, 2, \ldots, n-1\}$$. We now break the derangements on $$n$$ elements into two cases.

Case 1: $$j_k = n$$ (so $$k$$ and $$n$$ map to each other). By removing elements $$k$$ and $$n$$ from the permutation we have a derangement on $$n-2$$ elements, and so, for fixed $$k$$, there are $$D_{n-2}$$ derangements in this case.

Case 2: $$j_k \neq n$$. Swap the values of $$j_k$$ and $$j_n$$, so that we have a new permutation with $$j_k = k$$ and $$j_n \neq n$$. By removing element $$k$$ we have a derangement on $$n-1$$ elements, and so, for fixed $$k$$, there are $$D_{n-1}$$ derangements in this case.

Thus, with $$n-1$$ choices for $$k$$, we have, for $$n \geq 2$$, $$D_n = (n-1)(D_{n-1} + D_{n-2}).$$

What I'm having trouble understanding is, if $$j_n \neq n$$, and $$j_n=k$$, why can $$k$$ only be any positive integer less than $$n$$, and does this only apply to the final element of the derangement (which is listed here as $$j_n$$), or does it apply to all of them? If it did apply to all of them, it seems like the only numbers being able to be chosen for a certain position would be those less than the position number, but that doesn't seem logical to me.

Any help would be very much appreciated.

Proof from: Mike Spivey (https://math.stackexchange.com/users/2370/mike-spivey), I have a problem understanding the proof of Rencontres numbers (Derangements), URL (version: 2012-08-28): https://math.stackexchange.com/q/83433

We do not have to pick the last element. We can pick other element as well and the proof will still work.

If $j_n = n$, then it is not a derangement anymore. Hence $j_n = k$ where $k \neq n$.

We can change the proof.

You can pick a particular index $p \in \{ 1, \ldots, n\}$

For any derangement $(j_1, j_2, \ldots, j_n)$, we have $j_p \neq p$. Let $j_p = k$, where $k \in \{1, 2, \ldots, n\}\setminus \{p\}$. We now break the derangements on $n$ elements into two cases.

Case $1$: $j_k = p$

Case $2$: $j_k \neq p$.

• Yeah, that makes sense. It seemed more logical to refer to indices as opposed to the actual numbers. Thanks :) Commented Aug 17, 2017 at 5:30

I think an easier-to-understand proof would be:

• we have $$n - 1$$ options to place $$n$$
• It suffices to count the number of derangements, such that $$j_{n-1} = n$$ (one fixed number) and multiply this by $$(n - 1)$$ to get $$D_n$$

If the number $$n - 1$$ appears in the last position ($$j_n = n - 1$$), then - as above - $$(j_1, \dots, j_{n - 2})$$ is any of the $$D_{n-2}$$ derangements

If the number $$n - 1$$ is among the first $$n - 2$$ numbers, then $$(j_1, \dots, j_{n -2}, j_n)$$ is any of the $$D_{n - 1}$$ derangements.