Réunion et produit d'ensembles, k-uplet

Signaler

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 EE un ensemble fini. Le cardinal de EE, noté Card(E)\text{Card}(E), est le nombre d’éléments de l’ensemble EE.

Exemple :
E={a,b,c,d}E = \{a, b, c, d\} est un ensemble fini et Card(E)=4\text{Card}(E) = 4.

Remarques :
i) On note parfois E\sharp E ou E|E| au lieu de Card(E)\text{Card}(E).
ii) Card()=0\text{Card}(\emptyset) = 0.
iii) Certains ensembles ne sont pas finis : N,R\mathbb{N}, \mathbb{R}, etc.

Définition :
Deux ensembles AA et BB sont disjoints si AB=A \cap B = \emptyset.

picture-in-text

Exemple :
A={1,2,3}A = \{1, 2, 3\} et B={4,5}B = \{4, 5\} sont disjoints car AB=A \cap B = \emptyset.

II. Réunion d'ensembles ou le principe additif

Si un ensemble EE est la réunion de plusieurs sous-ensembles deux à deux disjoints, alors le nombre d’éléments de EE est la somme des nombres d’éléments de chacun de ces sous-ensembles.

Formellement, si
E=A1A2Am E = A_1 \cup A_2 \cup \cdots \cup A_m et si AiAj= A_i \cap A_j = \varnothing pour tout ij i \neq j , alors :
card(E)=card(A1)+card(A2)++card(Am) \mathrm{card}(E) = \mathrm{card}(A_1) + \mathrm{card}(A_2) + \cdots + \mathrm{card}(A_m) .

Exemple :

Si EE se décompose en 3 sous-ensembles disjoints AA, BB et CC, on a :
card(E)=card(A)+card(B)+card(C) \mathrm{card}(E) = \mathrm{card}(A) + \mathrm{card}(B) + \mathrm{card}(C) .

picture-in-text

Exemple :

Soit un ensemble EE partitionné en 5 sous-ensembles disjoints E1,E2,E3,E4,E5E_1, E_2, E_3, E_4, E_5 contenant respectivement 2, 10, 4, 3 et 6 éléments. On a :
card(E)=2+10+4+3+6=25 \mathrm{card}(E) = 2 + 10 + 4 + 3 + 6 = 25 .

Corollaire : Soient AA une partie d’un ensemble fini EE et A\overline A le complémentaire de AA dans EE.

picture-in-textOn a : Card(E)=Card(A)+Card(A)\text{Card}(E) = \text{Card}(A) + \text{Card}(\overline A).

III. Produit cartésien ou le principe multiplicatif

Définition :
Soient AA et BB deux ensembles non vides. Le produit cartésien de AA et BB est l’ensemble noté A×BA \times B (se lit « croix AA BB »), constitué des couples (a,b)(a, b)aa est un élément de AA et bb un élément de BB. Plus formellement : A×B={(a,b)aA et bB}A \times B = \{(a, b) \mid a \in A \text{ et } b \in B\}.

Exemple :
Soient A={x,y}A = \{x, y\} et B={1,2,3}B = \{1, 2, 3\}. Alors :
A×B={(x,1),(x,2),(x,3),(y,1),(y,2),(y,3)}A \times B = \{(x, 1), (x, 2), (x, 3), (y, 1), (y, 2), (y, 3)\}.

Propriété :
Soient AA et BB deux ensembles finis. Alors : Card(A×B)=Card(A)×Card(B)\text{Card}(A \times B) = \text{Card}(A) \times \text{Card}(B).

Plus généralement, pour des ensembles finis A1,A2,,AkA_1, A_2, \ldots, A_k,
card(A1×A2××Ak)=card(A1)×card(A2)××card(Ak) \mathrm{card}(A_1 \times A_2 \times \cdots \times A_k) = \mathrm{card}(A_1) \times \mathrm{card}(A_2) \times \cdots \times \mathrm{card}(A_k) .

IV. k-uplets d'un ensemble fini

