A133922 a(n) is number of permutations (p(1),p(2),p(3),...,p(n)) of (1,2,3,...,n) such that p(k) is coprime to p(n+1-k) for k = all positive integers <= n.

1, 2, 2, 16, 16, 192, 192, 6912, 4608, 230400, 230400, 11612160, 11612160, 1199923200, 588349440, 98594979840, 98594979840, 11076328488960, 11076328488960, 2102897147904000, 1076597725593600, 331238941183180800, 331238941183180800, 66325953940291584000, 56326771107377971200

Offset: 1

Author

Leroy Quet, Jan 07 2008

Keywords

• hard
• nonn

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 even, a(n) = A037223(n)*A009679(n/2).

If n is an odd prime, a(n) = a(n-1). (End)

Examples

			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.
		

Links

• Robert Israel, Table of n, a(n) for n = 1..31

Crossrefs

Cf. A009679, A081123, A037223.

Programs

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

Extensions

a(6)-a(15) from Sean A. Irvine, May 17 2010

a(16)-a(25) from Robert Israel, Sep 12 2016