Calcul du nombre d’arbres binaires ayant n noeuds

Soit {T_n} le nombre d’arbres binaires à {n} noeuds (on ne prend pas ici en compte la valeur des étiquettes, mais seulement l’existence des noeuds). On a bien sûr {T_0=1} (c’est le seul arbre vide).

Un arbre binaire de {n+1} noeuds est la donnée d’une racine (qui compte comme un noeud), d’un arbre gauche (formé de {k} noeuds, avec {0\le k\le n}) et d’un arbre droit (formé alors de {n-k} noeuds). Quand on fait varier {k} de 0 à {n}, ce dénombrement donne l’égalité :

{T_{n+1}=\sum_{k=0}^{n}T_kT_{n-k}.}

Pour {x\le\frac14}, on pose {f(x)=\frac{1-\sqrt{1-4x}}{2x}}, avec {f(0)=1}.

On va montrer que le DL de {f} en 0 à l’ordre {n} est {f(x)=\sum\limits_{k=0}^{n}T_kx^k+o(x^n)}.

Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez :