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

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

Author

Lior Manor, Nov 04 2002

Keywords

• nonn

Examples

			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.
		

Crossrefs

Cf. A086595.

Programs

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}]

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

Formula

a(p-1) = A086595(p) for prime p. - Max Alekseyev, Jun 12 2005

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