Two ordering problems

[franktaw at netscape.net]

I'm pretty sure that  
http://www.research.att.com/~njas/sequences/A009997 is the
desired sequence.  This can be interpreted as linear extensions of the 
lattice 2^n
induced by assigning a weight to each primitive element, and taking the 
sum for the
other nodes.  Taking the log of each divisor, we just need to match the 
relative
ordering of the sums.

I don't really see how to prove the final step, but the primes are 
pretty dense.  I
would be astonished if any such arrangement cannot be obtained.

----
One can also generalize this question: given a partition P, how many 
orderings of
the divisors are possible for a number whose prime signature is P?  For 
example,
for [2,1] we are looking at numbers of the form p^2 q; possible 
orderings are

12: 1, p, q, p^2, pq, p^2q
18: 1, q, p, pq, p^2, p^2q
20: 1, p, p^2, q, pq, p^2q

Further subdividing to compositions, two of these -- 12 and 20 -- 
correspond to
<2,1>, while 18 corresponds to <1,2>.

Franklin T. Adams-Watters

-----Original Message-----
From: Mitch Harris <maharri at gmail.com>

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