Number of one-to-one function such that $f(f(x))=x$ and $\left\lvert f(x)-x \right\rvert>2$ for all $x\in\{1,2,...,2n\}$ One of my friends asked this combinatorics problem, and I am completely lost...
The problem is to find the number of one-to-one function $f:\{1,2,...,2n\}\mapsto\{1,2,...,2n\}$ such that
$$f(f(x))=x$$and$$\left\lvert f(x)-x \right\rvert>2$$for all $x\in\{1,2,...,2n\}$
I tried to make a recurrence relation, directly count it...etc. No methods seems to work for me.
P.S. If this can be solved, can it be extended to the case where $\left\lvert f(x)-x \right\rvert>k$?
 A: What follows is definitely more of  a comment, but it may help inspire
more  work on this  interesting problem.  Here is  a Perl  script that
succeeds in computing the number of admissible functions up to $n=8.$

#! /usr/bin/perl -w
#

sub enumerate {
    my ($n, $src, $pos, $seen, $mref) = @_;

    if(scalar(keys(%$seen)) == 2*$n){
        $$mref++;
        return;
    }


    return if $pos >= scalar(@$src);

    enumerate($n, $src, $pos+1, $seen, $mref);

    my ($u, $v) = @{ $src->[$pos] };

    if(not(exists($seen->{$u})) &&
       not(exists($seen->{$v}))){
        $seen->{$u} = 1;
        $seen->{$v} = 1;

        enumerate($n, $src, $pos+1, $seen, $mref);

        delete $seen->{$v};
        delete $seen->{$u};
    }

    1;
}

MAIN : {
    my $mx = int(shift || 3);

    for(my $n=1; $n <= $mx; $n++){
        my @srcdata;

        for(my $p=1; $p <= 2*$n; $p++){
            for(my $q=$p+3; $q <= 2*$n; $q++){
                push @srcdata, [$p, $q];
            }
        }

        my $match = 0;
        enumerate($n, \@srcdata, 0, {}, \$match);

        print "$n: $match\n";
    }

    1;
}

This produces the following table:

1: 0
2: 0
3: 1
4: 10
5: 99
6: 1146
7: 15422
8: 237135

It will send us  to OEIS entry A190823. We
discover  on consulting  this entry  that there  are no  references or
formulae at all.  This is definite evidence for  the problem being new
and difficult. Good luck!
