Hetero-weighted trees

(HWT)

An hetero-weighted tree is a tree never showing two identical integers:

+--+--+ <------ top

| |

6 | <-.

+--+--+ | \

| | | \

5 | | <------ intermediate results

+--+--+ | |

| | | |

2 3 1 4 <------ ground

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

[Franklin T. Adams-Watters said this much better on the Seqfan mailing-list:

« (...) 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. »]

Question:

What are the smallest “integers on top” for HWTs which show all integers from 1 to n?

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

n = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 ...

S = 1, 3, 3, 6, 10, 10, 15, 15, 21, 28, 28, 36, 36, 45, 55, 55, 66, 66, 78, 91, 91 ...

I’m definitely lost for bigger values of n... Is there an algorithm? A formula?

Examples:

First column is n; second column is the “smallest top integer”; third column is the corresponding HWT showing all integers from 1 to n:

n S(n) HWT Explanation

1: ---> 1 1 <--- integer 1 is visible in the diagram

2: ---> 3 3

+--+--+

| | <--- integers 1 and 2 are visible in the diagram,

1 2 and the top integer is 3

3: ---> 3 3

+--+--+

| | <--- integers 1, 2 and 3 are visible in the diagram,

1 2 and the top integer is 3

4: ---> 6 6

+--+--+

| |

4 |

+--+--+ | <--- integers 1, 2, 3 and 4 are visible in the diagram,

| | | and the top integer is 6

1 3 2

5: ---> 10 10

+-----+--+

| | |

5 | |

+-+-+ | | <--- integers 1 to 5 are visible in the diagram,

| | | | and the top integer is 10

1 4 2 3

6: ---> 10 10

+--+--+

| |

6 |

+--+--+ |

| | |

5 | | <--- integers 1 to 6 are visible in the diagram,

+-+-+ | | and the top integer is 10

| | | |

2 3 1 4

7: ---> 15 15

+-----+--+

| | |

7 | |

+-+--+ | |

| | | | <--- integers 1 to 7 are visible in the diagram,

6 | | | and the top integer is 15

+-+-+ | | |

| | | | |

2 4 1 3 5

8: ---> 15 15

+----+---+

| |

7 |

+-+--+ |

| | | <--- integers 1 to 8 are visible in the diagram,

6 | 8 and the top integer is 15

+-+-+ | +-+-+

| | | | |

2 4 1 3 5

9: ---> 21 21

+------+---+

| | |

9 | |

+-+-+ | |

| | | | <--- integers 1 to 9 are visible in the diagram,

| 8 7 | and the top integer is 21

| +-+ +-+ |

| | | | | |

1 2 6 3 4 5

10: ---> 28 28

+---+---+----+

| | | | <--- integers 1 to 10 are visible in the diagram,

10 | 8 9 and the top integer is 28

+--+ | +-+ +-+

| | | | | | |

3 7 1 2 6 4 5

11: ---> 28 28

+-----+----+

| | |

11 | |

+-+-+ | |

| | | | <--- integers 1 to 11 are visible in the diagram,

10 | 8 9 and the top integer is 28

+--+ | +-+ +-+

| | | | | | |

3 7 1 2 6 4 5

12: ---> 36 36

+-+----+-------+

| | | |

| | 11 12

| | +----+ +--+

| | | | | | <--- integers 1 to 12 are visible in the diagram,

| | 10 | 9 | and the top integer is 36

| | +--+ | +-+ |

| | | | | | | |

6 7 2 8 1 4 5 3

13: ---> 36 36

+------+-------+

| | |

13 11 12

+--+ +-+--+ +--+

| | | | | | <--- integers 1 to 13 are visible in the diagram,

| | 10 | 9 | and the top integer is 36

| | +--+ | +-+ |

| | | | | | | |

6 7 2 8 1 4 5 3

14: ---> 45 45

+----+----+------+

| | | |

11 | 13 14

+-+-+ | +--+ +--+--+ <--- integers 1 to 14 are visible in the diagram,

10 | | | | | 12

+--+ | | | | | +--+

| | | | | | | | |

4 6 1 7 5 8 2 3 9

15: ---> 55 55

