login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A076220
Number of permutations of 1..n in which every pair of adjacent numbers are relatively prime.
15
1, 1, 2, 6, 12, 72, 72, 864, 1728, 13824, 22032, 555264, 476928, 17625600, 29599488, 321115392, 805146624, 46097049600, 36481536000, 2754120268800, 3661604352000, 83905105305600, 192859121664000, 20092043520000000, 15074060547686400, 1342354557616128000
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
Cf. A086595.
Sequence in context: A136240 A090747 A287142 * A258213 A178846 A173843
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