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)}.
- avoir une souscription active sur mathprepa
- et être connecté au site
- revenir à la page d'accueil
- ou tester la page d'extraits libres