Terminale > Mathématiques > Combinatoire et dénombrement > Coefficients binomiaux, k parmi n
Accède gratuitement à cette vidéo pendant 7 jours
Profite de ce cours et de tout le programme de ta classe avec l'essai gratuit de 7 jours !
On dispose d'un ensemble $E$ à $n$ éléments ($n \in \mathbb{N}^*$), on compte le nombre de parties à $k$ éléments, $1 \leq k \leq n$, de $E$.
Deux questions sont à se poser lorsque l'on s'intéresse à un problème de dénombrement.
En réalisant un tirage de $k$ éléments parmi $n$ éléments, on doit se demander si l'ordre est important et si il y a de la répétition.
Ici, on s'intéresse à une partie à $k$ éléments, ce qui correspond à une poignée de $k$ éléments : l'ordre n'a donc pas d'importance puisque les $k$ éléments sont choisis en même temps et il n'y a pas de répétition.
Par définition, on note $\left ( \begin{array}{c} n \\ k \end{array} \right)$ le nombre de parties $k$ éléments dans un ensemble $E$ à $n$ éléments, et on lit ce nombre "$k$ parmi $n$".
Exemple :
Un sélectionneur doit choisir $k$ joueurs parmi $n \geq k$ et nommer parmi eux le capitaine.
Pour résoudre ce problème, deux méthodes sont possibles.
Première méthode :
Il choisit tout d'abord les $k$ joueurs parmi les $n$ joueurs possibles. Il n'y a pas d'ordre et pas de répétition. Ainsi, il y a $\left ( \begin{array}{c} n \\ k \end{array} \right)$ possibilités.
Parmi ces $k$ joueurs, il nomme le capitaine. Il y a donc $k$ choix possibles.
Le principe multiplicatif s'appliquant, le nombre d'équipes qu'il peut former est donc $k \left ( \begin{array}{c} n \\ k \end{array} \right)$
Seconde méthode :
On peut aussi procéder différemment. On peut en effet sélectionner d'abord le capitaine.
Il y a donc $n$ choix possibles pour le capitaine. Il s'agit ensuite de compléter l'équipe (un joueur ayant déjà été choisi : le capitaine). Il faut donc sélectionner $k - 1$ joueurs parmi les $n - 1$ disponibles, c'est à dire $\left ( \begin{array}{c} n - 1 \\ k - 1 \end{array} \right)$
Le principe multiplicatif s'appliquant, le nombre d'équipes qu'il peut former est donc $n \left ( \begin{array}{c} n - 1 \\ k - 1 \end{array} \right)$
Le nombre d'équipes étant le même quelque soit la méthode de résolution choisie, on a donc l'égalité suivante : $k \left ( \begin{array}{c} n \\ k \end{array} \right) = n \left ( \begin{array}{c} n - 1 \\ k - 1 \end{array} \right)$, que l'on préfère retenir sous la forme :
$ \left ( \begin{array}{c} n \\ k \end{array} \right) = \dfrac{n}{k} \left ( \begin{array}{c} n - 1 \\ k - 1 \end{array} \right)$.
En appliquant cette relation au choix de $k - 1$ éléments parmi $n - 1$ éléments on a :
$ \left ( \begin{array}{c} n - 1 \\ k - 1 \end{array} \right) = \dfrac{n- 1}{k - 1} \left ( \begin{array}{c} n - 2 \\ k - 2 \end{array} \right)$.
Ainsi, $ \left ( \begin{array}{c} n \\ k \end{array} \right) = \dfrac{n}{k} \left ( \begin{array}{c} n - 1 \\ k - 1 \end{array} \right) =\dfrac{n}{k} \times \dfrac{n- 1}{k - 1} \left ( \begin{array}{c} n - 2 \\ k - 2 \end{array} \right) $.
On réitère ce procédé jusqu'à ce que $k$ atteigne la valeur $1$ :
$ \left ( \begin{array}{c} n \\ k \end{array} \right) = \dfrac{n(n- 1)(n-2)...\big(n-(k-2)\big)}{k(k - 1)(k-2)...2} \left ( \begin{array}{c} n - (k-1) \\ 1 \end{array} \right) $
Il s'agit à présent de déterminer la valeur de $\left ( \begin{array}{c} n - (k-1) \\ 1 \end{array} \right) $. Cela correspond à choisir $1$ élément parmi $n - (k-1)$ éléments. Il y a donc $n - (k-1) $ choix possibles.
Ainsi, $\left ( \begin{array}{c} n - (k-1) \\ 1 \end{array} \right) = n - (k-1) = n - k +1$.
Finalement, $ \left ( \begin{array}{c} n \\ k \end{array} \right) = \dfrac{n(n- 1)(n-2)...(n-k+2)(n-k+1)}{k!} $.
Enfin, il est d'usage de transformer la formule précédente pour simplifier son écriture. On peut pour cela remarquer que le numérateur ressemble au développement de $n!$ même si les premiers facteurs sont manquants.
L'idée est alors des les rajouter, en multipliant au numérateur et au dénominateur par la quantité manquante, à savoir $(n - k)(n-k-1)...2\times 1$. On remarque que ce produit est égal à $(n - k)!$.
Ainsi, $ \left ( \begin{array}{c} n \\ k \end{array} \right) = \dfrac{n!}{k!(n-k)!} $.
On admettra que cette formule est valable pour $0 \leq k \leq n$.
Cette fiche de cours est réservée uniquement à nos abonnés. N'attends pas pour en profiter, abonne-toi sur lesbonsprofs.com. Tu pourras en plus accéder à l'intégralité des rappels de cours en vidéo ainsi qu'à des QCM et des exercices d'entraînement avec corrigé en texte et en vidéo.