Appendice E
Rappel des notations utilisées
E.1 Mathématiques
– Notations de Landau O et o : soient f et g deux fonctions définies au voisinage
d’un réel a (respectivement au voisinage de +∞). On dit que f (x) = O(g(x))
au voisinage de a (respectivement au voisinage de +∞) lorsqu’il existe des
constantes η (respectivement A) et C telles que pour tout x tel que |x − a| ≤ η
(respectivement pour tout x tel que x ≥ A) on a |f (x)| ≤ C|g(x)|.
On dit que f (x) = o(g(x)) au voisinage de a lorsque lim
x→a
f (x)
g(x)
= 0.
– Partie entière de x : pour x réel, est l’unique entier tel que ≤ x <
Et est l’unique entier tel que − 1 ≤ x <
– Pour x réel, {x} est sa partie fractionnaire : {x} = x − −x
– log + x est la partie positive du log, autrement dit : log + x = max(0, log x).
– Ensemble des permutations de taille n : S n .
– Nombres harmoniques : H n =
n
i=1
1
i .
– Nombres harmoniques étendus : H
(p)
n =
n
i=1
1
i p .
– γ est la constante d’Euler : γ = lim n H n − log n.
– Pour i et j entiers, i, j (notation d’Iverson) ou [i..j ] est l’ensemble des entiers
entre i et j .
– Symbole de Kronecker : pour i et j entiers, δ ij = 1 si i = j et δ ij = 0 si i = j .
– Pour une fonction développable en série entière autour de 0, f (z) =
k≥0 f k z k ,
le k-ième coefficient f k est noté [z k ]f (z).
– Fonction Gamma d’Euler : =
+∞
0
t a−1 e −t dt.
– est la dérivée logarithmique de : =
(x)
.
– Fonction Beta d’Euler : B(a, b) =
1
0 t a−1 (1 − t) b−1 dt =
(a))(b)
(a + b)
.
© Springer Nature Switzerland AG 2018
B. Chauvin et al., Arbres pour l’Algorithmique, Mathématiques et Applications 83,
https://doi.org/10.1007/978-3-319-93725-0
491