<div> </div>
<div>I wrote:<br>(and below I add some quick comments for those who would like to compute these in a "brute force" fashion. It might be that</div>
<div>only after the Christmas I will time to delve here more deeply.</div>
<div>Meanwhile, thanks for all the comments!)</div>
<div> </div>
<blockquote class="gmail_quote" style="PADDING-LEFT: 1ex; MARGIN: 0px 0px 0px 0.8ex; BORDER-LEFT: #ccc 1px solid"><br>><br>> Has anybody computed (i.e. is it in the OEIS?) the number of<br>> linear extension for the divisor lattice of each natural number n?
<br>> I.e. 36 has a divisibility lattice like this:<br>><br>> (Please see with a fixed width font, e.g. a Courier):<br>><br>> ...36<br>> .../.\<br>> .12..18<br>> ./.\./.\<br>> 4...6...9<br>> .\./.\./
<br>> ..2...3<br>> ...\./<br>> ....1<br>><br>> and one possible way to fill it with numbers 1-9<br>> in such a way, that never is a greater number<br>> beneath the smaller one, is for example this:<br>
><br>> ....9<br>> .../.\<br>> ..6...8<br>> ./.\./.\<br>> 5...4...7<br>> .\./.\./<br>> ..2...3<br>> ...\./<br>> ....1<br>></blockquote>
<div> </div>
<div>I realize that I used the term "beneath" very vaguely.</div>
<div>More technical phrase might be "never in the _same chain_</div>
<div>are two numbers situated so, that the greater of them</div>
<div>is located nearer to the greatest common element</div>
<div>than the smaller one" (common "meet", the "bottom").</div>
<div> </div>
<div>So this should be also a valid linear extension:</div>
<div> </div>
<div>> ....9<br>> .../.\<br>> ..6...8<br>> ./.\./.\<br>> 3...5...7<br>> .\./.\./<br>> ..2...4<br>> ...\./<br>> ....1<br> </div>
<div>So those who would like to compute the labeled version(s)</div>
<div>of these sequences, but do not care learn all this "posetological"</div>
<div>lattice jargon, it is enough to do this:</div>
<div> </div>
<div>Factor a natural number n into its divisors. If there are only</div>
<div>one or two, then it is 1 or a prime, in which case there are</div>
<div>exactly one solution. Otherwise, discard the tirivial divisors</div>
<div>1 and n itself, leaving tau(n)-2 divisors d_i,...,d_k (where tau = A000005),</div>
<div>and pair them with integers 1..(tau(n)-2): i_i,...,i_k</div>
<div>in such a way, that if d_i divides d_j, then</div>
<div>for their corresponding integers</div>
<div>i_i and i_j it holds that i_i <= i_j.</div>
<div> </div>
<div>Do this in some sensible experimental way, that</div>
<div>there is no need to generate all (tau(n)-2)! different</div>
<div>permutations.</div>
<div> </div>
<div>A nice project for Mathematica buffs?</div>
<div> </div>
<div>Use </div>
<div><a href="http://www.research.att.com/projects/OEIS?Anum=A025487">http://www.research.att.com/projects/OEIS?Anum=A025487</a></div>
<div>if you want to avoid computing duplicate cases.</div>
<div> </div>
<div>Yours again,</div>
<div> </div>
<div>Antti</div>
<div><br> </div>
<blockquote class="gmail_quote" style="PADDING-LEFT: 1ex; MARGIN: 0px 0px 0px 0.8ex; BORDER-LEFT: #ccc 1px solid">> How many such solutions ("linear extensions")<br>> there are at all for this lattice/poset?
<br>> How many for the divisor lattice of<br>> each n, for n=1,2,3,4,5,6,7,...<br>> This should begin 1,1,1,1,1,1,1,1,<br>> if we consider<br>> ..4<br>> ./.\<br>> 2...3<br>> .\./<br>> ..1<br>> the same linear extension as
<br>> ..4<br>> ./.\<br>> 3...2<br>> .\./<br>> ..1<br>> but 1,1,1,1,1,2,1,1,1,2,1,...<br>> if they are considered different. (E.g. 6 and 10 has<br>> this as their divisor lattice).<br>><br>> These two functions would be nice to see computed also for each A025487(n)
<br>> <a href="http://www.research.att.com/projects/OEIS?Anum=A025487">http://www.research.att.com/projects/OEIS?Anum=A025487</a><br>> which gives only minimal representatives of each<br>> divisor lattice, so each one is unique.
<br>> (Note for example that the nth primorial in that sequence has<br>> a n-dimensional hypercube as its divisor lattice).<br>><br>> I'm also interested about the number of linear extension of other<br>> simple graphs that can be used as posets, 
e.g. the "full binary trees"<br>> like these:<br>><br>> \./<br>><br>> \./   \./<br>>   \    /<br>>     \/<br>><br>> etc. (of 3, 7, 15, 31, 63, etc. vertices). In how many ways each one of them
<br>> can be "extended linearly"?<br>><br>><br>><br>> Terveisin,<br>><br>> Antti Karttunen<br><br><br>--<br>----------------------<br>Frank Ruskey             e-mail: (last_name)(AT)cs(DOT)uvic(DOT)ca
<br>Dept. of Computer Science      fax:    250-721-7292<br>University of Victoria         office: 250-721-7232<br>Victoria, B.C. V8W 3P6 CANADA  WWW: <a href="http://www.cs.uvic.ca/~(last_name)">http://www.cs.uvic.ca/~(last_name)
</a><br><br></blockquote><br>