(thanks to +----+-----+--------+----+

| | | 15 | <--- integers 1 to 15 are visible in the diagram

| | | +----+ | and the top integer is 55

| | | | | |

11 12 13 14 | |

+--+ +--+ +--+ +--+ | |

| | | | | | | | | |

2 9 5 7 10 3 6 8 1 4

16: ---> 55 55

(thanks to +-----+-------+-------+

Acetonik ) | | | |

| 16 | 15 <--- integers 1 to 16 are visible in the diagram

| +---+ | +----+ and the top integer is 55

| | | | | |

11 | 12 13 14 |

+--+ | +--+ +--+ +--+ |

| | | | | | | | | |

2 9 4 5 7 10 3 6 8 1

17: ---> 66 66

(thanks to +----+------+------+------+

and | 12 14 15 17

Jacques Mathon) | +--+ +--+ +--+ +--+ <--- integers 1 to 17 are visible in the diagram

| | | | | 13 | 16 |

| | | | | +--+ | +--+ |

| | | | | | | | | | |

8 3 9 10 4 6 7 2 5 11 1

18: ---> 66 66

(thanks to +-------+------+------+

Jacques Mathon) | | | |

18 17 16 15

+--+ +--+ +--+ +--+ <--- integers 1 to 18 are visible in the diagram

| | 12 | 13 | 14 |

| | +--+ | +--+ | +--+ |

| | | | | | | | | | |

11 7 10 2 5 9 4 3 8 6 1

[Jacques Mathon] :

Jusqu’à ce stade (sans meilleures solutions), on aurait (sauf erreur de ma part) S(n)=C(E(0,6(n+1)+1,5),2).

Cette conjecture donnerait pour n=19 : S(19)=C(E(0,6(19+1)+1,5)),2)=C(13,2)=78

et pour n=20 : S(20)=C(14,2)=91

[Acetonik] :

Oui, à ce stade seulement, car le nombre de possibilités de combiner les termes augmentant rapidement, on peut penser que les résultats deviendront plus chaotiques par la suite.

D’autre part, on n’est pas certain d’obtenir la valeur minimale.

La relative facilité avec laquelle on trouve une solution, et leur nombre, me laisse perplexe.

[Jacques Mathon] :

Je n’en suis pas convaincu, c’est la raison pour laquelle je propose cette formule.

[Acetonik] :

Quelques résultats pour confirmer que les valeurs de S obtenues par Eric pour n variant de 1 à 14 sont bien les valeurs minimales réalisables.

J’ai effectué une programmation (loin d’être optimale sans doute) qui envisage tous les cas d’arbres possibles.

J’ai donc pu calculer le nombre de fois f où le minimum est atteint pour chacune des valeurs de n. Ce nombre croît très rapidement avec n, ce qui laisse de l’espoir pour trouver d’autres résultats que ceux obtenus jusqu’à présent. Toutefois le nombre de cas à envisager augmente très rapidement aussi. Une recherche intuitive à partir de n=19 et suivants semble difficile à envisager... mon programme devrait pouvoir y parvenir... en lui laissant un peu de temps !

n = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ...

S = 1, 3, 3, 6, 10, 10, 15, 15, 21, 28, 28, 36, 36, 45, ...

f = 1, 1, 1, 1, 2, 1, 3, 6, 9, 30, 34, 96, 210, 410, ...

19: ---> 78 78

