More Permuations & Inverses & Coprime Pairs

[Max]

On 3/25/06, Leroy Quet <qq-quet at mindspring.com> wrote:

> I was wondering what the sequence is where the nth term is the number of
> permutations, {b(k)}, of {1,2,3,...n} where each inverse permutation
> {c(k)}, is such that
> GCD(b(k),c(k)) = 1 for all k, 1<=k<=n.

It worth to mention that the square of such permutation is a
permutation {d(k)} where GCD(k,d(k))=1 for all k=1..n, and vice verse.
The number of such permutations {d(k)} is given by A005326.

> For example: If we have the permutation (for n=4) 2,4,1,3, its inverse is
> 3,1,4,2.
> Since GCD(2,3) = GCD(4,1) = GCD(1,4) = GCD(3,2) = 1, then these two
> permutations of 1,2,3,4 are included in the count.

The square of (2,4,1,3) is (4,3,2,1) with GCD(1,4)=1, GCD(2,3)=1,
GCD(3,2)=1, GCD(4,1).

> Another permutation of 1,2,3,4, however, is 2,3,4,1 with an inverse of
> 4,1,2,3.
> Sonce GCD(2,4) = 2, these two permutations are not counted.

The square (2,3,4,1) is (3,4,1,2) that breaks the property since GCD(2,4)=2.

Max