Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: (Re) Permutations Involving Relatively-Primality
Replies: 3   Last Post: Dec 30, 2002 7:42 AM

 Search Thread: Advanced Search

 Messages: [ Previous | Next ]
 Bill Taylor Posts: 1,909 Registered: 12/8/04
(Re) Permutations Involving Relatively-Primality
Posted: Dec 28, 2002 2:59 AM
 Plain Text Reply

This is way past the thread's use-by date, but I finally got around to this
part of my back-log, and thought Leroy (and others?) might still be faintly
interested. Sorry if followups have already covered it.

Not that I'm sure I'm not sending this into cyber-vacuum anyway -- traffic
seems to have dropped almost to zero! I mean I know it's holiday time
and all, but I don't recall Usenet being QUITE so bereft in previous years.

Anyway, Leroy Quet wrote:

> What is the number of permutations of the first m positive integers where
> GCD(a(k-1), a(k)) = 1

Quite a fun counting problem, in fact.

> With a brute-force counting Mathematica program...
> 1, 2, 6, 12, 72, 72, 864, 1728,...

I managed to varify these by hand, (NOT by listing them all, natch!)
It seems to extend to:

1, 2, 6, 12, 72, 72, 864, 1728, 8928, ... so that...

> Noteworthy: For the terms given, anyway, each term is a multiple of
> the term before it.

...this does not in fact continue to apply. I'm slightly glad it doesn't,
because I couldn't think of any likely semi-reason why it should!

> variation of the question: What if a(m) must also be relatively-prime to a(1) ?

In fact this version is somewhat easier to tackle, by hand at least.
My tentative numbers come out as:

1 2 6 8 60 24 504 576 7776 5760 ...

Interestingly the sequence is no longer monotonic.

Hopefully someone else will take up the baton and run a little further with it?

------------------------------------------------------------------------------
Bill Taylor W.Taylor@math.canterbury.ac.nz
------------------------------------------------------------------------------
Does a political barge horse have to tow the party line?
------------------------------------------------------------------------------

Date Subject Author
12/28/02 Bill Taylor
12/28/02 klaus hoffmann
12/28/02 Leroy Quet
12/30/02 David Franklin

© The Math Forum at NCTM 1994-2018. All Rights Reserved.