Permutations: Adjacent Elements Are Coprime

[Emeric Deutsch]

P.S.
       1, 2, 6, 12, 72, 72, 864, 1728



On Mon, 28 Mar 2005, Emeric Deutsch wrote:

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