1
$\begingroup$

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

$\endgroup$

2 Answers 2

1
$\begingroup$

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$.

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

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .