Nombre de combinaisons ou de parties à $k$ éléments 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. Combinaisons de $k$ éléments d’un ensemble à $n$ éléments

Définition 1.
Soient $n$ et $k$ deux entiers naturels, $0\leqslant k\leqslant n$ et $E$ un ensemble non vide, à $n$ éléments.
Une combinaison de $k$ éléments de $E$ est une partie $A$ de $E$ qui contient $k$ éléments distincts de $E$.
Il existe $k$ éléments $x_1$, $x_2$,$\ldots$, $x_k$ distincts deux à deux tels que
$$A=\{ x_1;x_2;\ldots; x_k\}$$

Remarques
1°) Dans une partie ou une combinaison, les $k$ éléments sont deux à deux distincts.
2°) Une combinaison étant un sous-ensemble de $E$, l’ordre des éléments n’a aucune importance.

3°) Deux combinaisons sont égales si et seulement si, elles contiennent exactement les mêmes éléments. Ainsi, $\{a;b\}$ ; $\{b;a\}$ sont identiques.

Exemples

Soit $E={a;b;c}$ un ensemble à trois éléments.

  • Il existe une seule combinaison à $0$ élément : $\emptyset$ ;
  • Il existe trois combinaisons à $1$ éléments : $\{a\}$ ; $\{b\}$ ;$\{c\}$ ;
  • Il existe trois combinaisons à $2$ éléments : $\{a;b\}$ ; $\{a;c\}$ ;$\{b;c\}$ ;
  • Il existe une seule combinaisons à $3$ éléments : $\{a;b;c\}$.

2. Nombre de combinaisons de $k$ éléments d’un ensemble à $n$ éléments

Propriété 1.
Soient $n$ et $k$ deux entiers naturels, $0\leqslant k\leqslant n$ et $E$ un ensemble non vide, à $n$ éléments.
Le nombre de parties ou de combinaison de $k$ éléments de $E$, noté $\dbinom{n}{k}$, est donné par la formule :
$$\dbinom{n}{k}=\dfrac{\overbrace{n(n-1)(n-2)\cdots(n-k+1)}^{k\text{ facteurs}}}{k!}$$

Définition 2.
Les nombres entiers $\dbinom{n}{k}$ qu’on appelait les $k$-parmi-$n$ en 1ère, s’appellent aussi les « coefficients binomiaux » ou « coefficients du binôme ».

Ce nombres donnent le nombre de $k$ succès dans une loi binomiale ${\mathcal B}(n;p)$ de paramètres $n$ et $p$.

Remarques
On peut trouver des exemples de combinaisons ou de parties à $k$ éléments dans :
$\bullet$ Les mots de $k$ caractères tous différents ;
$\bullet$ Les groupes de $k$ personnes dans un ensemble à $n$ éléments ;
$\bullet$ Les tirages de $k$ boules dans une urne contenant $n$ boules numérotées de $1$ à $n$.

Une $k$-liste d’éléments distincts deux à deux s’obtient en choisissant successivement ses éléments $x_i$ distincts deux à deux, de la manière suivante :
On choisit $x_1$ parmi les $n$ éléments de $E$ ;
$x_1$ étant choisi, on choisit $x_2$ parmi les $(n-1)$ éléments restant dans $E$ ;
$x_1$ et $x_2$ étant choisis, on choisit $x_3$ parmi les $(n-2)$ éléments restant dans $E$ ;
et ainsi de suite…
$x_1$, $x_2$,$\ldots$, $x_{k-1}$ étant choisis, il reste : $n-(k-1)=\color{brown}{n-k+1}$ choix pour $x_k$.
Ce qui donne :
$$\begin{array}{|c|c|c|c|}\hline
x_1&x_2&x_3&\ldots&x_k\\ \hline
n\text{ choix}&(n-1)\text{ choix}&(n-2)\text{ choix}&\ldots&(n-(k-1))\text{ choix}\\ \hline
\end{array}$$
Par conséquent, d’après le principe multiplicatif, le nombre de $k$-listes $L_k$ 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}}$$
Or, à chaque partie $A_k$ ayant $k$ éléments (distincts) de $E$, correspondent $k!$ ($k$ factorielle) permutations donnant $k!$ possibilités de construire des $k$-listes avec les mêmes éléments deux à deux distincts de $A_k$. Ce qui donne la correspondance :
$$\color{brown}{\text{1 partie }A_k \longleftrightarrow k!\text{ listes différentes à } k \text{ éléments}}$$
Par conséquent, le nombre de parties $\dbinom{n}{k}$ de $k$ éléments dans un ensemble à $n$ éléments est égal au nombre de $k$-listes d’éléments distincts deux à deux, divisé par $k!$.

