Permutations: Adjacent Elements Are Coprime

[Emeric Deutsch]

Here is my rudimentary Maple program with the first 7 terms:

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);

                        1, 2, 6, 12, 72, 72, 864

Emeric




On Mon, 28 Mar 2005, Leroy Quet wrote:

> I wrote to seq.fan about this a while back, perhaps, but I cannot
> remember what kind of replies, if any, I received.
>
> Could someone calculate/submit the sequence, if it is not already in the
> database, where the nth term is the number of permutations of
> (1,2,3,...,n) where each integer is coprime with its closest neighbors in
> the permutation.
>
>
> I get, by hand (so I might have made a mistake), the sequence beginning:
> 1,2,6,12,72,68,...
>
> For example,
>
> for n = 6, we can have in the count the permutation
> 5,4,3,2,1,6,
>
> but not the permutation
> 2,5,4,1,6,3
> (because here 3 is adjacent with 6).
>
> thanks,
> Leroy Quet
>
>