A094206 a(n) = number of consistent orderings of 1..n based only on factorization.

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

Offset

1,4

Comments

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 two rules:

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.

Rule 2 captures certain intuitive requirements for ordering products - for example specializing A=[1] and C=D captures the idea that "multiples are larger", etc. Sequence gives number of ways of consistently ordering [1]..[n].

Links

Table of n, a(n) for n=1..20.

Example

Up to n=3 there's only one way: [1], [1][2], [1][2][3], but then for n=4=2^2 the rules do not 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].

Crossrefs

Sequence in context: A354141 A379694 A105180 * A278119 A118998 A276410

Adjacent sequences: A094203 A094204 A094205 * A094207 A094208 A094209

Keyword

nonn,nice,more

Author

Marc LeBrun, May 04 2004

Status

approved