Coefficients binomiaux, k parmi n

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

Coefficients binomiaux (k parmi n), propriétés

Coefficients binomiaux : $\binom{n}{k}$, $n \in \mathbf{N}$, $k \in \mathbf{N}$, $n\geq k$

Définition

On rappelle la formule des coefficients binomiaux :

$\binom{n}{k} = \dfrac{n!}{k!(n-k)!}$ pour $0\leq k\leq n$.

Regardons quelques exemples à connaitre :

$\binom{n}{0} = \dfrac{n!}{0!(n)!}=1$

En effet par convention, $0!=1$

Le résultat  est cohérent car le coefficient binomial $\binom{n}{0}$ revient à dénombrer les parties à 0 élément d’un ensemble à n éléments. Il n’y a qu’un ensemble possible, c’est l’ensemble vide.

$\binom{n}{1} = \dfrac{n!}{1!(n-1)!}=n$

En effet, $1!=1$ et $n!=n\times (n-1)!$

Le résultat  est cohérent car le coefficient binomial $\binom{n}{1}$ revient à dénombrer les parties à 1 élément d’un ensemble à n éléments. Il n’y a donc que les singletons possibles et il y a n singletons : {1}, {2},…,{n}.

$\binom{n}{2} = \dfrac{n!}{2!(n-2)!}$

$\binom{n}{2} = \dfrac{n(n-1)\times(n-2)!}{2\times (n-2)!}$

$\binom{n}{2} = \dfrac{n(n-1)}{2}$

En effet, $2!=2\times 1=2$.

Cette formule n’est pas nécessairement à connaitre mais permet d’avancer plus vite dans certains exercices.

Propriétés

Intéressons-nous maintenant à quelques formules à connaitre :

• La formule de symétrie :

$\binom{n}{k}=\binom{n}{n-k}$

Démontrons cette formule par une méthode de dénombrement.

$\binom{n}{k}$ correspond par exemple au nombre de façon de composer une équipe de k joueurs avec n joueurs disponibles. Et choisir dans un groupes de n joueurs les k joueurs qui vont aller sur le terrain revient au même que de choisir les n-k joueurs qui vont rester sur le banc. Ainsi, dans un effectif de n joueurs, il y a autant de composition d’équipe avec k joueurs que de composition de banc de touche avec les n-k joueurs restant (si j’intervertis 2 joueurs, je forme une nouvelle équipe mais aussi un nouveau banc de touche).

Il est aussi possible de redémontrer cette formule en développant avec les factorielles.

On en tire deux exemples à connaitre :

$\binom{n}{n} =\binom{n}{n-n} =\binom{n}{0}=1$

$\binom{n}{n-1} =\binom{n}{n-(n-1)} =\binom{n}{1}=n$

• La formule de Pascal :

$\binom{n+1}{k+1}=\binom{n}{k+1}+\binom{n}{k}$ avec $0\leq k\leq n-1$.

La formule de Pascal s’appelle ainsi car Pascal a mis en place le triangle de Pascal qui permet d’avoir les coefficients dans les identités remarquables généralisées :

$(a+b)^2, (a+b)^3, (a+b)^4…$.

En réalité ce n’est pas Pascal le premier qui a produit ce triangle mais c’est bien antérieur.

Démontrons cette formule par le dénombrement:

Soit E un ensemble à n+1 éléments :

$E={1,2,…,n+1}$

Nous devons fabriquer des parties à k+1 éléments. Dans la partie que nous fabriquons, soit elle contient n+1, soit elle ne le contient pas.

Soit n+1 est dans la partie : je dois encore choisir k éléments (j’en ai déjà 1 et il m’en faut k+1) parmi n (j’ai déjà choisi l’élément n+1, maintenant je ne peux piocher que parmi n éléments) : Il y a donc $\binom{n}{k}$ façons de fabriquer une partie à k+1 éléments dans laquelle n+1 se trouve.

Soit n+1 n’y est pas : je dois donc toujours sélectionner k+1 éléments, mais parmi n choix puisque je ne peux pas choisir n+1 : Il y a donc $\binom{n}{k+1}$ façons de fabriquer une partie à k+1 éléments dans laquelle n+1 ne se trouve pas.

On établit donc une classification sur l’ensemble des parties à k+1 éléments parmi les n+1 éléments. Parmi ces parties, il y en a qui contiennent n+1 et d’autres qui ne le contiennent pas.

En dénombrement il y a deux erreurs classiques : oublier certaines parties et compter certaines parties deux fois.

Ici la classification est exhaustive (on a bien compté toutes les partitions possibles) et non redondante (on a séparé en deux classes distinctes, une partie ne peux pas être en même temps dans les 2 cas présentés). On peut donc sommer :

$\binom{n+1}{k+1}=\binom{n}{k+1}+\binom{n}{k}$ avec $0\leq k\leq n-1$

• La formule du quarterback

$k\binom{n}{k}=n\binom{n-1}{k-1}$ avec $1\leq k\leq n$