5.2 Modèle de Catalan et arbres de Galton-Watson
199
∀k ≥ 0, p k = e −λ λ k /k!), conditionné à être de taille n, suit la loi uniforme sur
l’ensemble Cay n des arbres de Cayley à n nœuds.
Preuve Soit τ un arbre de Cayley de taille n, dont les nœuds sont numérotés de 1
à n, par exemple celui de la Figure 1.15 que nous remettons ici. Fixons-nous un
parcours. Pour i = 1, . . . , n, appelons A i l’ensemble des marques des enfants du
nœud numéro i. La marque de la racine apparaît pas, de sorte que la réunion de tous
les ensembles A i est en bijection avec un ensemble à n − 1 éléments. La donnée de
l’arbre τ est équivalente à la donnée de la liste d’ensembles A i . Inversement une liste
d’ensembles formant une partition d’un ensemble à n−1 éléments ne correspond pas
toujours à un arbre. Il faut ajouter des contraintes sur les y i = Card(A i ), qui sont
les contraintes (C) de la section précédente. Par exemple, pour l’arbre de Cayley
ci-dessus et pour le parcours en profondeur, nous avons n = 8, (A 1 , . . . , A 8 ) =
({3, 4, 6, 8}, ∅, {2, 7}, ∅, ∅, ∅, {1}, ∅) et (y 1 , . . . , y 8 ) = (4, 0, 2, 0, 0, 0, 1, 0).
Soit maintenant (y 1 , . . . , y n ) une suite de n entiers vérifiant (C) et soit t l’arbre à
n nœuds associé. Soit τ n un arbre de Cayley choisi avec la loi uniforme 9 sur Cay n .
Alors,
P(τ n = t) = P((Y 1 , . . . , Y n ) = (y 1 , . . . , y n ))
=
n − 1
y 1
n − 1 − y 1
y 2
. . .
n − 1 − y 1 − · · · − y n−1
y n
Card(Cay n )
=
(n − 1)!
y 1 ! . . . y n !
1
Card(Cay n )
.
9 Le cardinal de l’ensemble Cay n est n n−1 , voir en section 4.5.1, mais cela n’intervient pas dans la
preuve.