B Rappels mathématiques : combinatoire
465
Par convention habituelle, une somme vide de termes est nulle et H 0 = 0.
Asymptotiquement, quand n → +∞, H n = log n + γ + 1/2n + O(1/n 2 ),
où γ est la constante d’Euler : γ = 0,577215 . . .
– Coefficients binomiaux :
n
p
=
n!
p!(n − p)!
=
n(n − 1) . . . (n − p + 1)
p!
.
– Nombres de Catalan :
C n =
1
n + 1
2n
n
=
4 n
n
√
πn
1 + O
1
n
.
– Nombres de Stirling de première espèce :
Ils sont définis par récurrence par : ∀n ≥ 1, k ≥ 1,
n
k
=
n − 1
k − 1
+ (n − 1)
n − 1
k
;
n
0
=
0
k
= 0 ;
0
0
= 1.
Leur fonction génératrice est
f (z) :=
+∞
k=0
z
k
n
k
= z(z + 1) . . . (z + n − 1).
Ils comptent le nombre de permutations de S n qui se décomposent en k cycles
disjoints.
– Fonction Gamma d’Euler : pour (a) > 0, =
+∞
0
t
a−1 e
−t dt.
– Fonction Beta d’Euler : pour (a) > 0 et (b) > 0,
B(a, b) =
1
0
t
a−1 (1 − t)
b−1 dt =
(a))(b)
(a + b)
.
– La formule de Stirling donne une approximation de n! quand n → +∞ :
n! ∼
√
2πn
n
e
n
.
Si l’on a besoin de plus de précision, le développement asymptotique de la
factorielle commence par
n! = n(n − 1)(n − 2) . . . 2 · 1 =
√
2πn
n
e
n
1 +
1
12n
+ O
1
n 2
.