%I A076220
%S A076220 1,2,6,12,72,72,864,1728,13824,22032,555264,476928,17625600,29599488,
%T A076220 321115392,805146624,46097049600,36481536000,2754120268800,
%U A076220 3661604352000,83905105305600,192859121664000,20092043520000000,15074060547686400
%N A076220 Number of permutations of 1..n in which every pair of adjacent numbers 
               are relatively prime.
%F A076220 a(p-1)=A086595(p) for prime p. - Max Alekseyev (maxale(AT)gmail.com), 
               Jun 12 2005
%e A076220 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 A076220 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); (Deutsch)
%t A076220 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 A076220 (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} (Alekseyev)
%Y A076220 Cf. A086595.
%Y A076220 Sequence in context: A106037 A136240 A090747 this_sequence A107763 A166470 
               A144144
%Y A076220 Adjacent sequences: A076217 A076218 A076219 this_sequence A076221 A076222 
               A076223
%K A076220 nonn
%O A076220 1,2
%A A076220 Lior Manor (lior.manor(AT)gmail.com) Nov 04 2002
%E A076220 Extended by Frank Ruskey (fruskey(AT)cs.uvic.ca), Nov 11 2002
%E A076220 a(15)=321115392 and a(16)=805146624 from Ray Chandler (rayjchandler(AT)sbcglobal.net) 
               and Joshua Zucker (joshua.zucker(AT)stanfordalumni.org), Apr 10 2005
%E A076220 Many further terms from Max Alekseyev (maxale(AT)gmail.com), Jun 12 2005