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.
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
KEYWORD
nonn,nice
AUTHOR
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