Conclusion. $\color{brown}{\boxed{\;\dbinom{n}{k}=\dfrac{\overbrace{n(n-1)(n-2)\cdots(n-k+1)}^{k\text{ facteurs}}}{k!}\;}}\;(1)$
Cette formule ainsi écrite donne une manière très pratique pour les calculs numériques.

Cas particulier (de référence)

1°) Pour tout entier naturel $n$ :
$\quad$a) $\boxed{\;\dbinom{n}{0}=1\;}$ ; b) $\boxed{\;\dbinom{n}{n}=1\;}$ ;
$\quad$c) $\boxed{\;\dbinom{n}{1}=n\;}$ ; d) $\boxed{\;\dbinom{n}{n-1}=n\;}$.
2°) Pour tout entier $k$, $0\leqslant k\leqslant n$ :
$\quad$ e) $\boxed{\;\dbinom{n}{n-k}=\dbinom{n}{k}\;}$.
3°) Pour tout entier $k$, $0\leqslant k\leqslant n-1$ :
$\quad$f) $\boxed{\;\dbinom{n+1}{k+1}=\dbinom{n}{k}+\dbinom{n}{k+1}\;}$

Exemple

Exercice résolu n°1.
Calculer $\dbinom{20}{5}$.

Calcul de $\dbinom{20}{5}$

$\dbinom{20}{5}=\dfrac{20!}{5!\times (20-5)!}$
$\dbinom{20}{5}= \dfrac{\overbrace{20\times19\times18\times17\times16}^{5\text{ facteurs}}}{5\times4\times3\times2\times1}$.
On décompose pour simplifier :
$\dbinom{20}{5}=
\dfrac{(\not5\times\not4)\times19\times(3\times\not3\times\not2)\times17\times16}{\not5\times\not4\times\not3\times\not2\times\not1}$.
Ce qui donne :
$\dbinom{20}{5}=19\times3\times17\times16=15504$.

Conclusion. $\color{brown}{\boxed{\;\dbinom{20}{5}=15504\;}}$.

Propriété 2.
Pour tout entier naturel $n$ et tout entier $k$ tel que $0\leqslant k \leqslant n$, on a :
$$\dbinom{n}{k}=\dfrac{n!}{k!(n-k)!}$$

A faire

3. Exercices résolus

Exercice résolu n°1.
Soit $E={a;b;c}$ un ensemble à trois éléments.
Déterminer par le calcul le nombre de combinaisons à $0$, $1$ ; $2$ et $3$ éléments de $E$.

  • Pour $k=0$ On a $\dbinom{3}{0}=1$. Valeur de référence.
    Pour $k=1$ On a $\dbinom{3}{1}=3$.
    Et par le calcul : $\dbinom{3}{1}=\dfrac{\overbrace{3}^{1\text{ facteur}}}{1!}=3$
  • Pour $k=2$ On a $\dbinom{3}{2}=\dbinom{3}{3-1}=3$.
    Et par le calcul : $\dbinom{3}{1}=\dfrac{\overbrace{3\times2}^{2\text{ facteurs}}}{1!}=3$
  • Pour $k=3$ On a $\dbinom{3}{3}=1$.
    Et par le calcul : $\dbinom{3}{3}=1$. Valeur de référence.

Exercice résolu n°2.
Calculer : $\dbinom{10}{1}$ ; $\dbinom{10}{3}$ ; $\dbinom{10}{7}$ ; $\dbinom{10}{5}$ et $\dbinom{10}{9}$.

1°) $\dbinom{10}{1}=1$.
2°) $\dbinom{10}{3}=\dfrac{\overbrace{10\times9\times8}^{3\text{ facteurs}}}{3!}=\dfrac{(\not2\times5)\times(\not3\times3)\times8}{\not3\times\not2\times1}=120$.
3°) etc

Exercice résolu n°3.

A suivre

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