Techniques de base
On rencontre souvent des simplifications du type :
(n + 1)!
n!
= n + 1 ;
n!
(n − k)!
= n (n − 1) . . . (n − k + 1) ; . . .
4.2 Formules élémentaires
Nombre de termes
p et n étant des entiers naturels tels que p n, de p à n il y a n − p + 1
nombres entiers.
Ainsi, de 1 à 100, il y a 100 nombres entiers, et non 99. De 100 à 200 il
y a 200 − 100 + 1 = 101 nombres entiers.
Nombre de suites finies
• Soit n, k ∈ N. Le nombre de suites à k éléments d’un ensemble à
n éléments est égal à n
k .
• Soit n, k ∈ N tels que 1 k n. Le nombre de suites à k éléments
distincts d’un ensemble à n éléments est égal à
n (n − 1) . . . (n − k + 1) =
n!
(n − k)!
• Soit n ∈ N ; le nombre de suites à n éléments distincts de l’ensemble E à n éléments, ou permutations de E, est égal à n!.
On obtient ces formules à l’aide de représentations arborescentes.
La première est un cas particulier de la formule
Card(A 1 × A 2 × · · · × A k ) = Card(A 1 ) · Card(A 2 ) · . . . · Card(A k ),
avec tous les A i égaux, de cardinal n.
Elle est valable même si n ou k sont nuls, si on considère la « suite vide »
(suite à 0 élément), et avec la convention 0
0
= 1.
De même, en adoptant l’écriture avec des factorielles, la deuxième formule reste valable même si k ou n sont nuls. Notez que le produit
n (n − 1) . . . (n − k + 1)
comporte k facteurs (autant que de nombres de 0 à k − 1).
La troisième formule est un cas particulier important de la deuxième,
avec k = n. Une permutation d’un ensemble à n éléments peut être vue
comme une manière d’écrire dans un certain ordre les éléments de cet
ensemble, ou comme une bijection de 1, n sur cet ensemble.
13