|
|
A005326
|
|
Permanent of "coprime?" matrix.
(Formerly M2382)
|
|
7
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
FORMULA
|
|
|
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;
|
|
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
|
|
|
STATUS
|
approved
|
|
|
|