login
This site is supported by donations to The OEIS Foundation.

 

Logo


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

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

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

License Agreements, Terms of Use, Privacy Policy .

Last modified September 26 10:59 EDT 2017. Contains 292518 sequences.