Permutations Involving Relatively-Primality

[Frank Ruskey]

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.


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
>  


-- 
----------------------
Frank Ruskey                     e-mail: fruskey at cs.uvic.ca <- NEW!
Dept. of Computer Science        fax:    250-721-7292
University of Victoria           office: 250-721-7232
Victoria, B.C. V8W 3P6 CANADA    WWW: http://www.cs.uvic.ca/~fruskey