ENSEMBLES FINIS, DÉNOMBREMENT
Ensembles finis
Définition : Soit E un ensemble. On dit que E est fini s’il est en bijection avec un intervalle d’entiers Fn . L’entier
n, s’il existe est unique. On l’appelle le cardinal de E. On note Card E = n.
Théorème*.— Cardinal des parties —. Soit E un ensemble fini et A ∈ P(E) une partie de E. Alors
A est un ensemble fini et Card A ≤ Card E,
A = E si et seulement si Card A = Card E.
Proposition*.— Soit E et F des ensembles non vides et f : E → F une application. Alors
f est injective ssi il existe une application g : F → E telle que g ◦ f = idE .
f est surjective ssi il existe une application g : F → E telle que f ◦ g = idF .
Corollaire*.— Soit f une application d’un ensemble E vers un ensemble fini F .
L’ensemble image f (E) est fini et Card f (E) ≤ Card F.
Card f (E) = Card F si et seulement si f est surjective.
Corollaire*.— Soit f une application d’un ensemble fini E vers un ensemble F .
L’ensemble image f (E) est fini et Card f (E) ≤ Card E.
Card f (E) = Card E si et seulement si f est injective.
Théorème*.— Soit E et F des ensembles finis.
Il existe une injection de E dans F ssi Card E ≤ Card F
Il existe une surjection de E sur F ssi Card E ≥ Card F
Il existe une bijection de E dans F ssi Card E = Card F
Théorème.— Soit E et F deux ensembles finis et f : E → F une application. On suppose que Card E = Card F.
Les assertions suivantes sont équivalentes
~
w • f est injective
w
w • f est surjective
w
• f est bijective
Dénombrements
Théorème*.— Opérations élémentaires sur les ensembles finis —. Soit E et F des ensembles finis, A, B ∈ P(E)
des parties de E. Alors
Si E et F sont disjoints, la réunion disjointe E ∪ F est finie et Card (E ∪ F ) = Card E + Card F.
la réunion E ∪ F est finie et Card (E ∪ F ) = Card E + Card F − Card (E ∩ F ).
le complémentaire ∁E A est fini et Card (E \ A) = Card E − Card A
la différence A \ B est finie et Card (A \ B) = Card A − Card (A ∩ B)
le produit cartésien E × F est fini et Card (E × F ) = Card E × Card F.
1
Savoir-faire : utiliser le théorème du berger pour dénombrer E et pour dénombrer F .
Théorème.— Applications entre ensembles finis —. Soit Ep et Fn des ensembles finis de cardinaux respectifs p et
n. Alors
L’ensemble F E de toutes les applications de E vers F est fini et Card (F E ) = (Card F )Card E
.
n!
L’ensemble I(Ep , Fn ) des applications injectives de Ep vers Fn est fini et Card I(Ep , Fn ) = Apn = (n−p)! si
0 ≤ p ≤ n, et 0 sinon.
L’ensemble B(Ep , Fn ) des applications bijectives de Ep vers Fn est fini et Card B(Ep , Fn ) = n! si p = n, et
0 sinon.
Théorème.— Parties d’un ensemble fini —. Soit En un ensemble fini de cardinal n. Alors
P(En ) = 2n .
L’ensemble P(En ) de toutes les parties de En est fini et Card
P(En ) = np = n!
L’ensemble Pp (En ) des parties à p éléments de En est fini et Card si 0 ≤ p ≤ n
p!(n−p)!
et 0 sinon.
Analyse combinatoire
Soit En un ensemble à n éléments. On peut ranger les modèles canoniques dans le tableau suivant :
cardinal ensemble des
• tirages successifs avec remise de p éléments de En
np est le nombre de • listes à répétition de p éléments de En (ou p-listes d’éléments de En )
• applications de Fp dans En
• tirages successifs sans remise de p éléments de En
Apn est le nombre de • listes de p éléments distincts de En (ou p-arrangements d’éléments de En )
• applications injectives de Fp dans En
• tirages simultanés sans remise de p éléments de En
n
p est le nombre de • listes strictement croissantes de p éléments de En
• parties à p éléments de En
Propriétés des coefficients du binôme
Théorème*.— Formule du binôme de Newton —. Pour tout (a, b) ∈ C2 , et pour tout n ∈ N,
n
n
X n
(a + b) = ak bn−k .
k
k=0
Théorème*.— Pour tous (n, p) ∈ N2 ,
n
n n n n n+1 n n X n
=1 =n = = + = 2n
0 1 p n−p p+1 p p+1 k
k=0
Savoir-faire : donner une interprétation ensembliste de ces relations
