138
4 Approche combinatoire
et F ; nous supposons en outre que S(0) = σ 0 = 0. La fonction F (z) vérifie
l’équation
F (z) = σ 0 z + σ 1 zF (z) + . . . + σ p zF (z)
p
+ . . . ,
qui peut s’écrire de manière condensée
F (z) = zS(F (z)).
(4.17)
En d’autres termes, la fonction F (z) est solution d’une équation implicite. Nous
pourrons parfois, comme dans le cas des expressions présenté en section 4.2.1,
résoudre explicitement l’équation (4.17), ce qui permettra d’obtenir des informations sur les singularités de la fonction F , et donc sur le comportement asymptotique
de ses coefficients. Dans d’autres cas, nous utiliserons plutôt la formule de Lagrange
(cf. section B.3.5), qui relie les coefficients de F à ceux de S par
[z
n
]F (z) =
1
n
[u
n−1
]S
n (u),
(4.18)
pour calculer f n . Enfin, l’équation implicite (4.17) permet d’obtenir directement des
résultats sur le comportement asymptotique de f n . Regardons ce que cela donne sur
quelques exemples.
– Reprenons la famille P des arbres planaires. Pour chaque valeur p de N, il existe
exactement un symbole d’arité p dans S, dont la fonction génératrice est donc
S(t) =
p≥0 t p = (1 − t) −1 . La fonction P (z) énumérant les arbres de P
satisfait l’équation P (z) = z/(1 − P (z)), qui peut bien entendu se résoudre
directement. Si nous utilisons la formule de Lagrange sur cette équation, nous
trouvons
[z
n
]P (z) =
1
n
[u
n−1
]
1
(1 − u) n =
1
n
2n − 2
n − 1
= C n−1 ,
ce qui est cohérent avec la bijection présentée en Section 1.1.3 entre les arbres
planaires de taille n et les arbres binaires de taille n − 1, et était déjà l’objet du
corollaire 4.2.
– Comme autre exemple, prenons les arbres ternaires, dans lesquels les nœuds
internes sont d’arité 3. Nous avons S = {( 0), (•, 3)} et S(t) = 1 + t 3 , ce
qui donne une équation de degré 3 sur F : F (z) = z + zF (z) 3 . Nous pourrions
avec des formules de Cardan écrire une forme close pour F mais ce serait un peu
compliqué et inutile : la formule de Lagrange (4.18) donne, pour n = 3p + 1
(seules valeurs pour lesquelles le coefficient est non nul)
[z
n
]F (z) =
1
3p + 1
[u
3p
](1 + u
3 )
3p+1
=
1
3p + 1
3p + 1
p
.
4 Approche combinatoire
et F ; nous supposons en outre que S(0) = σ 0 = 0. La fonction F (z) vérifie
l’équation
F (z) = σ 0 z + σ 1 zF (z) + . . . + σ p zF (z)
p
+ . . . ,
qui peut s’écrire de manière condensée
F (z) = zS(F (z)).
(4.17)
En d’autres termes, la fonction F (z) est solution d’une équation implicite. Nous
pourrons parfois, comme dans le cas des expressions présenté en section 4.2.1,
résoudre explicitement l’équation (4.17), ce qui permettra d’obtenir des informations sur les singularités de la fonction F , et donc sur le comportement asymptotique
de ses coefficients. Dans d’autres cas, nous utiliserons plutôt la formule de Lagrange
(cf. section B.3.5), qui relie les coefficients de F à ceux de S par
[z
n
]F (z) =
1
n
[u
n−1
]S
n (u),
(4.18)
pour calculer f n . Enfin, l’équation implicite (4.17) permet d’obtenir directement des
résultats sur le comportement asymptotique de f n . Regardons ce que cela donne sur
quelques exemples.
– Reprenons la famille P des arbres planaires. Pour chaque valeur p de N, il existe
exactement un symbole d’arité p dans S, dont la fonction génératrice est donc
S(t) =
p≥0 t p = (1 − t) −1 . La fonction P (z) énumérant les arbres de P
satisfait l’équation P (z) = z/(1 − P (z)), qui peut bien entendu se résoudre
directement. Si nous utilisons la formule de Lagrange sur cette équation, nous
trouvons
[z
n
]P (z) =
1
n
[u
n−1
]
1
(1 − u) n =
1
n
2n − 2
n − 1
= C n−1 ,
ce qui est cohérent avec la bijection présentée en Section 1.1.3 entre les arbres
planaires de taille n et les arbres binaires de taille n − 1, et était déjà l’objet du
corollaire 4.2.
– Comme autre exemple, prenons les arbres ternaires, dans lesquels les nœuds
internes sont d’arité 3. Nous avons S = {( 0), (•, 3)} et S(t) = 1 + t 3 , ce
qui donne une équation de degré 3 sur F : F (z) = z + zF (z) 3 . Nous pourrions
avec des formules de Cardan écrire une forme close pour F mais ce serait un peu
compliqué et inutile : la formule de Lagrange (4.18) donne, pour n = 3p + 1
(seules valeurs pour lesquelles le coefficient est non nul)
[z
n
]F (z) =
1
3p + 1
[u
3p
](1 + u
3 )
3p+1
=
1
3p + 1
3p + 1
p
.