"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