Two ordering problems

[Mitch Harris]

On Tue, Aug 26, 2008 at 9:39 AM, David Wilson <dwilson at gambitcomm.com> wrote:
> Problem 2:
>
> Let p1 < p2 < ... < p_n be primes (call p1 = p, p2 = q, p3 = r, ...)
>
> Consider the set M of divisors of p1*p2*...*p_n. How many ways can M be
> ordered?
>
> For n = 0, we have m = { 1 }, with 1 ordering.
>
> For n = 1, we have M = { 1, p }. There is 1 possible ordering, 1 < p.
>
> For n = 2, we have M = { 1, p, q, pq }. Remembering p < q, there is again 1
> possible ordering, 1 < p < q < pq.
>
> For n = 3, we have M = { 1, p, q, r, pq, pr, qr, pqr }. There are 2 possible
> orderings here
>
> 1 < p < q < r < pq < pr < qr < pqr
> 1 < p < q < pq < r < pr < qr < pqr
>
> How many possible orderings are there for larger n?

Interesting.

For n = 3, two canonical examples are:

(2,3,5) = 30: 1, 2, 3, 5, 6, 10, 15, 30...

(2,3,7) = 42: 1, 2, 3, 6, 7, 10, 14, 21...

Forgetting numbers and divisibility for the moment, we can start with
the number of linear extensions of the boolean lattice 2^n:

 http://www.research.att.com/~njas/sequences/A046873

which starts:

 1, 2, 48, 1680384, 14807804035657359360

The latter is labeled. The sequence for unlabeled, closer but not
necessarily equivalent to yours, is, as far as I can tell, not in the
OEIS (and frankly labeled or not, that seems a hard problem (either
theoretically or just enumerating by computer)). This would also be an
interesting sequence to have.

But adding divisibility back in (for more constraints), it might be
easier. For n=4, the -unlabeled- case (closer to yours) I get:

 1, 1, 2, ... arghhh

by hand, this hurts. With a little thought... it's dual, so if the 2^n
length sequence goes 1,a,b,c...d,e,f,n, then f = n/a, e = n/b, c =
n/d... so only nonisomorphic sequences of length 7 need be considered.

So, by hand for n = 4 I found 14 nonisomorphic possibilities:

1155 = {3, 5, 7, 11}:  1, {p}, {q}, {r},    {s},    {p, q}, {p, r}, {p, s}
1365 = {3, 5, 7, 13}:  1, {p}, {q}, {r},    {s},    {p, q}, {p, r}, {q, r}
5313 = {3, 7, 11, 23}: 1, {p}, {q}, {r},    {p, q}, {s},    {p, r}, {p, s}
1785 = {3, 5, 7, 17}:  1, {p}, {q}, {r},    {p, q}, {s},    {p, r}, {q, r}
4466 = {2, 7, 11, 29}: 1, {p}, {q}, {r},    {p, q}, {p, r}, {s},    {p, s}
2030 = {2, 5, 7, 29}:  1, {p}, {q}, {r},    {p, q}, {p, r}, {s},    {q, r}
870 =  {2, 3, 5, 29}:  1, {p}, {q}, {r},    {p, q}, {p, r}, {q, r}, {s}
930 =  {2, 3, 5, 31}:  1, {p}, {q}, {r},    {p, q}, {p, r}, {q, r}, {p, q, r}
858 =  {2, 3, 11, 13}: 1, {p}, {q}, {p, q}, {r},    {s},    {p, r}, {p, s}
462 =  {2, 3, 7, 11}:  1, {p}, {q}, {p, q}, {r},    {s},    {p, r}, {q, r}
2530 = {2, 5, 11, 23}: 1, {p}, {q}, {p, q}, {r},    {p, r}, {s},    {p, s}
714 =  {2, 3, 7, 17}:  1, {p}, {q}, {p, q}, {r},    {p, r}, {s},    {q, r}
966 =  {2, 3, 7, 23}:  1, {p}, {q}, {p, q}, {r},    {p, r}, {q, r}, {s}
1806 = {2, 3, 7, 43}:  1, {p}, {q}, {p, q}, {r},    {p, r}, {q, r}, {p, q, r}

(fixed font view is better)

The only relevant entries in the OEIS are:

 http://www.research.att.com/~njas/sequences/A005806
 http://www.research.att.com/~njas/sequences/A009997

but I highly doubt that the higher entries are right for this
problem.(something in these latter sequences might be relevant for the
nonisomorphic -unlabeled- boolean lattices)

I can't see any informal reason why there -must- be a selection of
primes for any particular ordering of the lattice though, it could be
difficult to get a set of primes of just the right magnitude to get
any particular ordering for large n (so your desired sequence would be
different from the unlabeled linear extensions of 2^n). On the other
hand, it wasn't too difficult to come up with the examples above by
hand.

Any ideas about less 'experimental ways of counting these? any more constraints?
--
Mitch Harris



-- 
Mitch Harris