Introduction
Voir le § 2.2.1 (suites arithmétiques) pour la démonstration du premier
résultat, et le paragraphe § 2.2.2 pour celle du dernier.
Les deuxième et troisième résultats (somme des carrés, somme des cubes)
se démontrent classiquement par récurrence.
4. Dénombrement — Formule du binôme
Un ensemble non vide E est dit fini ssi il existe n ∈ N tel qu’il existe
une bijection de E sur 1 ; n. n est alors le cardinal de E.
On note Card E = n. L’ensemble vide est fini, de cardinal 0.
Le cardinal d’un ensemble fini est simplement le nombre de ses éléments.
Un ensemble est dit dénombrable ssi il existe une bijection de N sur
cet ensemble. Attention, les problèmes de dénombrement concerne les
ensembles finis !
4.1 Factorielle d’un nombre entier
Définition
Pour n appartenant à N, on définit par récurrence :
0! = 1 ; si n 1, n! = n × (n − 1)!
Lire « factorielle n ». D’après la définition, on a
1! = 1 ; 2! = 2 × 1 = 2 ; 3! = 3 × 2 × 1 = 6 ; 4! = 24 ; . . .
De façon générale, pour n 1 : n! = n × (n − 1) × · · · × 1
La programmation de n! en langage PASCAL peut se faire de façon
itérative :
ÙÒÒØØÓÒ ØØÖ´Ò ÒØØØØÖµ ÖÖÖÐ
ÚÚÖ ÒØØØØÖÖ ÖÖÖÐÐ
Ò
½½
ÓÖ ½ ØÓ Ò Ó ¶¶¶
ØØÖÖÖÖÖÖÖ
ÒÒÒ
La programmation récursive est ici préférable :
ÙÒÒØØÓÒ ÖÖÖ´Ò ÖÖÖеµÖÖÖÐÐ
Ò
ÒÒ¼ ØØØÒ ÖÖÖÖÖ½ Ð××
ÖÖÖÖÖÒ¶¶¶¶ÖÖÖ´Ò¹½µµ
ÒÒÒ
12