OFFSET
1,2
COMMENTS
For n = odd integer the middle term of all counted permutations must be 1.
From Robert Israel, Sep 12 2016: (Start)
Consider the graph with vertices [1,...,n] if n is even, [2,...,n] if n is odd, and edges joining coprime integers.
a(n) is A037223(n) times the number of perfect matchings in this graph.
If n is an odd prime, a(n) = a(n-1). (End)
LINKS
Robert Israel, Table of n, a(n) for n = 1..31
EXAMPLE
For n = 6, the permutation (3,2,1,6,4,5) is not counted because p(2)=2 is not coprime to p(5)=4. However, the permutation (3,6,1,4,5,2) is counted because GCD(3,2) = GCD(6,5) = GCD(1,4) = 1.
MAPLE
M:= proc(A) option remember;
local n, t, i, Ai, Ap, inds, isrt, As;
n:= nops(A);
if n = 0 then return 1 fi;
t:= 0;
for i in A[1] do
inds:= [$2..i-1, $i+1..n];
Ai:= subs([1=NULL, i=NULL, seq(inds[i]=i, i=1..n-2)], A[inds]);
isrt:= sort([$1..n-2], (r, s) -> nops(Ai(r)) <= nops(Ai(s)), output=permutation);
Ai:= subs([seq(isrt[i]=i, i=1..n-2)], Ai[isrt]);
t:= t + procname(Ai);
od;
t;
end proc:
F:= proc(n) local A;
if n::odd then
if isprime(n) then return procname(n-1) fi;
A:= [seq(select(t -> igcd(t+1, i+1)=1, [$1..i-1, $i+1..n-1]), i=1..n-1)];
else
A:= [seq(select(t -> igcd(t, i)=1, [$1..i-1, $i+1..n]), i=1..n)]
fi;
M(A)*floor(n/2)!*2^floor(n/2)
end proc;
seq(F(n), n=1..27); # Robert Israel, Sep 12 2016
CROSSREFS
KEYWORD
hard,nonn
AUTHOR
Leroy Quet, Jan 07 2008
EXTENSIONS
a(6)-a(15) from Sean A. Irvine, May 17 2010
a(16)-a(25) from Robert Israel, Sep 12 2016
STATUS
approved