- Langage et notations des ensembles
- Sous-ensemble. Inclusion. Complémentaire d’un sous-ensemble.
- Égalité de deux ensembles
- Intersection et réunion de deux ensembles. Partition d’un ensemble.
- Ensemble des parties d’un ensemble $E$
- Cardinal d’un ensemble. Ensembles finis
- Produit cartésien de deux ensembles.
- Principe additif: nombre d’éléments d’une réunion d’ensembles deux à deux disjoints.
- Principe multiplicatif : nombre d’éléments d’un produit cartésien.
- Ensemble des parties d’un ensemble $E$.
- Nombre des parties d’un ensemble à $n$ éléments. Démonstrations de : $\dsum_{k=0}^{n}\dbinom{n}{k}=2^n$.
- Nombre des $k$-uplets ou $k$-listes d’éléments d’un ensemble à $n$ éléments
- Factorielle d’un entier naturel $n$.
- Nombre des $k$-listes ou $k$-uplets d’éléments distincts d’un ensemble à $n$ éléments.
- Nombre de permutations d’un ensemble fini à $n$ éléments.
- 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)!}$. - Propriétés des coefficients binomiaux $k$-parmi-$n$. Relations de Pascal. Méthodes algébriques.
- Propriétés des coefficients binomiaux $k$-parmi-$n$. Relations de Pascal. Méthodes combinatoires
- Triangle de Pascal et formule du binôme de Newton. Méthode algébrique.
Approfondissem*nt possible
- 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.
- Langage et notations des ensembles
- Sous-ensemble. Inclusion. Complémentaire d’un sous-ensemble.
- Égalité de deux ensembles
- Intersection et réunion de deux ensembles. Partition d’un ensemble.
- Ensemble des parties d’un ensemble $E$
- Cardinal d’un ensemble. Ensembles finis
- Produit cartésien de deux ensembles.
- Principe additif: nombre d’éléments d’une réunion d’ensembles deux à deux disjoints.
- Principe multiplicatif : nombre d’éléments d’un produit cartésien.
- Ensemble des parties d’un ensemble $E$.
- Nombre des parties d’un ensemble à $n$ éléments. Démonstrations de : $\dsum_{k=0}^{n}\dbinom{n}{k}=2^n$.
- Nombre des $k$-uplets ou $k$-listes d’éléments d’un ensemble à $n$ éléments
- Factorielle d’un entier naturel $n$.
- Nombre des $k$-listes ou $k$-uplets d’éléments distincts d’un ensemble à $n$ éléments.
- Nombre de permutations d’un ensemble fini à $n$ éléments.
- 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)!}$. - Propriétés des coefficients binomiaux $k$-parmi-$n$. Relations de Pascal. Méthodes algébriques.
- Propriétés des coefficients binomiaux $k$-parmi-$n$. Relations de Pascal. Méthodes combinatoires
- Triangle de Pascal et formule du binôme de Newton. Méthode algébrique.
Approfondissem*nt possible
- Combinaisons avec répétitions.
