B Rappels mathématiques : combinatoire
457
La formule de Lagrange relie les coefficients de F à ceux de :
Théorème B.7 (Formule d’inversion de Lagrange) Soit une fonction analytique en 0, telle que = φ 0 = 0 et soit F l’unique fonction analytique en 0
qui soit solution de l’équation implicite F (z) = zz(F (z)). Alors F (0) = 0, et pour
tout n ≥ 1,
[z
n
]F (z) =
1
n
[u
n−1
]
n (u).
De plus,
[z
n
]F (z)
k
=
k
n
[u
n−1
]
n (u)
et, par linéarité, pour toute fonction G analytique,
[z
n
]G(F (z)) =
1
n
[u
n−1
]
G
(u) )
n (u)
.
B.3.6 Lemme de transfert
Ce qui suit est détaillé dans le livre de Flajolet et Sedgewick [94] et l’exposition qui
est faite ici s’inspire largement du cours de Pouyanne [216].
L’idée générale est la suivante : l’asymptotique des coefficients d’une série
entière est intimement liée aux singularités sur son cercle de convergence de la
fonction holomorphe qu’elle définit. Le théorème de transfert dit pour l’essentiel,
modulo quelques hypothèses, que lorsqu’on sait développer la fonction au voisinage
d’une singularité dominante ζ dans l’échelle log-puissance en z
1 −
z
ζ
α
1
z
ζ
log
1
1 −
z
ζ
β
,
alors son n-ième coefficient de Taylor se développe automatiquement dans l’échelle
géométrico-log-puissance en n
ζ
−n n
a log
b n.
Plus précisément, le premier théorème qui suit, le théorème B.8, donne
l’asymptotique des coefficients [z n ]f d’une fonction f de l’échelle log-puissance.
Ensuite est détaillée l’hypothèse dite « camembert » sur la fonction f au voisinage
d’une singularité dominante ζ , hypothèse qui intervient dans le théorème de
transfert proprement dit, qui est le théorème B.10.