Permutations Involving Relatively-Primality

[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