A009679 -id:A009679 - cp's OEIS frontend

A005326 Permanent of "coprime?" matrix.

1, 1, 3, 4, 28, 16, 256, 324, 3600, 3600, 129744, 63504, 3521232, 3459600, 60891840, 91240704, 8048712960, 3554067456, 425476094976, 320265446400, 12474417291264, 16417666704384, 2778580249611264, 1142807773593600, 172593628397420544

Offset: 1

N. J. A. Sloane

Number of permutations p of (1,2,3,...,n) such that k and p(k) are relatively prime for all k in (1,2,3,...,n). - Benoit Cloitre, Aug 23 2002

Coprime matrix M=[m(i,j)] is a square matrix defined by m(i,j)=1 if gcd(i,j)=1 else 0.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Stephen C. Locke, Table of n, a(n) for n = 1..50 (first 30 terms from Seiichi Manyama)
D. M. Jackson, The combinatorial interpretation of the Jacobi identity from Lie algebra, J. Combin. Theory, A 23 (1977), 233-256.
Carl Pomerance, Coprime permutations, arXiv:2203.03085 [math.NT], 2022.
Ashwin Sah and Mehtaab Sawhney, Enumerating coprime permutations, arXiv:2203.06268 [math.NT], 2022.

Cf. A009679.

Jackson2:=proc(n) local m,i,j,M,p,b,s,x;
if 0=(n mod 2) then;
m := n/2;
M := Matrix(m, m, 0);
  for i from 1 to m do for j from 1 to m do;
    if 1= igcd(2*i,2*j-1) then M[i,j]:=1; fi; od; od;
s := LinearAlgebra[Permanent](M);
return s^2;
else;
m := (n + 1)/2;
M := Matrix(m, m, 0);
    for i from 1 to m-1 do for j from 1 to m do;
      if 1=igcd(2*i,2*j-1) then M[i,j]:=1; fi; od; od;
for j to m do
    M[m,j] := x[j];
end do;
p := LinearAlgebra[Permanent](M);
b := [ ];
for j to m do
    b := [op(b), coeff(p, x[j])];
end do;
s := 0;
  for i from 1 to m do for j from 1 to m do;
    if 1=igcd(2*i-1,2*j-1) then s:=s+b[i]*b[j]; fi; od; od; fi;
return s;
end;
seq(Jackson2(n), n=1..25); # Stephen C. Locke, Feb 24 2022

perm[m_?MatrixQ] := With[{v = Array[x, Length[m]]}, Coefficient[Times @@ (m.v), Times @@ v]]; a[n_] := perm[ Table[ Boole[GCD[i, j] == 1], {i, 1, n}, {j, 1, n}]]; Table[an = a[n]; Print[an]; an, {n, 1, 24}] (* Jean-François Alcover, Nov 15 2011 *)
(* or, if version >= 10: *)
a[n_] := Permanent[Table[Boole[GCD[i, j] == 1], {i, 1, n}, {j, 1, n}]]; Table[an = a[n]; Print[an]; an, {n, 1, 24}] (* Jean-François Alcover, Jul 25 2017 *)

permRWNb(a)=n=matsize(a)[1]; if(n==1,return(a[1,1])); sg=1; nc=0; in=vectorv(n); x=in; x=a[,n]-sum(j=1,n,a[,j])/2; p=prod(i=1,n,x[i]); for(k=1,2^(n-1)-1,sg=-sg; j=valuation(k,2)+1; z=1-2*in[j]; in[j]+=z; nc+=z; x+=z*a[,j]; p+=prod(i=1,n,x[i],sg)); return(2*(2*(n%2)-1)*p)
for(n=1,26,a=matrix(n,n,i,j,gcd(i,j)==1); print1(permRWNb(a)",")) \\ Herman Jamke (hermanjamke(AT)fastmail.fm), May 13 2007

a(2n) = A009679(n)^2. - T. D. Noe, Feb 10 2007

Corrected by Vladeta Jovovic, Jul 05 2003
More terms from T. D. Noe, Feb 10 2007
a(25) from Alois P. Heinz, Nov 15 2016

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.

Original entry on oeis.org

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

Leroy Quet, Jan 07 2008

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)

			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.

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

Cf. A009679, A081123, A037223.

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

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

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

cp's OEIS Frontend

A005326 Permanent of "coprime?" matrix.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions