[SeqFan] Number of linear extensions of divisibility lattices and of other posets?

[Antti Karttunen]

I wrote:
(and below I add some quick comments for those who would like to compute
these in a "brute force" fashion. It might be that
only after the Christmas I will time to delve here more deeply.
Meanwhile, thanks for all the comments!)


>
> >
> > Has anybody computed (i.e. is it in the OEIS?) the number of
> > linear extension for the divisor lattice of each natural number n?
> > I.e. 36 has a divisibility lattice like this:
> >
> > (Please see with a fixed width font, e.g. a Courier):
> >
> > ...36
> > .../.\
> > .12..18
> > ./.\./.\
> > 4...6...9
> > .\./.\./
> > ..2...3
> > ...\./
> > ....1
> >
> > and one possible way to fill it with numbers 1-9
> > in such a way, that never is a greater number
> > beneath the smaller one, is for example this:
> >
> > ....9
> > .../.\
> > ..6...8
> > ./.\./.\
> > 5...4...7
> > .\./.\./
> > ..2...3
> > ...\./
> > ....1
> >


I realize that I used the term "beneath" very vaguely.
More technical phrase might be "never in the _same chain_
are two numbers situated so, that the greater of them
is located nearer to the greatest common element
than the smaller one" (common "meet", the "bottom").

So this should be also a valid linear extension:

> ....9
> .../.\
> ..6...8
> ./.\./.\
> 3...5...7
> .\./.\./
> ..2...4
> ...\./
> ....1

So those who would like to compute the labeled version(s)
of these sequences, but do not care learn all this "posetological"
lattice jargon, it is enough to do this:

Factor a natural number n into its divisors. If there are only
one or two, then it is 1 or a prime, in which case there are
exactly one solution. Otherwise, discard the tirivial divisors
1 and n itself, leaving tau(n)-2 divisors d_i,...,d_k (where tau = A000005),
and pair them with integers 1..(tau(n)-2): i_i,...,i_k
in such a way, that if d_i divides d_j, then
for their corresponding integers
i_i and i_j it holds that i_i <= i_j.

Do this in some sensible experimental way, that
there is no need to generate all (tau(n)-2)! different
permutations.

A nice project for Mathematica buffs?

Use
http://www.research.att.com/projects/OEIS?Anum=A025487
if you want to avoid computing duplicate cases.

Yours again,

Antti



> > How many such solutions ("linear extensions")
> > there are at all for this lattice/poset?
> > How many for the divisor lattice of
> > each n, for n=1,2,3,4,5,6,7,...
> > This should begin 1,1,1,1,1,1,1,1,
> > if we consider
> > ..4
> > ./.\
> > 2...3
> > .\./
> > ..1
> > the same linear extension as
> > ..4
> > ./.\
> > 3...2
> > .\./
> > ..1
> > but 1,1,1,1,1,2,1,1,1,2,1,...
> > if they are considered different. (E.g. 6 and 10 has
> > this as their divisor lattice).
> >
> > These two functions would be nice to see computed also for each
> A025487(n)
> > http://www.research.att.com/projects/OEIS?Anum=A025487
> > which gives only minimal representatives of each
> > divisor lattice, so each one is unique.
> > (Note for example that the nth primorial in that sequence has
> > a n-dimensional hypercube as its divisor lattice).
> >
> > I'm also interested about the number of linear extension of other
> > simple graphs that can be used as posets, e.g. the "full binary trees"
> > like these:
> >
> > \./
> >
> > \./   \./
> >   \    /
> >     \/
> >
> > etc. (of 3, 7, 15, 31, 63, etc. vertices). In how many ways each one of
> them
> > can be "extended linearly"?
> >
> >
> >
> > Terveisin,
> >
> > Antti Karttunen
>
>
> --
> ----------------------
> Frank Ruskey             e-mail: (last_name)(AT)cs(DOT)uvic(DOT)ca
> Dept. of Computer Science      fax:    250-721-7292
> University of Victoria         office: 250-721-7232
> Victoria, B.C. V8W 3P6 CANADA  WWW: http://www.cs.uvic.ca/~(last_name)
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20051217/96c36f74/attachment-0001.htm>