[seqfan] Re: Hetero-labeled trees

franktaw at netscape.net franktaw at netscape.net
Tue Dec 13 15:37:16 CET 2011

It is IMO better to describe these as "weights" rather than "labels". 
So what you are defining are "hetero-weighted trees", the requirement 
is that each node has a distinct positive integer weight, and the 
weight of any non-leaf node is the sum of the weights of its children.

As far as I know, no one has studied these, but I don't know everything.

Try counting how many such trees there are with a given weight at the 
root, and see if that sequence is in the database. (One could break 
this down further, asking how many such trees there are with leaf 
weights a particular partition into distinct parts (see A118457). There 
will always be at least one: the single node tree for a partition with 
only one part, and a height 2 tree for any other partition into 
distinct parts.)

Other than that, I have to wonder whether every term in your sequence 
is a triangular number. Whether it is or not, this suggests another 
sequence: the maximum number of consecutive values 1 to a(n) in a tree 
whose leaves have weights 1 to n.

Franklin T. Adams-Watters

-----Original Message-----
From: Eric Angelini <Eric.Angelini at kntv.be>

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

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


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:


Seqfan Mailing list - http://list.seqfan.eu/


More information about the SeqFan mailing list