Principe multiplicatif : nombre d’éléments d’un produit cartésien

  1. Langage et notations des ensembles
  2. Sous-ensemble. Inclusion. Complémentaire d’un sous-ensemble.
  3. Égalité de deux ensembles
  4. Intersection et réunion de deux ensembles. Partition d’un ensemble.
  5. Ensemble des parties d’un ensemble $E$
  6. Cardinal d’un ensemble. Ensembles finis
  7. Produit cartésien de deux ensembles.
  1. Principe additif: nombre d’éléments d’une réunion d’ensembles deux à deux disjoints.
  2. Principe multiplicatif : nombre d’éléments d’un produit cartésien.
  3. Ensemble des parties d’un ensemble $E$.
  4. Nombre des parties d’un ensemble à $n$ éléments. Démonstrations de : $\dsum_{k=0}^{n}\dbinom{n}{k}=2^n$.
  5. Nombre des $k$-uplets ou $k$-listes d’éléments d’un ensemble à $n$ éléments
  6. Factorielle d’un entier naturel $n$.
  7. Nombre des $k$-listes ou $k$-uplets d’éléments distincts d’un ensemble à $n$ éléments.
  8. Nombre de permutations d’un ensemble fini à $n$ éléments.
  9. Nombre de combinaisons de $k$ éléments d’un ensemble à $n$ éléments.
    Nombre de parties à $k$ éléments d’un ensemble à $n$ éléments.
    Formules $\dbinom{n}{k} =\dfrac{n(n-1)…(n-k+1)}{k!} =\dfrac{n!}{k!(n-k)!}$.
  10. Propriétés des coefficients binomiaux $k$-parmi-$n$. Relations de Pascal. Méthodes algébriques.
  11. Propriétés des coefficients binomiaux $k$-parmi-$n$. Relations de Pascal. Méthodes combinatoires
  12. Triangle de Pascal et formule du binôme de Newton. Méthode algébrique.

Approfondissement possible

  1. Combinaisons avec répétitions.

1. Ensemble produit cartésien

Définition 1.
Soient $E$ et $F$ deux ensembles non vides.
Le produit cartésien des deux ensembles $E$ et $F$, noté $E\times F$ (lire « $E$ croix $F$») est l’ensemble de tous les couples $(x;y)$ avec $x\in E$ et $y\in F$.
$$(x;y)\in E\times F\Leftrightarrow [x\in E\text{ et }y\in F]$$

Cas particulier très important

Si $E=F$, le produit cartésien $E\times E$ se note $E^2$ et se lit « $E$ au carré », ou encore « $E$ puissance $2$ ». On dit également « $E$ deux » par abus de langage.

On peut généraliser cette définition à $k$ ensembles $E_k$ non vides, $n\geqslant2$.

Définition 2.
Soit $k$ un entier naturel, $k\geqslant2$. Soient $E_1$, $E_2$,$\ldots$, $E_k$, $k$ ensembles non vides.
Le produit cartésien des $k$ ensembles $E_1$, $E_2$,$\ldots$, $E_k$, noté $E_1\times E_2\times\cdots \times E_k$ est l’ensemble de toutes les listes ordonnées $(x_1;x_2;\ldots;x_k)$ avec $x_i\in E_i$ pour tout $i$ allant de $1$ à $k$.
Ces listes ordonnées de $k$ élément s’appellent des $k$-listes ou $k$-uplets.
En particulier, les $2$-listes sont des couples, les $3$-listes des triplets et les $4$-listes des quadruplets.

Cas particulier très important

Si tous les ensembles $E_i$ sont égaux à $E$, le produit cartésien $\underbrace{E\times E\times\ldots\times E}_{k\textrm{ facteurs}}$ se note $E^k$ et se lit « $E$ puissance $k$ ». On dit également « $E$ $k$ » par abus de langage.

Remarque
1°) Dans $E^k$, l’ordre des éléments dans une liste est très important. Si on change l’ordre en gardant les mêmes éléments, on obtient une nouvelle liste différente.

Exemples

Soient $E$, $F$ et $G$ les trois ensembles : $E=\{a;b\}$, $F=\{1;2;3\}$ et $G=\{\alpha;\beta\}$.

$\bullet$ Par un arbre de dénombrement

Fig. 1. Utiliser un arbre pour déterminer un produit cartésien

Par conséquent :
$$\color{brown}{
\begin{array}{l}
E\times F\times G= \{(a;1;\alpha); (a;1;\beta); (a;2;\alpha);\\
\phantom{E\times F\times G=}\quad (a;2;\beta);(a;3;\alpha);(a;3;\beta);\\
\phantom{E\times F\times G=}\quad (b;1;\alpha); (b;1;\beta); (b;2;\alpha);\\
\phantom{E\times F\times G=}\quad (b;2;\beta);(b;3;\alpha);(b;3;\beta);\}\\
\end{array}
}$$

2. Principe multiplicatif : nombre d’éléments d’un produit cartésien

