5.2 Modèle de Catalan et arbres de Galton-Watson
197
Proposition 5.16 Pour un parcours d’arbre fixé, pour tout entier n ≥ 1,
l’application D : τ → (y 1 , y 2 , . . . , y n ), qui à un arbre planaire associe la suite
des nombres d’enfants des nœuds successifs, est une bijection de l’ensemble P n des
arbres planaires à n nœuds sur l’ensemble D n des suites de n entiers vérifiant les
contraintes (C)
(C)
⎧
⎪ ⎪ ⎪ ⎪ ⎪ ⎨
⎪ ⎪ ⎪ ⎪ ⎪ ⎩
y 1
≥ 1,
y 1 + y 2
≥ 2,
. . .
y 1 + . . . +y n−1 ≥ n − 1,
y 1 + . . . +y n = n − 1.
La preuve est laissée en exercice (les détails sont dans Marckert [178]) ; remarquons
que la suite (s 0 , s 1 , . . . , s n ) définie par s 0 = 0, s 1 = y 1 − 1, s 2 = (y 1 − 1) + (y 2 −
1), . . . , s n = (y 1 − 1) + · · · + (y n − 1) vérifie des contraintes déduites de (C) et se
retrouve être une marche d’incréments (y i − 1) qui est une excursion sur [0, n − 1]
et qui est ainsi en bijection avec un arbre planaire à n nœuds. Ce n’est pas la même
excursion que celle du processus de contour qui sera décrit dans la section 5.2.3 (a).
Rendons tous ces objets aléatoires : soit (p k ) k≥0 une loi de probabilité sur N telle
que m =
k kp k ≤ 1, et soit τ un arbre de Galton-Watson pour cette loi. Cet arbre
τ est fini presque sûrement, en vertu du corollaire 5.3.
Soient maintenant un entier n et un arbre t planaire à n noeuds, t ∈ P n . D’après
ce qui précède, c’est la même chose de se donner l’arbre t, ou bien une suite
(y 1 , y 2 , . . . , y n ) de n entiers vérifiant (C). Donc
P(τ = t) = P ((Y 1 , . . . , Y n ) = (y 1 , . . . , y n )) =
u∈τ
p M u =
n
i=1
p y i =
j ≥0
p
d j
j ,
où d j est le nombre de nœuds de l’arbre t qui ont j enfants. En conditionnant par la
taille de l’arbre :
P(τ = t
|τ | = n) = P ((Y 1 , . . . , Y n ) = (y 1 , . . . , y n ) | |τ | = n)
(5.7)
=
P ((Y 1 , . . . , Y n ) = (y 1 , . . . , y n ))
P(|τ | = n)
(5.8)
=
n
i=1 p y i
P(|τ | = n)
(5.9)
=
j ≥0 p
d j
j
P(|τ | = n)
.
(5.10)
Ce sont ces égalités qui permettent d’obtenir la correspondance entre arbres de
Galton-Watson et arbres sous la loi uniforme, résumée dans la proposition suivante.
197
Proposition 5.16 Pour un parcours d’arbre fixé, pour tout entier n ≥ 1,
l’application D : τ → (y 1 , y 2 , . . . , y n ), qui à un arbre planaire associe la suite
des nombres d’enfants des nœuds successifs, est une bijection de l’ensemble P n des
arbres planaires à n nœuds sur l’ensemble D n des suites de n entiers vérifiant les
contraintes (C)
(C)
⎧
⎪ ⎪ ⎪ ⎪ ⎪ ⎨
⎪ ⎪ ⎪ ⎪ ⎪ ⎩
y 1
≥ 1,
y 1 + y 2
≥ 2,
. . .
y 1 + . . . +y n−1 ≥ n − 1,
y 1 + . . . +y n = n − 1.
La preuve est laissée en exercice (les détails sont dans Marckert [178]) ; remarquons
que la suite (s 0 , s 1 , . . . , s n ) définie par s 0 = 0, s 1 = y 1 − 1, s 2 = (y 1 − 1) + (y 2 −
1), . . . , s n = (y 1 − 1) + · · · + (y n − 1) vérifie des contraintes déduites de (C) et se
retrouve être une marche d’incréments (y i − 1) qui est une excursion sur [0, n − 1]
et qui est ainsi en bijection avec un arbre planaire à n nœuds. Ce n’est pas la même
excursion que celle du processus de contour qui sera décrit dans la section 5.2.3 (a).
Rendons tous ces objets aléatoires : soit (p k ) k≥0 une loi de probabilité sur N telle
que m =
k kp k ≤ 1, et soit τ un arbre de Galton-Watson pour cette loi. Cet arbre
τ est fini presque sûrement, en vertu du corollaire 5.3.
Soient maintenant un entier n et un arbre t planaire à n noeuds, t ∈ P n . D’après
ce qui précède, c’est la même chose de se donner l’arbre t, ou bien une suite
(y 1 , y 2 , . . . , y n ) de n entiers vérifiant (C). Donc
P(τ = t) = P ((Y 1 , . . . , Y n ) = (y 1 , . . . , y n )) =
u∈τ
p M u =
n
i=1
p y i =
j ≥0
p
d j
j ,
où d j est le nombre de nœuds de l’arbre t qui ont j enfants. En conditionnant par la
taille de l’arbre :
P(τ = t
|τ | = n) = P ((Y 1 , . . . , Y n ) = (y 1 , . . . , y n ) | |τ | = n)
(5.7)
=
P ((Y 1 , . . . , Y n ) = (y 1 , . . . , y n ))
P(|τ | = n)
(5.8)
=
n
i=1 p y i
P(|τ | = n)
(5.9)
=
j ≥0 p
d j
j
P(|τ | = n)
.
(5.10)
Ce sont ces égalités qui permettent d’obtenir la correspondance entre arbres de
Galton-Watson et arbres sous la loi uniforme, résumée dans la proposition suivante.