Nombre de $k$-uplets ou $k$-listes d’un ensemble fini à $n$ éléments

  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. $k$-uplets ou $k$-listes d’un ensemble fini à $n$ éléments

Définition 2.
Soit $k$ un entier naturel, $k\geqslant2$ et $E$ un ensembles non vide.
Une $k$-listes ou un $k$-uplets est une liste ordonnée de $k$ éléments distincts ou égaux de $E$.
C’est un élément du produit cartésien $\color{brown}{E^k=\underbrace{E\times E\times\ldots \times E}_{k\text{ facteurs}}}$ de la forme : $$(x_1;x_2;\ldots;x_k)\in E^k$$

Remarque
Dans $E^k$, l’ordre des éléments dans une $k$-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

2. Nombre de $k$-uplets ou $k$-listes d’un ensemble fini à $n$ éléments

En applique le principe multiplicatif des cardinaux d’un produit cartésien $E^k$, on obtient le résultat très important suivant.

Propriété 1.
Soient $n$ et $k$ deux entiers naturels non nul, et $E$ un ensembles non vide à $n$ éléments. Alors le nombre $k$-listes ou $k$-uplets d’éléments (non nécessairement distincts) de $E$ est égal à $n^k$. $$\text{Card}(E^k)=n^k$$

En effet, le cardinal du produit cartésien de $k$ ensembles (ici tous égaux à $E$), est égal au produit des cardinaux de ces $k$ ensembles. Ce qui donne : $$\text{Card}(E^k)=\left[\text{Card}(E)\right]^k$$
D’où le résultat.

Autre manière de comprendre les $k$-listes :

Définir une $k$-liste ou un $k$-uplet de $E$, c’est chosir une liste d’éléments $x_1$ ; $x_2$ ; $\ldots$ ; $x_k$ distincts ou égaux dans $E$, prix dans un certain ordre :

  • Pour $x_1$, nous avons $n$ choix ;
    Les $x_i$ n’étant pas nécessairement distincts ;
  • Pour $x_2$, nous avons $n$ choix ;
  • Pour $x_3$, nous avons $n$ choix ;
    et ainsi de suite$\ldots$ jusqu’au $k$-ème élément de la liste :
  • Pour $x_k$, nous avons $n$ choix.

$$\begin{array}{|c|c|c|c|c|}\hline
1er&2e&3e\cdots&ke\\ \hline
n\text{ choix}&n\text{ choix}&n\text{ choix}&\cdots&n\text{ choix}\\ \hline
\end{array}$$
D’après le principe multiplicatif, il existe $\color{brown}{\underbrace{n\times n\times\ldots \times n}_{k\text{ facteurs}}=n^k}$ possibilités de choisir une $k$-liste d’éléments de $E$.

Exemple

Exercice résolu n°1.
Combien peut on former de listes de quatre lettres de l’alphabet français ? Justifier.

L’ensemble $E$ est formé de $26$ lettres de l’alphabet. Donc : $\text{Card}(E)=26$.
On veut former des $4$-listes d’éléments de $E$. On sait que le nombre de $k$-listes d’élément d’un ensemble à $n$ éléments est égal à $n^k=26^4$.
Donc, on obtient $456976$ possibilités de former une 4-liste d’éléments de $E$.

3. Exercices résolus

Exercice résolu n°2.
Le code d’un cadenas est composé de 2 lettres et trois chiffres. Déterminer le nombre de « combinaisons » possibles pour choisir un code ?

Le code est composé de deux parties. Deux cases pour les lettres et trois cases pour les chiffres.
$\bullet$ Pour les deux lettres : $$\begin{array}{|c|c|}\hline
\text{1re lettre}&\text{2e lettre}\\ \hline
26\text{ choix}&26\text{ choix}\\ \hline
\end{array}$$ Nous avons donc $26^2$ chois pour les deux lettres.

$\bullet$ Pour les trois chiffres : $$\begin{array}{|c|c|c|}\hline
\text{1er chiffre} &\text{2e chiffre} &\text{3e chiffre}\\ \hline
10\text{ choix}&10\text{ choix}&10\text{ choix}\\ \hline
\end{array}$$ Nous avons donc $10^2$ chois pour les deux lettres.

Maintenant, d’après le principe multiplicatif, on obtient le nombre de toutes les « combinaisons » possibles : $$26^2\times 10^3=676\,000$$
Conclusion. Avec 2 lettres suivies de trois chiffres, il existe $676\,000$ possibilités de choisir un code pour ce cadenas.

Exercice résolu n°3.
Une plaque minéralogique en France est composée de $7$ cases : 2 lettres suivies de 3chiffres, puis de deux lettres. Il existe certaines exceptions.
$\bullet$ Les lettres $I$ et $O$ sont exclues pour ne pas créer de confusions avec les nombres $1$ et $0$.
$\bullet$ La paire $WW$ à droite est réservée aux voitures neuves.
$\bullet$ La paire $SS$ est exclue à gauche et à droite.
Déterminer le nombre total de plaques minéralogiques qu’on peut créer en France.

  • Avec le même raisonnement que dans l’exercice précédent, et avec les deux lettres $I$ et $O$ exclues (il en reste $24$), le nombre total de plaques minéralogiques sans les exceptions sur les lettres est : $$24^2\times 10^3\times 24^2$$
  • A terminer.
  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 : 1289