A005326 - OEIS

%I M2382 #64 Mar 18 2023 08:49:14

%S 1,1,3,4,28,16,256,324,3600,3600,129744,63504,3521232,3459600,

%T 60891840,91240704,8048712960,3554067456,425476094976,320265446400,

%U 12474417291264,16417666704384,2778580249611264,1142807773593600,172593628397420544

%N Permanent of "coprime?" matrix.

%C 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

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

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

%H Stephen C. Locke, <a href="/A005326/b005326.txt">Table of n, a(n) for n = 1..50</a> (first 30 terms from Seiichi Manyama)

%H D. M. Jackson, <a href="http://dx.doi.org/10.1016/0097-3165(77)90016-4">The combinatorial interpretation of the Jacobi identity from Lie algebra</a>, J. Combin. Theory, A 23 (1977), 233-256.

%H Carl Pomerance, <a href="https://arxiv.org/abs/2203.03085">Coprime permutations</a>, arXiv:2203.03085 [math.NT], 2022.

%H Ashwin Sah and Mehtaab Sawhney, <a href="https://arxiv.org/abs/2203.06268">Enumerating coprime permutations</a>, arXiv:2203.06268 [math.NT], 2022.

%F a(2n) = A009679(n)^2. - _T. D. Noe_, Feb 10 2007

%p Jackson2:=proc(n) local m,i,j,M,p,b,s,x;

%p if 0=(n mod 2) then;

%p m := n/2;

%p M := Matrix(m, m, 0);

%p   for i from 1 to m do for j from 1 to m do;

%p     if 1= igcd(2*i,2*j-1) then M[i,j]:=1; fi; od; od;

%p s := LinearAlgebra[Permanent](M);

%p return s^2;

%p else;

%p m := (n + 1)/2;

%p M := Matrix(m, m, 0);

%p     for i from 1 to m-1 do for j from 1 to m do;

%p       if 1=igcd(2*i,2*j-1) then M[i,j]:=1; fi; od; od;

%p for j to m do

%p     M[m,j] := x[j];

%p end do;

%p p := LinearAlgebra[Permanent](M);

%p b := [ ];

%p for j to m do

%p     b := [op(b), coeff(p, x[j])];

%p end do;

%p s := 0;

%p   for i from 1 to m do for j from 1 to m do;

%p     if 1=igcd(2*i-1,2*j-1) then s:=s+b[i]*b[j]; fi; od; od; fi;

%p return s;

%p end;

%p seq(Jackson2(n), n=1..25); # _Stephen C. Locke_, Feb 24 2022

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

%t (* or, if version >= 10: *)

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

%o (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)

%o 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

%Y Cf. A009679.

%K nonn,nice

%O 1,3

%A _N. J. A. Sloane_

%E Corrected by _Vladeta Jovovic_, Jul 05 2003

%E More terms from _T. D. Noe_, Feb 10 2007

%E a(25) from _Alois P. Heinz_, Nov 15 2016