A076220 - OEIS

%I #28 Aug 13 2017 22:45:02

%S 1,1,2,6,12,72,72,864,1728,13824,22032,555264,476928,17625600,

%T 29599488,321115392,805146624,46097049600,36481536000,2754120268800,

%U 3661604352000,83905105305600,192859121664000,20092043520000000,15074060547686400,1342354557616128000

%N Number of permutations of 1..n in which every pair of adjacent numbers are relatively prime.

%F a(p-1) = A086595(p) for prime p. - _Max Alekseyev_, Jun 12 2005

%e a(4) = 12 since there are 12 permutations of 1234 in which every 2 adjacent numbers are relatively prime: 1234, 1432, 2134, 2143, 2314, 2341, 3214, 3412, 4123, 4132, 4312, 4321.

%p with(combinat): for n from 1 to 7 do P:=permute(n): ct:=0: for j from 1 to n! do if add(gcd(P[j][i+1],P[j][i]),i=1..n-1)=n-1 then ct:=ct+1 else ct:=ct fi od: a[n]:=ct: od: seq(a[n],n=1..7); # _Emeric Deutsch_, Mar 28 2005

%p # second Maple program:

%p b:= proc(s, t) option remember; `if`(s={}, 1, add(

%p       `if`(igcd(i, t)>1, 0, b(s minus {i}, i)), i=s))

%p     end:

%p a:= n-> b({$1..n}, 1009):

%p seq(a(n), n=0..14);  # _Alois P. Heinz_, Aug 13 2017

%t f[n_] := Block[{p = Permutations[ Table[i, {i, 1, n}]], c = 0, k = 1}, While[k < n! + 1, If[ Union[ GCD @@@ Partition[p[[k]], 2, 1]] == {1}, c++ ]; k++ ]; c]; Do[ Print[ f[n]], {n, 2, 15}]

%o (PARI) {A076220(n)=local(A, d, n, r, M); A=matrix(n,n,i,j,if(gcd(i,j)==1,1,0)); r=0; for(s=1,2^n-1,M=vecextract(A,s,s)^(n-1);d=matsize(M)[1];r+=(-1)^(n-d)*sum(i=1,d,sum(j=1,d,M[i,j])));r} \\ _Max Alekseyev_, Jun 12 2005

%Y Cf. A086595.

%K nonn

%O 0,3

%A _Lior Manor_, Nov 04 2002

%E Extended by _Frank Ruskey_, Nov 11 2002

%E a(15)-a(16) from _Ray Chandler_ and _Joshua Zucker_, Apr 10 2005

%E a(17)-a(24) from _Max Alekseyev_, Jun 12 2005

%E a(0) prepended and a(25) added by _Alois P. Heinz_, Aug 13 2017