168
4 Approche combinatoire
Fig. 4.15 Les premières
valeurs de la constante κ m
intervenant dans l’énoncé de
la proposition 4.27
4.5 Arbres non planaires
Nous nous intéressons dans cette section au dénombrement de trois classes d’arbres :
les arbres de Pólya, le sous-ensemble de ces arbres dont les nœuds internes sont
d’arité 2, et les arbres de Cayley qui, à la différence des précédents, sont marqués.
Nous rappelons qu’il s’agit ici d’arbres non planaires, i.e. tels que les enfants d’un
nœud interne ne sont pas ordonnés. L’énumération de ces arbres, dans le cas non
marqué, remonte à Pólya [211] ; elle a été ensuite reprise et systématisée par
Otter [201]. Nous traitons d’abord les arbres de Cayley, qui sont de loin les plus
simples ; certains résultats sur ces arbres nous serviront pour l’étude des arbres de
Pólya généraux, que nous aborderons après le cas particulier des arbres de Pólya
binaires.
4.5.1 Arbres de Cayley
Rappelons que ces arbres, que nous avons définis dans la section 1.2.3 et qui ne
sont autres que des arbres de Pólya marqués par des clés distinctes de N, vérifient
l’équation récursive
Cay = (◦ × SET(Cay)).
Cette relation se traduit sur la fonction génératrice exponentielle Cay(z) =
n Cay n
z n
n! , avec Cay 0 = 0 (un arbre de Cayley n’est pas vide ; il a donc au
moins un nœud), par l’équation implicite (cf. section B.2)
Cay(z) = ze
Cay(z) ,
(4.27)
formule qui se prête bien à une extraction des coefficients par inversion de Lagrange
(cf. section B.3.5) :
[z
n
] Cay(z) =
Cay n
n!
=
1
n
[u
n−1
]e
nu
=
1
n
n n−1
(n − 1)!
=
n n−1
n!
.