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).
Group
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
You can also select a web site from the following list
How to Get Best Site Performance
Select the China site (in Chinese or English) for best site performance. Other MathWorks country sites are not optimized for visits from your location.
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).