Two ordering problems

[David Wilson]

If we momentarily ignore the problem of finding numerical examples for a 
moment, let P(n) be a set of n distinct symbolic primes (e.g, P(3) = 
{p,q,r}) and let D(n) be the set of divisors of PROD(P(n)) (e.g, D(3) = 
{1,p,q,r,pq,qr,pr,pqr}. We then use the following rules

    [1] 1 < p < q < r < ... < x
    [2] a < b  =>  ac < bc
    [3] (a < b and b < c) => a < c

to induce a partial order G(n) on D(n) (G(n) because it can be 
represented as a graph with nodes D(n)).

The first problem is to count the total orderings of D(n) that conform 
to G(n). I doubt we are the first to consider this problem, I wonder if 
there is an efficient algorithm.

The second problem is whether all of the total orderings can be realized 
by assignment of numerical primes to the variables. Interesting question.


Mitch Harris wrote:
> 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?
>