[SeqFan] Number of linear extensions of divisibility lattices? A shorter definition.

[Antti Karttunen]

On 12/17/05, Antti Karttunen <antti.karttunen at gmail.com> wrote:

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

I realize that i ja j look extremely similar on some fonts,
so let's rephrase this as:

... in such a way, that if d_i divides d_k, then for their corresponding
integers
i_i and i_k it holds that i_i <= i_k.

But, fortunately, there is even more succinct way to put this:
"How many ways there are arrange the divisors of n, in such a way,
that no divisor has any of _its own_ divisors following after it."
(or equally "... has all its divisors before it".)

E.g. for 12, the following five arrangements are possible:

1,2,3,4,6,12
1,2,3,6,4,12
1,2,4,3,6,12
1,3,2,4,6,12
1,3,2,6,4,12

but e.g.
1,2,6,4,3,12
is not possible, because 3 divides 6 but follows after it.

Mitch Harris had already computed this to begin as:
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
...
but I'm afraid that I have no time to submit it before January.
If anybody wants to do it meanwhile, please go ahead.


-- Same.

And rest of my old comments still apply:


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.
>
>
>
> > 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:
> >
>
> ...
>
>
>
>
> > > 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
> >
> >
> >
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20051221/3f96d391/attachment.htm>