Arbres binaires et décompositions totales

Description des arbres

Il s'agit des arbres décrits par Éric Angelini sur son site, à la page http://www.cetteadressecomportecinquantesignes.com/HLT.htm
         10
       +--+--+     <------ total, sommet, top   $S=10$
       |     |    
       6     |     <-.     $n=6$                          
    +--+--+  |        \                          
    |     |  |         \                        
    5     |  |     <------ les résultats intermédiaires 
 +--+--+  |  |    
 |     |  |  |    
 2     3  1  4     <------ la base, (la terre)

 arbre composé à partir de $\{1, 2, 3, 4, 5, 6\}$.
 la partie contenant les autres nombres (dont le sommet) est le chapeau. 
 l'arbre est binaire (sauf éventuellement le chapeau, par commodité)
Par commodité les solutions seront présentées sous la forme condensée suivante :
10 : 6=5+1, 5=3+2
qui permet de retrouver l'arbre.

Plus petits sommets

La question posée par Éric est de rechercher pour chaque $n$ le plus petit sommet $S$ possible.


Solutions

L'application ci-dessous cherche toutes les solutions qui correspondent à la valeur de $n$.
Lorsque l'on précise la valeur $N$, toutes les solutions dont le sommet est inférieur ou égal à $N$.
Sinon, l'application calcule et choisit elle-même la plus petite valeur du sommet.

Le programme C équivalent mais plus rapide est appar.c. Il est nécessaire de le compiler avant de l'utiliser :
gcc -O2 -o appar appar.c
usage : appar n [N]



$n=$   $N=$

     



Généralisations

Représentation par des intervalles

Une somme $y=x+d$ où $x\lt y$ peut être représentée par le schéma suivant :
     _____ d _____
    |             |
    x             y
Cette remarque permet de comprendre le schéma suivant, mais attention, l'axe est orienté vers la gauche !
(La raison en est que l'on cherche à décomposer dans l'ordre décroissant, d'abord $18$, puis $17$ etc.)
$n=5\times 3+3$
      ______________7____________
     |    __________5________    |      18=11+7
     |   |    ______3____    |   |      17=12+5
     |   |   |    __1    |   |   |      16=13+3, 15=14+1
     |   |   |   |   |   |   |   |
    18  17  16  15  14  13  12  11  10   9   8
                     |   |   |       |   |   |
                     |   |   |___2___|   |   |   12=10+2
                     |   |_______4_______|   |   13=9+4
                     |___________6___________|   15=8+6

Formules

$n=5\times 4+3$
       ____________________________________________
      |     __________________________________     |
      |    |     ________________________     |    |    
      |    |    |     ______________     |    |    |    
      |    |    |    |     ____     |    |    |    |    
      |    |    |    |    |    |    |    |    |    |    
     23   22   21   20   19   18   17   16   15   14   13   12   11   10    
                               |    |    |    |_________|    |    |    |
                               |    |    |___________________|    |    |
                               |    |_____________________________|    |
                               |_______________________________________|
On généralise aisément les deux exemples précédents au cas où $n$ est de la forme $n=5p+3$
$x = 4p+3+r$ avec $0\leq r \leq p$ se décompose en $4p+3+r = (4p+2-r) + (2r+1)$
$x = 3p+r$ avec $0\leq r \leq p-2$ se décompose en $3p+r=(3p-r-2)+ (2r+2)$
et la somme est $\displaystyle S = \sum_{k=1}^{3n+2} k = \frac {(3n+2)(3n+3)} 2$

Documents - références - compléments - liens utiles

Hetero-weighted trees   par Éric Angelini.
















Pour un premier contact, [utilisez ce formulaire] ou utilisez l'adresse de messagerie qui y figure. Merci d'indiquer la page précise du site "http//jm.davalan.org/...", cela m'aidera beaucoup. Ne joignez aucun document à votre message.
Jeux-et-Mathématiques n'est pas un site commercial. Aucun des liens placés sur ce site n'est rémunéré, ni non plus aucune des informations données.
Important : Si votre question a un quelconque rapport avec un travail personnel (Devoir TIPE Master...) , vous devez absolument me le préciser dès votre premier message et m'indiquer très précisément les limites des informations demandées. Vous devez aussi avertir la personne qui dirige éventuellement votre travail ou le corrige de cette communication et lui montrer les documents fournis.

J'essaie de répondre aux questions posées, mais ne lis pas les documents mathématiques amateurs, pas plus que je ne donne mon avis sur les démonstrations des conjectures de Collatz ou autres. Je ne lis pas les documents word, je ne corrige pas les programmes informatiques et depuis des années je n'utilise plus de tableur.

© (Copyright) Jean-Paul Davalan 2002-2014