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

Author

N. J. A. Sloane

Keywords

• nonn
• nice

Comments

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.

References

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

Links

• 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.

Crossrefs

Cf. A009679.

Programs

Maple

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

Mathematica

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 *)

PARI

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

Formula

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

Extensions

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