[seqfan] Hetero-labeled trees

Eric Angelini Eric.Angelini at kntv.be
Mon Dec 12 18:13:11 CET 2011


Hello SeqFans,
An hetero-labeled tree is a tree showing no two identical labels:

         10
       +--+--+     <------ top
       |     |    
       6     |     <-.                           
    +--+--+  |        \                          
    |     |  |         \                        
    5     |  |     <------ intermediate results 
 +--+--+  |  |     
 |     |  |  |    
 2     3  1  4     <------ ground

We are interested in HLT, like the one above, which are provided 
with an additive rule: integers on the ground are added, at some
point (as are the intermediate ones), but the integer on top is
unique.

Question:

What is the smallest integer on top for HLTs showing all integers
from 1 to n (plus others, if needed - but integers from 1 to n 
must appear in the tree)?

The "smallest top integers" sequence seems to start like this 
(not in the OEIS):

S = 1, 3, 3, 6, 10, 10, 15, 15,...

I'm definitely lost for bigger values of n... Is there an algorithm?
A formula?
Sorry if this is old hat -- trees must have been searched a lot, 
I guess.

More examples here:
http://www.cetteadressecomportecinquantesignes.com/HLT.htm
Best,
É.






More information about the SeqFan mailing list