196
5 Approche probabiliste
5.2 Modèle de Catalan et arbres de Galton-Watson
Dans cette section, les arbres binaires ou planaires sous le modèle de Catalan (c’està-dire que les arbres de même taille sont équiprobables) sont vus comme des arbres
de Galton-Watson conditionnés par leur taille. De nombreux résultats sur les arbres
sous le modèle de Catalan proviennent de ce lien, par exemple le comportement
asymptotique de leur hauteur et de leur largeur exposé dans la section 5.2.3.
Ce lien organique entre les arbres sous le modèle uniforme et les arbres de
Galton-Watson fait partie du « folklore » et remonte au moins à Kolchin [159]
et [160, Chap. 2] et Kennedy [152] ; la présentation qui suit est due essentiellement
à Jean-François Marckert, dans son cours de master à Versailles dans les années
2000 puis dans son cours à Graz [178].
5.2.1 Pour les arbres binaires et les arbres planaires
Supposons qu’un type de parcours soit fixé, le parcours en largeur ou le parcours
en profondeur (les parcours d’arbres sont présentés dans l’annexe A). Les nœuds
d’un arbre planaire fini τ sont alors ordonnés par le parcours ; pour k =
1, . . . , |τ |, appelons u k le k-ième nœud. Associons à tout arbre planaire τ la suite
(y 1 , y 2 , . . . , y |τ | ) où y i = M u i , nombre d’enfants du nœud u i dans l’arbre τ
(figure 5.3). L’application D ainsi définie de l’ensemble P des arbres planaires dans
l’ensemble des suites finies d’entiers
n≥1 N n est clairement une injection : si deux
arbres sont différents, c’est qu’il existe un nœud u qui est dans l’un et pas dans
l’autre ; alors le père de u n’a pas le même nombre d’enfants dans les deux arbres,
donc les suites associées par D sont différentes.
Inversement, n’importe quelle liste d’entiers ne correspond pas à un arbre. Par
exemple, quel que soit le parcours choisi, la suite (1, 0, 0, 2) ne correspond pas à un
arbre. Cependant, nous avons la proposition suivante.
Fig. 5.3 Un exemple d’arbre planaire τ et la suite associée par l’application D. Ici le parcours
d’arbre choisi est le parcours en profondeur ou parcours préfixe
5 Approche probabiliste
5.2 Modèle de Catalan et arbres de Galton-Watson
Dans cette section, les arbres binaires ou planaires sous le modèle de Catalan (c’està-dire que les arbres de même taille sont équiprobables) sont vus comme des arbres
de Galton-Watson conditionnés par leur taille. De nombreux résultats sur les arbres
sous le modèle de Catalan proviennent de ce lien, par exemple le comportement
asymptotique de leur hauteur et de leur largeur exposé dans la section 5.2.3.
Ce lien organique entre les arbres sous le modèle uniforme et les arbres de
Galton-Watson fait partie du « folklore » et remonte au moins à Kolchin [159]
et [160, Chap. 2] et Kennedy [152] ; la présentation qui suit est due essentiellement
à Jean-François Marckert, dans son cours de master à Versailles dans les années
2000 puis dans son cours à Graz [178].
5.2.1 Pour les arbres binaires et les arbres planaires
Supposons qu’un type de parcours soit fixé, le parcours en largeur ou le parcours
en profondeur (les parcours d’arbres sont présentés dans l’annexe A). Les nœuds
d’un arbre planaire fini τ sont alors ordonnés par le parcours ; pour k =
1, . . . , |τ |, appelons u k le k-ième nœud. Associons à tout arbre planaire τ la suite
(y 1 , y 2 , . . . , y |τ | ) où y i = M u i , nombre d’enfants du nœud u i dans l’arbre τ
(figure 5.3). L’application D ainsi définie de l’ensemble P des arbres planaires dans
l’ensemble des suites finies d’entiers
n≥1 N n est clairement une injection : si deux
arbres sont différents, c’est qu’il existe un nœud u qui est dans l’un et pas dans
l’autre ; alors le père de u n’a pas le même nombre d’enfants dans les deux arbres,
donc les suites associées par D sont différentes.
Inversement, n’importe quelle liste d’entiers ne correspond pas à un arbre. Par
exemple, quel que soit le parcours choisi, la suite (1, 0, 0, 2) ne correspond pas à un
arbre. Cependant, nous avons la proposition suivante.
Fig. 5.3 Un exemple d’arbre planaire τ et la suite associée par l’application D. Ici le parcours
d’arbre choisi est le parcours en profondeur ou parcours préfixe