Suite et arbre — Les-mathematiques.net The most powerful custom community solution in the world

Suite et arbre

Bonjour je cherche à obtenir le nombre de nœuds d'un arbre à la hauteur n se construisant comme ceci :

on dispose d'un nombre (supérieur à n) d’éléments que l'on cherche à apparier (à mettre ensemble) dans un arbre.
On place (1) à la racine. Si (1) peut s'apparier avec (2) (selon une relation d'équivalence dont on n'a pas besoin ici) alors (1) on aura 2 nœuds fils : un nœud F1 qui contient (1,2) et l'autre F2 qui contient (2).
On continue pour le nœud de gauche F1. F1 possède 2 fils : un nœud qui contient (1,2,3), et un nœud qui contient seulement (3). En effet, si (3) ne s'apparie pas à (1,2) il ne s'apparie ni à (1), ni à (2) selon la relation d'équivalence.
F2 lui possède 3 fils : soit 3 s'apparie à (1) et on obtient (1,3), soit il s'apparie à (2) et on obtient (2,3) soit il ne ne s'apparie à rien et on n'obtient seulement (3). Évidement lors du parcours de l'arbre, celui ci sera élagué la relation étant transitive, si l'on arrive sur (1,3) il est inutile d'aller explorer (2,3), (1) n'étant pas apparié à (2). Mais cela n'est pas le problème.
a la hauteur 3 on a donc 2+3=5 nœuds. Je n'arrive seulement pas à généraliser le problème pour n. Il y a bien sûr dans la formule une somme des k parmi n mais il manque un quelque chose que je n'arrive pas obtenir.
Je vous remercie!

Réponses

  • Bonjour je cherche à obtenir le nombre de nœuds d'un arbre à la hauteur n se construisant comme ceci :

    on dispose d'un nombre (supérieur à n) d’éléments que l'on cherche à apparier (à mettre ensemble) dans un arbre.
    On place (1) à la racine. Si (1) peut s'apparier avec (2) (selon une relation d'équivalence dont on n'a pas besoin ici) alors (1) on aura 2 nœuds fils : un nœud F1 qui contient (1,2) et l'autre F2 qui contient (2).
    On continue pour le nœud de gauche F1. F1 possède 2 fils : un nœud qui contient (1,2,3), et un nœud qui contient seulement (3). En effet, si (3) ne s'apparie pas à (1,2) il ne s'apparie ni à (1), ni à (2) selon la relation d'équivalence.
    F2 lui possède 3 fils : soit 3 s'apparie à (1) et on obtient (1,3), soit il s'apparie à (2) et on obtient (2,3) soit il ne ne s'apparie à rien et on n'obtient seulement (3). Évidement lors du parcours de l'arbre, celui ci sera élagué la relation étant transitive, si l'on arrive sur (1,3) il est inutile d'aller explorer (2,3), (1) n'étant pas apparié à (2). Mais cela n'est pas le problème.
    a la hauteur 3 on a donc 2+3=5 nœuds. Je n'arrive seulement pas à généraliser le problème pour n. Il y a bien sûr dans la formule une somme des k parmi n mais il manque un quelque chose que je n'arrive pas obtenir.
    Je vous remercie!

    [ Discussions fusionnées : inutile d'ouvrir plusieurs discussions sur un même sujet. jacquot ]
  • Vraiment besoin d'aide svp n'hésitez pas à répondre juste pour me demander des infos si je n'ai pas été assez clair merci
  • Vraiment besoin d'aide svp n'hésitez pas à répondre juste pour me demander des infos si je n'ai pas été assez clair merci
  • Peux-tu donner un exemple sous forme d'un dessin pour comprendre ces nœuds
    -------------------------------------------------------------------------------------------------------------------------------
    Citation :  Je préfère une solution qui se construit au fur et à mesure des échanges que de m'envoyer  consulter une solution détaillée via un lien
  • voilà l'arbre pour n =4
  • l'arbre pour n =4
  • Restons- en à $n=3.$ Je n'ai pas compris pourquoi le chemin $1-12-13$ n'existe pas.
  • Prenons 1. 2 s'apparie à 1 alors on obtient (1,2). Si 3 s'apparie à 1 par la suite on obtient (1,2,3) et non (1,3). En effet si 3 s'apparie à 1, comme 2 s'appariait à 1 alors par transitivité 3 s'apparie à 2 et on obtient donc les trois.
  • Obscur.
  • Bonjour,

    Les noeuds de 'hauteur $n$" dans cet arbre semblent décrire ( au moins jusqu'à $n=4$) l' ensemble des relations d'équivalence que l'on peut définir sur $\mathcal E_n =\{1,2,...n\}$, ou, ce qui revient au même, l'ensemble des partitions de $\mathcal E_n$: par exemple, pour $n=4$, ces noeuds me paraissent correspondre, en lisant de gauche à droite dans ton arbre, aux partitions de $\mathcal E_4$ suivantes:
    $(1234);\:\:(123)(4);\:\: (34)(12);\:\:(124)(3);\:\:(4)(3)(12);\:\: (234)(1);\:\:(14)(23);\:\:
    (4)(23)(1);\:\:(134)(2);\:\:(24)(13);\:\:(4)(13)(2);\:\:(34)(2)(1)$
    $(24)(3)(1);\:\:(14)(3)(2);\:\: (4)(3)(2)(1)$.
    En notant $u_n$ le nombre que tu cherches , celui-ci peut alors être obtenu par la relation de récurrence suivante:
    $u_0=u_1=1;\:\:\: \forall n \in \N, \:\:u_{n+1} = \displaystyle{\sum_{k=0}^{n} \binom n k u_k}$.
    Ainsi: $u_2 = 2;\:\: u_3 =5;\:\: u_4 =15;\:\: u_5 = 52;\:\: u_6 =203 ...$
    Cela dit , je n'ai rien compris à tes explications et je ne suis pas du tout sûr que ma réponse convienne pour la question que tu poses.
    Amicalement,
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!