COEFFICIENTS BINOMIAUX, K PARMI N

Coefficients binomiaux $\left ( \begin{array}{c} n \\ k \end{array} \right)$, $n \in \mathbb{N}$, $k \in \mathbb{N}$, $n \geq k$

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$.