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

[Frank Ruskey]

Dear Antti,
A few quick comments on the labelled version of your problem:

For prime powers the answer will be 1.

For numbers of the form p^n*q^m with p and q prime
the answer will be easily computable from the
hook-length formula for standard Young Tableau.

For the others I don't think there is any known
formulae.  E.g., for the boolean lattice,
which you get when all the primes in the factorization
occur with exponent 1, there is no formula, just asymptotics.
To compute these for specific small values,
you could use my program for generating linear extensions:
http://www.cs.uvic.ca/~ruskey/Publications/ExtensionFast/ExtensionFast.html
(note that a particular initial labelling of the poset is required).

Regarding your last question, there is a "hook-length"
formula for trees (with a much easier proof).
You divide by the product of the subtree sizes, rather
than the product of the hook-lengths.

Cheers,
Frank


Antti Karttunen wrote:
>  
> 
> 
> ------------------------------------------------------------------------
> 
> 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
> 
> 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)