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!
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!
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
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 ]
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,