Le nombre de descentes d'un arbre enraciné décoré

On considère les arbres enracinés munis d'une bijection entre leurs sommets et les entiers de 1 à n. Il est bien connu que leur nombre total est nn-1.

Descentes sur 3 sommets

Figure : Les 9 arbres enracinés décorés sur 3 sommets (la racine est en vert)


On appelle descente une arête dont les deux sommets sont en ordre décroissant lorsque cette arête est parcourue en direction de la racine.
On a représenté les descentes par une arête rouge dans la figure ci-dessus.
Le nombre de descentes définit une statistique sur les arbres enracinés décorés, qui prend des valeurs entre 0 et n-1.
Cette statistique est symétrique, car changer l'ordre total sur les étiquettes en son inverse revient à échanger descentes et non-descentes.
Le polynôme en une variable t défini par cette statistique se factorise : Πi=1n-1 (n-i+it).
Dans le cas n=3 (voir la figure ci-dessus), on trouve 2+5t+2t2=(2+t)(1+2t).

Mars 2002

HTML 5