A005326 Permanent of "coprime?" matrix. (Formerly M2382)

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,3

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.

Formula

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

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

Prog

(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

Crossrefs

Cf. A009679.

Sequence in context: A042829 A232110 A140896 * A298561 A226049 A354844

Adjacent sequences: A005323 A005324 A005325 * A005327 A005328 A005329

Keyword

nonn,nice

Author

N. J. A. Sloane

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

Status

approved