Permutations Involving Relatively-Primality

[Leroy Quet]

Though not in the data-base when I last checked (at the beginning of 
November), the sequence was soon after added by Lior Manor (sequence 
A076220).

Leroy Quet

----
>Just posted this to sci.math too.
>
>---------------------
>This was bugging me recently. I thought the solution would be simple.
>And after several false solutions, I have finally given up.
>
>What is the number of permutations of the first m positive integers
>where
>
>GCD(a(k-1), a(k)) = 1
>
>for all k, 2 <= k <= m,
>where a(k) is the k_th ordered element of each permutation?
>
>For example, if m = 5,
>then: 1, 3, 2, 5, 4 
>is one of the permutations that I wish to count, while:
>1, 3, 2, 4, 5
>is not. (2 and 4 next to each other)
>
>With a brute-force counting Mathematica program,
>I get the number-of-these-particular-permutations sequence beginning:
>
>1, 2, 6, 12, 72, 72, 864, 1728,...
>
>Noteworthy: For the terms given, anyway, each term is a multiple of
>the term before it.
>
>A variation of the question: What if a(1) must be relatively-prime to
>a(m) as well?
>
>Thanks,
>Leroy Quet
>