<br><br><div><span class="gmail_quote">On 12/17/05, <b class="gmail_sendername">Antti Karttunen</b> <<a href="mailto:antti.karttunen@gmail.com">antti.karttunen@gmail.com</a>> wrote:</span><div><br>
<br>
</div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<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>
</blockquote><div><br>
I realize that i ja j look extremely similar on some fonts,<br>
so let's rephrase this as:<br>
<br>
... in such a way, that if d_i divides d_k, then
<div>for their corresponding integers</div>
<div>i_i and i_k it holds that i_i <= i_k.<br>
<br>
But, fortunately, there is even more succinct way to put this:<br>
"How many ways there are arrange the divisors of n, in such a way,<br>
that no divisor has any of _its own_ divisors following after it."<br>
(or equally "... has all its divisors before it".)<br>
<br>
E.g. for 12, the following five arrangements are possible:<br>
<br>
1,2,3,4,6,12<br>
1,2,3,6,4,12<br>
1,2,4,3,6,12<br>
1,3,2,4,6,12<br>
1,3,2,6,4,12<br>
<br>
but e.g.<br>
1,2,6,4,3,12<br>
is not possible, because 3 divides 6 but follows after it.<br>
<br>
Mitch Harris had already computed this to begin as:<br>
<span class="q">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 ...</span><br>
but I'm afraid that I have no time to submit it before January.<br>
If anybody wants to do it meanwhile, please go ahead.<br>
<br>
<br>
-- Same.<br>
<br>
And rest of my old comments still apply:<br>
<br>
</div>
</div><br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<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>
<span class="q">
<div><a href="http://www.research.att.com/projects/OEIS?Anum=A025487" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">http://www.research.att.com/projects/OEIS?Anum=A025487</a></div></span>
<div>if you want to avoid computing duplicate cases.</div>
<div> </div>
<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"><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><span class="q">
<div> </div>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0px 0px 0px 0.8ex; padding-left: 1ex;"><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></span>
<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></blockquote>
<br>
...<br>
<br>
<div><span class="e" id="q_1083908b8d7e6a2c_6"><div><br> </div>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0px 0px 0px 0.8ex; padding-left: 1ex;">> 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" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">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>
</blockquote></span></div></blockquote></div><br>