Proving recursive identity for permutations where no element stays in the same place $f_n = (n-1)(f_{n-1} + f_{n-2})$ A strict permutation is a permutation where none of the objects stay in the same place, i.e. the $i$th object is not in the $i$th position after the permutation. $f_n$, the number of strict permutations of $n$ elements can be defined recursively:
$f_n = (n-1)(f_{n-1} + f_{n-2})$
The proof was given as follows: if the $n$th element goes into position $i$, then either:

*

*The $i$th element goes to position $n$, and we strictly permute the remaining $n-2$ elements, giving $f_{n-2}$.


*The $i$th element goes to one of the $n-2$ positions other than $n$ and $i$, and we permute all the elements except the $n$th element (but including the $i$th one), giving $f_{n-1}$.
Since there are $n-1$ choices for the initial position $i$ which the $n$th element went to, the overall formula is $(n-1)(f_{n-2}+f_{n-1})$.
I don't quite understand this: in the second case, why do we include $i$ in the permutation? It's already no longer in its original position so we do not need to move it again.
I thought of another proof, but I'm not sure if it's right. We can either strictly permute $n-1$ elements first and then switch in the remaining $n$th element, which gives a strict permutation of $n$ elements. Or we can switch the $n$th element with some other element first, and then also ignore the element it was switched with and strictly permute the remaining $n-2$ elements, again giving a strict permutation of $n$ elements. In either case, there are $n-1$ options for which element to switch with the $n$th element, thus giving the formula $f_n = (n-1)(f_{n-1} + f_{n-2}).$
However, I am confused about this proof as well: the two cases do not actually seem to be distinct. Switching the $n$th element with another element before the permutation seems exactly equivalent to switching it in afterwards. In either case we are counting all the instances where one of the other $n-1$ elements are in position $n$. But the proof did properly yield the identity, so clearly I am mistaken somewhere.
I would appreciate if anyone could address my confusion with either of these proofs.
 A: Your proof is good, because the two cases are actually distinct. If you strictly permute $\{1,\dots,n-1\}$, and then switch in $n$, then $n$ will certainly be in a cycle of length $3$ or more. On the other hand, if you switch $n$ with some element, then strictly permute the remaining $n-2$, then $n$ will be in a cycle of length $2$. Therefore, the two cases are distinguished by the length of the cycle that $n$ is in.
In general, if you take a permutation where $x$ is in a cycle of length $k$, and $y$ is in a distinct cycle of length $\ell$, then switching $x$ and $y$ will combine the two cycles into a single cycle of length $k+\ell$. This is why switching in $n$ causes $n$ to be a in cycle of length $3$ or more; since the previous permutation was strict, all cycles were length two or more, so switching in $n$ makes it three or more.

I also agree that their proof is confusingly worded. It is not really clear to me what they mean when they say "we permute all the elements except the nth element (but including the ith one)". Your explanation is obviously correct.
