OFFSET
0,3
FORMULA
a(p-1) = A086595(p) for prime p. - Max Alekseyev, Jun 12 2005
EXAMPLE
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.
MAPLE
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
# second Maple program:
b:= proc(s, t) option remember; `if`(s={}, 1, add(
`if`(igcd(i, t)>1, 0, b(s minus {i}, i)), i=s))
end:
a:= n-> b({$1..n}, 1009):
seq(a(n), n=0..14); # Alois P. Heinz, Aug 13 2017
MATHEMATICA
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}]
PROG
(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
CROSSREFS
KEYWORD
nonn
AUTHOR
Lior Manor, Nov 04 2002
EXTENSIONS
Extended by Frank Ruskey, Nov 11 2002
a(15)-a(16) from Ray Chandler and Joshua Zucker, Apr 10 2005
a(17)-a(24) from Max Alekseyev, Jun 12 2005
a(0) prepended and a(25) added by Alois P. Heinz, Aug 13 2017
STATUS
approved