Problem 55280. Count estrangements

Here's an informal proof:

To meet the permutation requirement, the numbers 1:n must form one or more "circulations", that is P(a)=b, P(b)=c, ... P(?) =a. In order to meet the two constraints that nothing match to itself, nor a swapped pair, each such circulation must contain at least three elements.
Calculating such permutations for small numbers is simple. There are clearly zero estrangements for sets of 1 or 2 due to the constraints. For 3, there are only six permutations, of which only 2 are estrangements ([312] and [213]).

So let's assume we have E(n) already calculated for 1:n, with n>=3, and we're calculating E(n+1). This is sufficient to solve all larger cases.

Key Question for induction: where does entry n+1 fit in the "circulations"? This breaks down to two cases: N+1 is in a circulation of exactly three numbers, or N+1 is in a circulation of four or more numbers. As discussed earlier, the group cannot be smaller than three.

If N+1 is in a circulation of exactly 3 numbers, there are clearly nchoosek(N,2) sets of two additional items which can be chosen, each with two permutations. This is then multiplied by the number of estrangements for N-2, yielding N*(N-1)*E(N-2).
If N+1 is in a circulation of 4 or more numbers, it can clearly be "shoved" into a solution for E(N). As each solution to E(N) has N circulation links, this yields N*E(N)solutions.

Combining the two, E(N+1) = N*E(N) + N*(N-1)*E(N-2).