2.2 Aléa sur les arbres marqués
53
Fig. 2.7 Pour n = 3, les 6 permutations de S 3 donnent les abr de cette figure. Les permutations
213 et 231 donnent le même arbre (celui du dessous) qui est donc de probabilité 2/6 alors que
les autres sont chacun obtenus par une seule permutation, et sont donc de probabilité 1/6. Dans le
modèle de Catalan, les 5 arbres de taille 3 sont chacun de probabilité 1/5
Proposition 2.13 Soit τ n un abr de taille n, sous le modèle des permutations
uniformes. Appelons τ
(g)
n et τ
(d)
n les sous-arbres respectivement gauche et droit de
τ n . Soit p ∈ {0, . . . , n − 1}. Alors
P
|τ
(g)
n | = p
=
1
n
,
et, conditionnellement en la taille de τ
(g)
n égale p, les sous-arbres τ
(g)
n et τ
(d)
n sont
indépendants, τ
(g)
n a même loi que τ p , et τ
(d)
n a même loi que τ n−1−p .
Preuve Soit p ∈ {0, . . . , n − 1}. Le réordonnement des x i , i = 1, . . . , n est donné
par la permutation σ n :
x σ n (1) < x σ n (2) < · · · < x σ n (n) ,
de sorte que
P
|τ
(g)
n | = p
= P
σ
−1
n (1) = p + 1
=
1
n
,
puisque σ −1
n est de loi uniforme sur S n . Conditionnellement en la taille de τ
(g)
n
égale p, nous avons σ n (p + 1) = 1 et donc
x σ n (1) < · · · < x σ n (p) sont les clés de τ
(g)
n ,
x σ n (p+2) < · · · < x σ n (n) sont les clés de τ
(d)
n ,
avec la convention habituelle : si p = 0, le premier ensemble est vide, si p = n − 1,
le second ensemble est vide. Comme les x i , i = 1, . . . , n sont i.i.d. les arbres τ
(g)
n
et τ
(d)
n sont indépendants, τ
(g)
n a même loi qu’un abr de taille p, et τ
(d)
n a même loi
qu’un abr de taille n − 1 − p.