I. Cardinal d'un ensemble
Définition :
On dit d’un ensemble qu’il est fini s’il possède un nombre fini d’éléments.
Soit E un ensemble fini. Le cardinal de E, noté Card(E), est le nombre d’éléments de l’ensemble E.
Exemple :
E={a,b,c,d} est un ensemble fini et Card(E)=4.
Remarques :
i) On note parfois ♯E ou ∣E∣ au lieu de Card(E).
ii) Card(∅)=0.
iii) Certains ensembles ne sont pas finis : N,R, etc.
Définition :
Deux ensembles A et B sont disjoints si A∩B=∅.
Exemple :
A={1,2,3} et B={4,5} sont disjoints car A∩B=∅.
II. Réunion d'ensembles ou le principe additif
Si un ensemble E est la réunion de plusieurs sous-ensembles deux à deux disjoints, alors le nombre d’éléments de E est la somme des nombres d’éléments de chacun de ces sous-ensembles.
Formellement, si
E=A1∪A2∪⋯∪Am et si Ai∩Aj=∅ pour tout i=j, alors :
card(E)=card(A1)+card(A2)+⋯+card(Am).
Exemple :
Si E se décompose en 3 sous-ensembles disjoints A, B et C, on a :
card(E)=card(A)+card(B)+card(C).
Exemple :
Soit un ensemble E partitionné en 5 sous-ensembles disjoints E1,E2,E3,E4,E5 contenant respectivement 2, 10, 4, 3 et 6 éléments. On a :
card(E)=2+10+4+3+6=25.
Corollaire : Soient A une partie d’un ensemble fini E et A le complémentaire de A dans E.
On a : Card(E)=Card(A)+Card(A).
III. Produit cartésien ou le principe multiplicatif
Définition :
Soient A et B deux ensembles non vides. Le produit cartésien de A et B est l’ensemble noté A×B (se lit « croix A B »), constitué des couples (a,b) où a est un élément de A et b un élément de B. Plus formellement : A×B={(a,b)∣a∈A et b∈B}.
Exemple :
Soient A={x,y} et B={1,2,3}. Alors :
A×B={(x,1),(x,2),(x,3),(y,1),(y,2),(y,3)}.
Propriété :
Soient A et B deux ensembles finis. Alors : Card(A×B)=Card(A)×Card(B).
Plus généralement, pour des ensembles finis A1,A2,…,Ak,
card(A1×A2×⋯×Ak)=card(A1)×card(A2)×⋯×card(Ak).
IV. k-uplets d'un ensemble fini
1. Un peu de vocabulaire : couple, triplet et k-uplet d'un ensemble à n éléments
Soit k un entier naturel non nul
∘ Couple (ou 2-uplet) : on note (a,b) un objet composé de deux éléments a et b.
∘Triplet (ou 3-uplet) : (a,b,c).
∘ k-uplet (ou k-liste) : (x1,x2,…,xk) où chaque xi est un élément de l’ensemble considéré.
Remarque : L’ordre compte dans un k-uplet :
(a,b)=(b,a) en général si a=b.
L'ensemble Ek
Lorsque tous les ensembles sont identiques, c’est-à-dire E1=E2=⋯=Ek=E, on note :
Ek={(x1,x2,…,xk) ∣ xi∈A pour i=1,…,k}
∘Un élément de Ek est donc un k-uplet d’éléments de E.
Un exemple avec deux ensembles :Si card(A)=4 et card(B)=7, alors
card(A×B)=4×7=28.Concrètement, il y a 28 couples (a,b) possibles avec a∈A et b∈B
Autres exemples :
i) (a,b,q) est un 3-uplet de l’ensemble des 26 lettres de l'alphabet.
ii) Combien existe-t-il de codes de carte bancaire à 4 chiffres ?
L’ensemble des chiffres utilisés est {0,1,2,…,9} et comporte 10 éléments.Le nombre de 4-uplets de chiffres (c’est-à-dire le nombre de suites de 4 chiffres) est : 104=10×10×10×10=10 000.
Théorème :
Soient k≥1 et E un ensemble fini de cardinal n. Le nombre de k-uplets de E est nk, soit :
Card(Ek)=nk.
Autrement dit, le nombre de k-upletsd’un ensemble de n eˊleˊments est : nk
Exemple :
i) On dispose de trois boîtes notées A,B,C et cinq jetons numérotés de couleurs différentes. On doit ranger ces jetons dans les boîtes. On note E=A,B,C l’ensemble des boîtes. Les différents rangements possibles sont des 5-uplets de E. Par exemple, (A,B,B,C,A) signifie que le premier jeton est rangé dans A, le deuxième dans B, etc. Il y a alors : Card(E5)=35=243 rangements possibles.
ii) Soit E=1,2,3. Puisque Card(E)=3, le nombre de 3-uplets de E est : Card(E3)=33=27.
On peut le vérifier à l’aide d’un arbre en écrivant l’ensemble des 3-uplets de E.
E3={(a;a;a),(a;a;b),(a;b;a),(a;b;b),(b;a;a),(b;a;b),(b;b;a),(b;b;b)}
En reˊsumeˊ :Le principe additif s’applique pour compterdes eˊleˊments reˊpartis dans des ensembles disjoints.Le principe multiplicatif s’applique pour compterdes k-uplets (ou listes ordonneˊes) d’eˊleˊmentsissus de plusieurs ensembles (ou d’un meˆme ensemble).
Ces deux principes sont fondamentaux pour aborder la combinatoire élémentaire en mathématiques discrètes.