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,3

Links

Table of n, a(n) for n=0..25.

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