le 12 Novembre 1996

Démonstration Combinatoire des Formules de Prodinger Concernant les Arbres Binaires

Guo-Niu HAN

1. Introduction.— Nous considérons les arbres binaires d’ordre n. Il est bien connu que le nombre de ces arbres est égal au nombre de Catalan c_{n} = \frac{1}{n+1} \binom{2n}{n}. Pour m = 0, 1 ou 2, on définit m-noeuds comme étant les noeuds ayant m fils. En particulier, les 0-noeuds ne sont d’autre que les feuilles.

Dans [M], Mahmoud a trouvé trois formules qui donnent le nombre des arbres binaires ayant j feuilles, j 1-noeuds et j 2-noeuds respectivement. D’après ces résultat, Prodinger a trouvé trois formules closes pour ces mêmes nombres [P], en utilisant le logiciel Ekhad, développé par Zeilberger [Z].

Dans cette note, on trouvera une démonstration combinatoire pour ces formules.

2. Formule de Prodinger.— Dans un arbre binaire, il est facile à vérifier que le nombre des feuilles est égal au nombre des 2-noeuds plus 1. Les formules de Prodinger se réduisent donc à une seule formule [P] :

Théoème [Prodinger].—Le nombre des arbres binaires d’ordre n ayant j feuilles est égal à

A_{n}^{j} = \frac{2^{n+1−2j}(n − 1)!}{j!(j − 1)!(n + 1 − 2 ∗ j)!}.

3. Démonstration Combinatoire.— Considérons les mots finis engendrés par l’alphabet {U, D, R, L} (Up, Down, Right, Left). Un tel mot w est dit de Grand-Motzkin si |w|_{D} = |w|_{U}. Il est évident que le nombre des mots de Grand-Motzkin d’ordre n ayant j Down est égal à

B_{n}^{j} = \binom{n}{j, j, n − 2 ∗ j}2^{n−2∗j}.

Un mot w = x_{1}x_{2} ⋯ x_{n−1}D est dit de Motzkin, si x_{1}x_{2} ⋯ x_{n−1} est de Grand-Motzkin et si |x_{1}x_{2} ⋯ x_{i}|_{D} ≤ |x_{1}x_{2} ⋯ x_{i}|_{U} pour tout 1 ≤ i ≤ n−1. Soit w un mot de Motzkin d’ordre n ayant j Down, il existe j façons de factoriser ce mot sous la forme w = uDv. C’est clair que la concatenation vu est un mot de Grand-Motzkin, et que le nombre des mots de Motzkin d’ordre n ayant j Down est jB_{n−1}^{j−1} = A_{n}^{j}.

Enfin, la formule de Prodinger est assurée par une simple bijection entre les arbres binaires et les mots de Motzkin, qui envoie les feuilles en Down, les 2-noeuds en Up, et les 1-noeuds ayant un fils droit en Right, les 1-noeuds ayant un fils gauche en Left.

Exercice.— Tracer l’arbre binaire correspondant au mot de Motzkin w = ULDRUULDRDRD.

BIBLIOGRAPHIE

[M] H. M. Mahmoud. The joint distribution of the three types of nodes in uniform binary trees. Algorithmica, 13:313-323, 1995.

[P] H. Prodinger. A note on the distribution of the three types of nodes in uniform binary trees. Séminaire Lotharingien de Combinatoire, B38b,

5pp, 1996. http://cartan.u-strasbg.fr/~slc/

[Z] M. Petkovsek, H. Wilf, and D. Zeilberger. A = B. A.K. Peters, Ltd., 1996.

IRMA, Université Louis Pasteur & CNRS

7, rue René-Descartes

67084 Strasbourg Cedex, France

                             email:  guoniu@math.u-strasbg.fr