"factoids" anyone?

Marc LeBrun mlb at fxpt.com
Wed May 5 01:38:54 CEST 2004


Can anyone help check/extend the following (not yet in OEIS) sequence

1 1 1 2 3 5 9 25 66 158 424 1048 2445 5736 17069 88674 241698 648786 
1600339 5379356...

defined roughly as a(n) = "the number of consistent orderings of 1..n based 
only on factorization"?

Take a set of objects [n] indexed by the positive integers which multiply 
so that

   [a] [b] = [ab]

(which automatically makes them commute, associate, obey 
gcd([a],[b])=[gcd(a,b)] etc)

and also partially define a consistent ordering relation < to obey

   Rule 1:  p<q ==> [p] < [q], for primes p,q

and

   Rule 2:  A<B, C<D ==> AC < BD, for any objects A, B, C, D.

(I *think* this Rule 2 captures all the intuitive requirements for ordering 
products--for example specializing A=[1] and B=D captures the idea that 
"multiples are larger", etc.--but I'm open to other suggestions.)

Anyway, given this, how many ways are there of consistently ordering [1]..[n]?

Up to n=3 there's only one way:
[1]
[1][2]
[1][2][3]
but then for n=4=2^2 the rules don't say whether [3]<[4] or [4]<[3], 
although they do say that [2]<[4], so we get two orderings
[1][2][3][4], [1][2][4][3]
and things get complicated from there, because the lattice of orderings is 
richly and chaotically structured.  For example the ordering of [6] and [8] 
depends on the ordering of [3] and [4], but [7] only need be > [5] (which 
in turn is > [3] etc).


For fun, I like to abbreviate these "ordered commutative groupoids" to 
"factoids", as their orderings are constrained only by the factorization 
structure.

 From earlier comments on this list I think others may have studied this, 
but either I miscounted or this sequence needs to be added to the 
OEIS.  And my naive program ran out of memory on n=21.  Any help is 
appreciated...

Thanks!







More information about the SeqFan mailing list