# Two ordering problems

Mitch Harris maharri at gmail.com
Thu Aug 28 23:05:49 CEST 2008

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...

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