1.1. Un peu de vocabulaire : couple, triplet et k-uplet d'un ensemble à nn éléments

Soit kk un entier naturel non nul

\circ\quad Couple (ou 2-uplet) : on note (a,b) (a, b) un objet composé de deux éléments aa et bb.

\circ\quadTriplet (ou 3-uplet) : (a,b,c) (a, b, c) .

\circ\quad k-uplet (ou k-liste) : (x1,x2,,xk) (x_1, x_2, \ldots, x_k) où chaque xix_i est un élément de l’ensemble considéré.

Remarque : L’ordre compte dans un k-uplet :
(a,b)(b,a) (a, b) \neq (b, a) en général si ab a \neq b .

L'ensemble EkE^k

Lorsque tous les ensembles sont identiques, c’est-à-dire E1=E2==Ek=EE_1 = E_2 = \cdots = E_k = E, on note :
Ek={(x1,x2,,xk)  xiA pour i=1,,k} E^k = \{(x_1, x_2, \ldots, x_k)\ \mid\ x_i \in A \text{ pour } i=1,\ldots,k \}

\circ\quadUn élément de EkE^k est donc un k-uplet d’éléments de EE.

Un exemple avec deux ensembles :Si card(A)=4\mathrm{card}(A) = 4 et card(B)=7\mathrm{card}(B) = 7, alors
card(A×B)=4×7=28 \mathrm{card}(A \times B) = 4 \times 7 = 28 .Concrètement, il y a 28 couples (a,b)(a, b) possibles avec aAa \in A et bBb \in B

Autres exemples :
i) (a,b,q)(a, b, q) est un 33-uplet de l’ensemble des 2626 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}\{0,1,2,\ldots,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 10^4 = 10 \times 10 \times 10 \times 10 = 10~000 .

Théorème :
Soient k1k \geq 1 et EE un ensemble fini de cardinal nn. Le nombre de kk-uplets de EE est nkn^k, soit :
Card(Ek)=nk\text{Card}(E^k) = n^k.

Autrement dit, le nombre de k-upletsd’un ensemble de n eˊleˊments est : nk\boxed{ \begin{array}{l}\text{Autrement dit,}\textbf{ le nombre de k-uplets}\\\text{d’un ensemble de } n\textbf{ éléments est : }n^k\end{array} }

Exemple :
i) On dispose de trois boîtes notées A,B,CA, 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,CE = {A, B, C} l’ensemble des boîtes. Les différents rangements possibles sont des 55-uplets de EE. Par exemple, (A,B,B,C,A)(A, B, B, C, A) signifie que le premier jeton est rangé dans AA, le deuxième dans BB, etc. Il y a alors : Card(E5)=35=243 rangements possibles.\text{Card}(E^5) = 3^5 = 243 \text{ rangements possibles.}

ii) Soit E=1,2,3E = {1, 2, 3}. Puisque Card(E)=3\text{Card}(E) = 3, le nombre de 33-uplets de EE est : Card(E3)=33=27\text{Card}(E^3) = 3^3 = 27.
On peut le vérifier à l’aide d’un arbre en écrivant l’ensemble des 33-uplets de EE.

picture-in-text

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)}E^3 = \lbrace (a ; a ; a), (a ; a ; b), (a ; b ; a), (a ; b ; b), (b ; a ; a), (b ; a ; b), (b ; b ; a), (b ; b ; b) \rbrace

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).\boxed{ \begin{array}{l} \textbf{En résumé :}\\[6pt] \textbf{Le principe additif} \text{ s’applique pour compter}\\ \quad \text{des éléments répartis dans des ensembles } \textbf{disjoints}.\\[6pt] \textbf{Le principe multiplicatif} \text{ s’applique pour compter}\\ \quad \text{des } \textbf{k-uplets} \text{ (ou listes ordonnées) d’éléments}\\ \quad \text{issus de plusieurs ensembles (ou d’un même ensemble).} \end{array} }


Ces deux principes sont fondamentaux pour aborder la combinatoire élémentaire en mathématiques discrètes.