The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A076220 Number of permutations of 1..n in which every pair of adjacent numbers are relatively prime. 11
 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 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,3 LINKS 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 Adjacent sequences:  A076217 A076218 A076219 * A076221 A076222 A076223 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified April 21 23:52 EDT 2021. Contains 343156 sequences. (Running on oeis4.)