9.2 Etude combinatoire analytique
379
Fig. 9.1 Un abr avec des
feuilles/possibilités
d’insertion distinguées : en
rose, de type 1, la plus à
droite ; en bleu, de type 2,
celles qui sont enfant direct
d’un nœud de la branche de
droite ; celles de type 3, dans
les sous-arbres τ 1 , τ 2 , . . . , ne
sont pas représentées
9.2.2 Une urne dans un abr
En guise d’illustration de la méthode combinatoire analytique, le résultat suivant
a constitué un point clé dans une étude d’arbres d’expressions booléennes [41].
Considérons un processus d’abr (T n ) comme en section 2.2.3. Pour un arbre T n ,
considérons sa branche droite, celle qui va de la racine à la feuille la plus à droite
et appelons X n le nombre de feuilles directement enfant d’un nœud interne de cette
branche droite. Voir la figure 9.1.
Proposition 9.4 La loi de X n est donnée par : pour tout n ≥ 1, pour tout m ≤ n,
P(X n = m) =
1
m!
n−m
j =0
(−1) j
j !
.
La loi de X n converge lorsque n → +∞ vers une loi de Poisson de paramètre 1.
Preuve (idée) Une urne de Pólya apparaît lorsque nous convenons que les boules de
l’urne sont les feuilles de l’arbre. Elles sont de trois types. Les feuilles de type 2 sont
celles que nous voulons compter. La feuille de type 1 est la feuille la plus à droite.
Les feuilles de type 3 sont les autres feuilles de l’arbre. Important : l’insertion a bien
lieu uniformément sur les feuilles/boules.
La matrice de remplacement de cette urne est
⎛
⎝
0 1 0
0 −1 2
0 0 1
⎞
⎠
et X n est le nombre de boules de type 2 dans l’urne à l’instant n. L’application du
théorème 9.2, ou plutôt de son extension au cas de plus de deux couleurs, fournit le
379
Fig. 9.1 Un abr avec des
feuilles/possibilités
d’insertion distinguées : en
rose, de type 1, la plus à
droite ; en bleu, de type 2,
celles qui sont enfant direct
d’un nœud de la branche de
droite ; celles de type 3, dans
les sous-arbres τ 1 , τ 2 , . . . , ne
sont pas représentées
9.2.2 Une urne dans un abr
En guise d’illustration de la méthode combinatoire analytique, le résultat suivant
a constitué un point clé dans une étude d’arbres d’expressions booléennes [41].
Considérons un processus d’abr (T n ) comme en section 2.2.3. Pour un arbre T n ,
considérons sa branche droite, celle qui va de la racine à la feuille la plus à droite
et appelons X n le nombre de feuilles directement enfant d’un nœud interne de cette
branche droite. Voir la figure 9.1.
Proposition 9.4 La loi de X n est donnée par : pour tout n ≥ 1, pour tout m ≤ n,
P(X n = m) =
1
m!
n−m
j =0
(−1) j
j !
.
La loi de X n converge lorsque n → +∞ vers une loi de Poisson de paramètre 1.
Preuve (idée) Une urne de Pólya apparaît lorsque nous convenons que les boules de
l’urne sont les feuilles de l’arbre. Elles sont de trois types. Les feuilles de type 2 sont
celles que nous voulons compter. La feuille de type 1 est la feuille la plus à droite.
Les feuilles de type 3 sont les autres feuilles de l’arbre. Important : l’insertion a bien
lieu uniformément sur les feuilles/boules.
La matrice de remplacement de cette urne est
⎛
⎝
0 1 0
0 −1 2
0 0 1
⎞
⎠
et X n est le nombre de boules de type 2 dans l’urne à l’instant n. L’application du
théorème 9.2, ou plutôt de son extension au cas de plus de deux couleurs, fournit le