Nombre de $k$-listes ou $k$-uplets d’éléments distincts d’un ensemble à $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$-listes d’éléments distincts deux à deux d’un ensemble à $n$ éléments

Définition 1.
Soit $k$ un entier naturel, $k\geqslant2$ et $E$ un ensemble non vide, à $n$ éléments.
$(x_1;x_2;\ldots;x_k)$ est une $k$-liste ou un $k$-uplet d’éléments distincts deux à deux de $E$ si, et seulement si, pour tout $i$ et tout $j$ compris entre $1$ et $k$ :
$$i\not= j\Rightarrow x_i\not=x_j$$

Dans certains ouvrages, une $k$-liste d’éléments distincts deux à deux d’un ensemble à $n$ éléments s’appelle un « arrangement de $k$ éléments parmi $n$ ».

Remarque
Naturellement, dans une $k$-liste d’éléments distincts deux à deux d’un ensemble à $n$ éléments, l’ordre des éléments est très important. Si on change l’ordre en gardant les mêmes éléments, on obtient une nouvelle liste différente.

Propriété 1.
Soient $n$ un entier naturel non nul et $E$ un ensemble non vide à $n$ éléments.
Alors le nombre $k$-listes ou $k$-uplets d’éléments distincts deux à deux de $E$ est égal à $$\underbrace{n\times(n-1)\times(n-2)\times\ldots\times (n-k+1)}_{k\text{ facteurs}}$$
ou encore : $\qquad\dfrac{n!}{(n-k)!}$

Exemple

Exercice résolu n°1.
Avec cinq rouleaux de tissu de couleurs différentes, combien de drapeaux peut-on former avec 3 colonnes de couleurs différentes ?

On choisit l’ensemble $E$ de cinq couleurs, par exemple : $E =\{\,$Bleu, Blanc, Rouge, Vert et Jaune$\,\}$. $\text{Card}(E)=5$. Un drapeau correspond au choix d’une $3$-liste d’éléments deux à deux distincts dans $E$.
D’après le principe multiplicatif, le nombre des $3$-listes d’éléments deux à deux distincts dans un ensemble $E$ à $5$ éléments, est :
$\dfrac{5!}{(5-3)!}=\dfrac{5!}{2!}=\underbrace{5\times4\times3}_{3\text{ facteurs}}=60$.
Conclusion. On peut former $60$ drapeaux de $3$ colonnes de de couleurs différentes.

Propriété 2.
Pour tout entier naturel $n$ et tout entier $k$ tel que $0\leqslant k \leqslant n$, on a :
$$\color{brown}{\boxed{\;\underbrace{n(n-1)(n-2)\cdots(n-k+1)}_{k\text{ facteurs}}=\dfrac{n!}{(n-k)!}\;}}$$

$\begin{array}{l}
\underbrace{n(n-1)(n-2)\cdots(n-k+1)}_{k\text{ facteurs}}\\
=\dfrac{n(n-1)(n-2)\cdots(n-(k-1))\color{brown}{\times (n-k)!}}{\color{brown}{(n-k)!}}\\
=\dfrac{n(n-1)(n-2)\cdots(n-(k-1))(n-k)(n-k-1)\ldots\times2\times1}{(n-k)!}\\
=\dfrac{n!}{(n-k)!}\\
\end{array}$
Conclusion. Pour tout $n\in\N$ et tout $k$ tel que $0\leqslant k \leqslant n$ : $$\color{brown}{\boxed{\;\underbrace{n(n-1)(n-2)\cdots(n-k+1)}_{k\text{ facteurs}}=\dfrac{n!}{(n-k)!}\;}}$$

2. Autre manière de comprendre les $k$-listes d’éléments distincts d’un ensemble à $n$ éléments

Définir une $k$-liste ou un $k$-uplet d’un ensemble $E$ à $n$ éléments ; c’est choisir une liste d’éléments $x_1$ ; $x_2$ ; $\ldots$ ; $x_k$ distincts deux à deux dans $E$, pris dans un certain ordre.

  • Pour $x_1$, nous avons $n$ choix ;
  • $x_1$ étant choisi, nous avons $(n-1)$ choix pour $x_2$ ;
  • $x_1$ et $x_2$ étant choisis, nous avons $(n-2)$ choix pour $x_3$ ;
  • et ainsi de suite$\ldots$ jusqu’au $k$-ème élément de la liste :
  • $x_1 ; x_2;\ldots x_{k-1}$ étant choisis, nous avons $(n-(k-1))$ choix pour $x_k$ ;

Par conséquent, d’après le principe multiplicatif, il existe $\color{brown}{\underbrace{n\times(n-1)\times(n-2)\times\ldots\times (n-k+1)}_{k\text{ facteurs}}}$ possibilités de choisir une $k$-liste d’éléments distincts deux à deux de $E$.

Exemple

Exercice résolu n°2.
Combien peut on former de « mots » à quatre lettres distinctes deux à deux, de l’alphabet français, ayant ou non un sens ? 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 distincts deux à deux de $E$.
On sait que le nombre de $4$-listes d’éléments distincts deux à deux d’un ensemble à $26$ éléments est égal à $\underbrace{26\times25\times24\times23}_{4\text{ facteurs}}$.
Conclusion. On peut former $358.800$ « mots possibles » à cinq lettres distinctes deux à deux, ayant ou non un sens avec les 26 lettres de l’alphabet.

3. Exercices résolus

Exercice résolu n°3.

  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 : 884