Permutations Involving Relatively-Primality

Leroy Quet qqquet at mindspring.com
Tue Nov 12 04:43:06 CET 2002

```>I don't know the answer to your nice question, but here are some
>more numbers (up to n=14).
>1, 2, 6, 12, 72, 72, 864, 1728, 13824, 22032, 555264,
>476928, 17625600, 29599488
>Worthy of note: (a) the numbers are not montone, (b) the multiplicity
>property noted below disappears.
>
>-Frank R.
>

Interesting. I am glad that this confirms my original values for the
sequence.
And I won't waste my time looking for an INTEGER sequence which
represents each term divided by the previous term.

(My instinct is that this sequence is less likely to increase at n with
many divisors.)

Thanks,
Leroy Quet

>
>Leroy Quet wrote:
>> 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
>>

```