Propriété.
Soit $k$ un entier naturel, $k\geqslant2$. Soient $E_1$, $E_2$,$\ldots$, $E_k$, $k$ ensembles non vides. Le nombre d’élément dans le produit cartésien des $k$ ensembles $E_1$, $E_2$,$\ldots$, est égal au produit des cardinaux de tous les ensembles $E_i$ pour $i$ allant de $1$ à $k$.
$$\begin{array}{c}
\text{Card}(E_1\times E_2\times\cdots \times E_k)=\\
\text{Card}(E_1)\times\text{Card}(E_2)\times\cdots\times\text{Card}(E_k)\\
\end{array}$$

Cas particulier important

Si tous les ensembles $E_i$ sont égaux à $E$, alors le nombre d’éléments de $E^k$ est :
$$\text{Card}(E^k)=\left[\text{Card}(E)\right]^k$$

3. Exercices résolus

Exercice résolu n°1.
Soient $E$ et $F$ les deux ensembles : $E=\{a;b\}$ et $F=\{1;2;3\}$.
1°) Déterminer le nombre d’éléments dans le produit cartésien $E^3$ puis de $F^2$.
2°) Déterminer l’ensemble des éléments des produits cartésiens $E^3$ et de $F^2$, par la méthode de votre choix.

1°a) Nombre d’éléments dans le produit cartésien $E^3$
Card($E$) = $2$. Donc, d’après le principe multiplicatif, le nombre d’éléments du produit cartésien $E^3$, est donné par :
$\text{Card}(E^3)=\left[\text{Card}(E)\right]^3 =2^3=8.$
Conclusion. Le produit cartésien $E^3$ contient 8 éléments.

1°b) Nombre d’éléments dans le produit cartésien $F^2$
Card($F$) = $3$. D’une manière analogue, on obtient :
$\text{Card}(F^2)=\left[\text{Card}(F)\right]^2 = 3^2=9.$$
Conclusion. Le produit cartésien $F^2$ contient 9 éléments.

2°a) $E=\{a;b\}$. On a $E^2=E\times E$. En utilisant un arbre de dénombrement à trois étapes avec les 2 éléments de $E$, on obtient :
$$\color{brown}{
\begin{array}{c}
E^3=E\times E = \{(a;a;a); (a;a;b); (a;b;a);(a;b;b) \\
\phantom{E^3=E\times E =}(b;a;a); (b;a;b); (b;b;a);(b;b;b)\}\\
\end{array}
}$$

2°a) $F=\{1;2;3\}$. On a : $F^2=F\times F$. En utilisant un arbre de dénombrement à trois étapes avec les 3 éléments de $F$, on obtient :
$$\color{brown}{
\begin{array}{c}
F^2=F\times F = \{(1;1); (1;2); (1;3) \\
\phantom{F^2=F\times F =}(2;1); (2;2); (2;3)\\
\phantom{F^2=F\times F =}(3;1); (3;2); (3;3)\}\\
\end{array}
}$$

Exercice résolu n°2.

  1. Langage et notations des ensembles
  2. Sous-ensemble. Inclusion. Complémentaire d’un sous-ensemble.
  3. Égalité de deux ensembles
  4. Intersection et réunion de deux ensembles. Partition d’un ensemble.
  5. Ensemble des parties d’un ensemble $E$
  6. Cardinal d’un ensemble. Ensembles finis
  7. Produit cartésien de deux ensembles.
  1. Principe additif: nombre d’éléments d’une réunion d’ensembles deux à deux disjoints.
  2. Principe multiplicatif : nombre d’éléments d’un produit cartésien.
  3. Ensemble des parties d’un ensemble $E$.
  4. Nombre des parties d’un ensemble à $n$ éléments. Démonstrations de : $\dsum_{k=0}^{n}\dbinom{n}{k}=2^n$.
  5. Nombre des $k$-uplets ou $k$-listes d’éléments d’un ensemble à $n$ éléments
  6. Factorielle d’un entier naturel $n$.
  7. Nombre des $k$-listes ou $k$-uplets d’éléments distincts d’un ensemble à $n$ éléments.
  8. Nombre de permutations d’un ensemble fini à $n$ éléments.
  9. Nombre de combinaisons de $k$ éléments d’un ensemble à $n$ éléments.
    Nombre de parties à $k$ éléments d’un ensemble à $n$ éléments.
    Formules $\dbinom{n}{k} =\dfrac{n(n-1)…(n-k+1)}{k!} =\dfrac{n!}{k!(n-k)!}$.
  10. Propriétés des coefficients binomiaux $k$-parmi-$n$. Relations de Pascal. Méthodes algébriques.
  11. Propriétés des coefficients binomiaux $k$-parmi-$n$. Relations de Pascal. Méthodes combinatoires
  12. Triangle de Pascal et formule du binôme de Newton. Méthode algébrique.

Approfondissement possible

  1. Combinaisons avec répétitions.

Vues : 3392