354
8 Arbres m-aires et quadrants
et donc, puisque (x, y) suit la loi Ord 1 × Ord 1 :
P n (n 0 + n 1 = m) =
1
0
1
0
P
(x,y)
n
(n 0 + n 1 = m)dxdy
=
1
0
n − 1
m
x
m ( 1 − x)
n−1−m dx
=
n − 1
m
B(m + 1, n − m),
où la fonction Beta est définie (cf section B.5.1) par
B(a, b) =
1
0
u
a−1 (1 − u)
b−1 du =
(a) )(b)
(a + b)
.
Le résultat est immédiat en remplaçant B(i +1, n−i) par son expression en fonction
des factorielles.
L’expression de μ n 0 ,n 1 ,n 2 ,n 3 et celle de w p,n,, s’obtiennent par un raisonnement
analogue. La valeur de π n,p découle de celle de w p,n,, , en sommant sur la taille
du troisième sous-arbre (nous rappelons que H n est le n-ième nombre harmonique).
Puis π n,0 est obtenue en posant p = 0 dans la formule précédente. Enfin, la dernière
propriété se déduit de la propriété ii).
Remarque 8.14 La propriété iv) de la proposition 8.13 montre bien la différence de
comportement avec le cas des arbres binaires de recherche (d = 1), pour lesquels la
taille du premier sous-arbre (sous-arbre gauche) a pour loi 1 Ord 1 étant une
variable aléatoire de loi uniforme sur [0, 1], c’est-à-dire que la taille est uniforme
sur {0, 1, . . . , n − 1}.
Lois des tailles des sous-arbres : cas général
Passons maintenant au cas où d ≥ 3. Les notations seront les mêmes
que pour d = 2, ou étendues de manière évidente. Il est possible d’obtenir
l’analogue de la proposition 8.13 ; nous donnons ci-dessous la probabilité
π n,p qu’un sous-arbre de la racine soit de taille p (cf. Flajolet et al. [99, 101]),
et ne mentionnons pas ici les extensions.
(tsvp)
8 Arbres m-aires et quadrants
et donc, puisque (x, y) suit la loi Ord 1 × Ord 1 :
P n (n 0 + n 1 = m) =
1
0
1
0
P
(x,y)
n
(n 0 + n 1 = m)dxdy
=
1
0
n − 1
m
x
m ( 1 − x)
n−1−m dx
=
n − 1
m
B(m + 1, n − m),
où la fonction Beta est définie (cf section B.5.1) par
B(a, b) =
1
0
u
a−1 (1 − u)
b−1 du =
(a) )(b)
(a + b)
.
Le résultat est immédiat en remplaçant B(i +1, n−i) par son expression en fonction
des factorielles.
L’expression de μ n 0 ,n 1 ,n 2 ,n 3 et celle de w p,n,, s’obtiennent par un raisonnement
analogue. La valeur de π n,p découle de celle de w p,n,, , en sommant sur la taille
du troisième sous-arbre (nous rappelons que H n est le n-ième nombre harmonique).
Puis π n,0 est obtenue en posant p = 0 dans la formule précédente. Enfin, la dernière
propriété se déduit de la propriété ii).
Remarque 8.14 La propriété iv) de la proposition 8.13 montre bien la différence de
comportement avec le cas des arbres binaires de recherche (d = 1), pour lesquels la
taille du premier sous-arbre (sous-arbre gauche) a pour loi 1 Ord 1 étant une
variable aléatoire de loi uniforme sur [0, 1], c’est-à-dire que la taille est uniforme
sur {0, 1, . . . , n − 1}.
Lois des tailles des sous-arbres : cas général
Passons maintenant au cas où d ≥ 3. Les notations seront les mêmes
que pour d = 2, ou étendues de manière évidente. Il est possible d’obtenir
l’analogue de la proposition 8.13 ; nous donnons ci-dessous la probabilité
π n,p qu’un sous-arbre de la racine soit de taille p (cf. Flajolet et al. [99, 101]),
et ne mentionnons pas ici les extensions.
(tsvp)