Two ordering problems

franktaw at netscape.net franktaw at netscape.net
Fri Aug 29 01:05:11 CEST 2008

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

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

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

```