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

[Mitch Harris]

From: Frank Ruskey
> 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? 

Has anybody computed them? Probably.
Is it in the OEIS? No.

> A few quick comments on the labelled version of your problem:

I think the labelled version is the more tractable one (and, really, the
symmetries of these lattices are simple enough that the unlabelled
version is a simple consequence)

> 
> 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 a factorization of exactly two prime powers (and hook length), see
A060854

> For the others I don't think there is any known
> formulae.  

That is my impression too, even for only 3 primes.
Of course computable for very small values (the numbers grow really
fast):
For a 2 by 2 by 2 lattice (the divisibility lattice for 30) there are 48
linear extensions.
For a 2 by 2 by 3 there are 2452 (by enumeration).

Note: the 2x2x2 value can be found by hand by simple counting.

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

That is my impression, too. There is a lattice path interpretation (with
suitable path restrictions, Stanley has a short section on this
correspondence). Even for 2x2xk lattices the function is (as far as I
know) unknown.


> To compute these for specific small values,
> you could use my program for generating linear extensions:
> http://www.cs.uvic.ca/~ruskey/Publications/ExtensionFast/Exten
> sionFast.html
> (note that a particular initial labelling of the poset is required).

This will work very small values and # of dimensions. It is very fast 
growing.

The interesting ones 100 and below are
   le(12) = le(18) = 5
   le(24) = le(54) = 14
   le(48) =          42
   le(96) =          132   (Catalan #'s)

   30 = 2*3*5       le = 48
   36 = 2^2*3^2     le = 42
   42 = 2*3*7       le = 48
   60 = 2^2*3*5     le = 2452
   70 = 2*5*7       le = 48
   72 = 2^3*3^2     le = 462
   90 = 2*3^2*5     le = 2452
   100= 2^2*5^2     le = 42

So the sequence starts:

1 1 1 1 1 2 1 1 1 2 1 5 1 2 2 1 1 5 1 5 2 2 1 14 1 2 1 5 1 48 1 1 2 2 2
42 ...

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

for any rooted tree, a recursive function will work: if you have linear
extensions for the subtrees (each of size n_k), the linear extensions
can be interleaved in all possible ways: (n_1+n_2+...+n_k choose n_1 n_2
... n_k)*le(t_1)le(t_2)*...*le(t_k).


Mitch