(thanks to +-----+-----+-----+-----+

| | | | 19

| | | | +--+

| | | | | |

| | | | | 18 <--- integers 1 to 19 are visible in the diagram

| | | | | | |

15 14 17 13 | | 16

+--+ +--+ +--+ +--+ | | +--+

| | | | | | | | | | | |

12 3 10 4 11 6 5 8 1 2 7 9

[Eric Angelini] :

.. si la suite cherchée n’est pas en rapport avec les nombres triangulaires (comme le fait remarquer Frank T. Adams-Watters – voir plus bas), je veux bien être pendu (à l’arbre) !

T = 0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120,...

[Acetonik] :

Cela me semblait évident depuis longtemps : pour obtenir un top mini, il faut obligatoirement choisir p plus petits nombres consécutifs à la base (ground), ensuite le top mini reste toujours la somme de ces p nombres et c’est bien connu :

1+2+3 +........+p = p(p+1)/2 = C(p+1,2)

Ce qui peut devenir chaotique, c’est le fait que pour plusieurs valeurs de n consécutives le nombre de termes à la base peut rester le même (et donc le top mini aussi). On a déjà vu deux top mini consécutifs égaux, mais rien ne dit qu’il ne puisse pas y en avoir 3, 4... AMHA.

[Jean-Paul Davalan] :

> [ÉA]

> en rapport avec les nombres triangulaires

...certes, du moins pour les petites valeurs de n, mais avec des doublements (période 5 = deux, deux, un) :

S = 1, 3, 3, 6, 10, 10, 15, 15, 21, 28, 28, 36, 36, 45, 55, 55, 66, 66, 78, 91, 91, 105, 105, 120, 136, 136, 153, 153, 171, 190, 190, 210, 210, 231, 253, 253,...

20: ---> 91 91

(thanks to +-------+------+------+--+-+

17 18 19 20 | |

+--+ +--+ +--+ +--+ | | <--- integers 1 to 20 are visible in the diagram

| | 16 | 15 | 14 | | |

| | +--+ | +--+ | +--+ | | |

| | | | | | | | | | | | |

10 7 11 5 2 12 3 4 13 1 6 8 9

21: ---> 91 91

(thanks to +-----+----+----+-- ---+

21 19 18 17 16

+--+ +--+ +--+ +--+ +--+

| | | | | | | | | | <--- integers 1 to 21 are visible in the diagram

20 | | | | | | | 14 | and the top integer is 91

+--+ | | | | | | | +--+ |

| | | | | | | | | | | |

15 | | | | | | | | | | |

+--+ | | | | | | | | | | |

| | | | | | | | | | | | |

7 8 5 1 10 9 12 6 13 4 11 3 2

[Acetonik] :

Un petit bilan:

Pour chaque n variant de 1 à 14, la valeur S(n) correspondante est la valeur top minimale (vérifié en envisageant tous les cas possibles). Le nombre de fois où le top minimum est atteint dépend de la façon dont on distingue les cas (ordre des termes, ordre des opérations dans une branche, ordre des branches...)

Pour 14 < n <=21 des arbres ont été obtenus, mais il n’est pas assuré que la valeur S(n) donnée soit la valeur minimale... Il faut du temps pour envisager tous les cas possibles.

De même, le programme de JP en C permet de donner des solutions (jusqu’à n=30 chez moi) mais il n’est pas prouvé que S(n) soit le top *minimum*. Voici deux exemples :

– le cas n=22, S(22)=105

19 17

22 21 20 16 15

5 : 10 12 : 13 8 : 6 14 : 9 7 3 : 2 4 11 1

– le cas n=30 et S(30)=190

24 29 28

26 23 22 21 20 27 25

16 : 14 12 : 13 10 : 5 17 : 6 15 : 11 9 4 : 8 19 2 1 : 7 18 3

[Jacques Mathon]:

J’ai aussi quelques exemples pour 22, 23, 24, 25, 26, 27, 28 et 50.

Je crois bien (je vérifie) que j’ai une méthode systématique pour construire un arbre de valeur S(n)=C(E((6n+21)/10),2) pour tout n. Mais pas de méthode de calcul pour obtenir le nombre total de solutions. Et, en effet, il restera à prouver, comme je le pense, que S(n) est l’optimum.

Soit n le nombre de nombres (de 1 à n) à répartir dans l’arbre.

Soit S(n)=C(E((6n+21)/10),2)

Soit m=E((6n+21)/10)

La construction s’effectue sur trois lignes

Si n-m est pair :

_ n _ n-1 _ ... _ ...

m \ m+1 \ ... \ ... \ ...

m-1 1 n-m : m-2 3 n-m-2 : ... ... ... : ... ... 2 : ... ... : ... : ...

Si n-m est impair :

_ n _ n-1 _ ... _ ...

m \ m+1 \ ... \ ... \

m-1 m-2 2 n-m : m-3 4 n-m-2 : ... ... ... : ... ... 1 : ...

Comme c’est un peu long de formaliser ça, voici quelques exemples:

n=23

m=15

S(n)=105

_23 _22 _21 _20

15 \ 16 \ 17 \ 18 \ 19

14 1 8 13 3 6 12 5 4 11 7 2 10 9

n=24

m=16

S(n)=120

_24 _23 _22 _21

16 \ 17 \ 18 \ 19 \ 20

15 1 8 14 3 6 13 5 4 12 7 2 11 9 10

n=25

m=17

S(n)=136

_25 _24 _23 _22

17 \ 18 \ 19 \ 20 \ 21

16 1 8 15 3 6 14 5 4 13 7 2 12 9 11 10

n=26

m=17

S(n)=136

_26 _25 _24 _23 _22

17 \ 18 \ 19 \ 20 \ 21 \

16 15 2 9 14 4 7 13 6 5 12 8 3 10 11 1

n=27

m=18

S(n)=153

_27 _26 _25 _24 _23

18 \ 19 \ 20 \ 21 \ 22 \

17 16 2 9 15 4 7 14 6 5 13 8 3 12 10 1 11

n=28

m=18

S(n)=153

_28 _27 _26 _25 _24

18 \ 19 \ 20 \ 21 \ 22 \ 23

17 1 10 16 3 8 15 5 6 14 7 4 13 9 2 12 11

n=50

m=32

S(n)=496

50 49 48 47 46 45 44 43 42

32 \ 33 \ 34 \ 35 \ 36 \ 37 \ 38 \ 39 \ 40 \ 41

31 1 18 30 3 16 29 5 14 28 7 12 27 9 10 26 11 8 25 13 6 24 15 4 23 17 2 22 19 21 20

__________

Franklin T. Adams-Watters said also, on December 13^th:

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.

__________

Merci à tous,

É.

(Last update: December 19^th, 2011, Brussels, Belgium)