Les coefficients binomiaux : Cours, propriétés et exercices corrigés

Les coefficients binomiaux sont au cœur du dénombrement et de l’algèbre. On les retrouve dans le binôme de Newton, dans les probabilités (la loi binomiale), et dans de nombreux problèmes de combinaisons. Dans cet article, on fait le tour complet : définition, triangle de Pascal, propriétés essentielles, exercices corrigés et exercices d’entraînement.

Prérequis

• Les factorielles

Définition

Soient k et n deux entiers naturels tels que 0 \leq k \leq n. On définit le coefficient binomial « k parmi n », noté \binom{n}{k}, par :

 \binom{n}{k} = \frac{n!}{k!\,(n-k)!}

Ce nombre a une interprétation combinatoire directe : \binom{n}{k} est le nombre de façons de choisir k éléments parmi n, sans tenir compte de l’ordre. C’est exactement le nombre de combinaisons de k éléments parmi n.

Par exemple, \binom{5}{2} = \frac{5!}{2! \times 3!} = \frac{120}{2 \times 6} = 10 : il y a 10 façons de choisir 2 objets parmi 5.

Par convention, on pose \binom{n}{k} = 0 si k > n ou k < 0.

Propriétés des coefficients binomiaux

Quelques valeurs à retenir

Pour k = 0, c’est immédiat :

\binom{n}{0} = \frac{n!}{0!\,n!} = 1

Il n’y a qu’une seule façon de ne choisir aucun élément : prendre l’ensemble vide.

Pour k = 1 :

\binom{n}{1} = \frac{n!}{1!\,(n-1)!} = n

Choisir 1 élément parmi n revient à choisir lequel, d’où n possibilités.

Pour k = 2 :

\binom{n}{2} = \frac{n!}{2!\,(n-2)!} = \frac{n(n-1)}{2}

Enfin, \binom{n}{n} = 1 : il n’y a qu’une seule façon de choisir tous les éléments.

Symétrie des coefficients binomiaux

Pour tous entiers 0 \leq k \leq n, on a :

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

La démonstration est immédiate :

\binom{n}{n-k} = \frac{n!}{(n-k)!\,k!} = \binom{n}{k}

L’interprétation combinatoire est élégante : choisir k éléments à garder revient à choisir n - k éléments à écarter.

Triangle de Pascal et formule de Pascal

La formule de Pascal est la relation fondamentale des coefficients binomiaux. Pour tous entiers 1 \leq k \leq n - 1 :

\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}

Cette formule permet de construire le triangle de Pascal, où chaque coefficient est la somme des deux coefficients situés juste au-dessus de lui :

              1
            1   1
          1   2   1
        1   3   3   1
      1   4   6   4   1
    1   5  10  10   5   1

Le terme à la ligne n et à la position k (en partant de 0) est \binom{n}{k}. Par exemple, à la ligne 4, on lit \binom{4}{0} = 1, \binom{4}{1} = 4, \binom{4}{2} = 6, \binom{4}{3} = 4, \binom{4}{4} = 1.

Démonstration de la formule de Pascal : On part du membre de droite :

 \binom{n-1}{k-1} + \binom{n-1}{k} = \frac{(n-1)!}{(k-1)!\,(n-k)!} + \frac{(n-1)!}{k!\,(n-1-k)!}

On met au même dénominateur k!\,(n-k)! :

 = \frac{k \cdot (n-1)!}{k!\,(n-k)!} + \frac{(n-k) \cdot (n-1)!}{k!\,(n-k)!} = \frac{(n-1)!\,(k + n - k)}{k!\,(n-k)!} = \frac{n!}{k!\,(n-k)!} = \binom{n}{k}

Somme des coefficients binomiaux

La somme de tous les coefficients binomiaux d’une même ligne du triangle de Pascal vaut une puissance de 2 :

 \sum_{k=0}^{n} \binom{n}{k} = 2^n

Démonstration par récurrence :

Initialisation : pour n = 0, \displaystyle\sum_{k=0}^{0} \binom{0}{k} = \binom{0}{0} = 1 = 2^0.

Hérédité : supposons que \displaystyle\sum_{k=0}^{n} \binom{n}{k} = 2^n pour un certain n \geq 0. On calcule la somme au rang n+1 en appliquant la formule de Pascal aux termes intérieurs :

 \sum_{k=0}^{n+1} \binom{n+1}{k} = \binom{n+1}{0} + \sum_{k=1}^{n} \left[\binom{n}{k-1} + \binom{n}{k}\right] + \binom{n+1}{n+1}

On sépare les deux sommes et on réindexe la première (j = k - 1) :

= 1 + \sum_{j=0}^{n-1} \binom{n}{j} + \sum_{k=1}^{n} \binom{n}{k} + 1

Chacune de ces deux sommes est presque la somme complète de la ligne n, à un terme près :

= 1 + \left[2^n - \binom{n}{n}\right] + \left[2^n - \binom{n}{0}\right] + 1 = 1 + 2^n - 1 + 2^n - 1 + 1 = 2^{n+1}

Conclusion : par récurrence, \displaystyle\sum_{k=0}^{n} \binom{n}{k} = 2^n pour tout n \geq 0.

L’interprétation combinatoire est aussi directe : un ensemble à n éléments possède exactement 2^n sous-ensembles (y compris l’ensemble vide et l’ensemble lui-même).

Identité de Vandermonde

Soient m, n et r des entiers naturels avec r \leq m + n. L’identité de Vandermonde affirme que :

\binom{m+n}{r} = \sum_{k=0}^{r} \binom{m}{k}\binom{n}{r-k}

L’interprétation combinatoire est très naturelle : on dispose de deux groupes de m et n personnes, et on veut choisir r personnes en tout. On peut prendre k personnes dans le premier groupe et r - k dans le second, pour chaque valeur de k admissible.

Formule d’absorption

Pour tous entiers 1 \leq k \leq n :

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

Démonstration :

k\binom{n}{k} = k \cdot \frac{n!}{k!\,(n-k)!} = \frac{n!}{(k-1)!\,(n-k)!} = n \cdot \frac{(n-1)!}{(k-1)!\,(n-k)!} = n\binom{n-1}{k-1}

Cette formule est très utile pour simplifier des sommes faisant intervenir k \cdot \binom{n}{k}.

Exercices corrigés

Exercice 1 : Calculer des coefficients binomiaux

Calculer sans calculatrice : \binom{13}{11}, \binom{9}{3} et \binom{8}{4}.

Corrigé : Pour \binom{13}{11}, on utilise la symétrie : \binom{13}{11} = \binom{13}{2} = \frac{13 \times 12}{2} = 78.

Pour \binom{9}{3} = \frac{9!}{3!\,6!} = \frac{9 \times 8 \times 7}{3 \times 2 \times 1} = \frac{504}{6} = 84.

Pour \binom{8}{4} = \frac{8!}{4!\,4!} = \frac{8 \times 7 \times 6 \times 5}{4 \times 3 \times 2 \times 1} = \frac{1680}{24} = 70.

Exercice 2 : Démontrer une identité avec la formule de Pascal

Simplifier la somme S = \displaystyle\sum_{k=p}^{n} \binom{k}{p} pour 0 \leq p \leq n.

Corrigé :

On procède par récurrence (ou par télescopage) en utilisant la formule de Pascal. On va montrer que :

\sum_{k=p}^{n} \binom{k}{p} = \binom{n+1}{p+1}

On note S_n = \displaystyle\sum_{k=p}^{n} \binom{k}{p} et on montre le résultat par récurrence sur n \geq p.

Initialisation : pour n = p, S_p = \binom{p}{p} = 1, et \binom{p+1}{p+1} = 1. C’est correct.

Hérédité : supposons que S_n = \binom{n+1}{p+1} pour un certain n \geq p. Alors :

 S_{n+1} = S_n + \binom{n+1}{p} = \binom{n+1}{p+1} + \binom{n+1}{p} = \binom{n+2}{p+1}

La dernière égalité est exactement la formule de Pascal appliquée au coefficient \binom{n+2}{p+1}.

Conclusion : par récurrence, \displaystyle\sum_{k=p}^{n} \binom{k}{p} = \binom{n+1}{p+1} pour tout n \geq p.

Cette identité s’appelle la formule de la « crosse de hockey » (hockey stick identity) car, dans le triangle de Pascal, on additionne des coefficients le long d’une diagonale et le résultat se lit juste en dessous.

Exercice 3 : Somme alternée de coefficients binomiaux

S_{n\ }=\ \sum_{k=0}^n\left(-1\right)^k\ \binom{2n+1}{k}

Montrer que pour tout n \geq 1 :

 \sum_{k=0}^{n} (-1)^k \binom{n}{k} = 0

Corrigé :

On procède par récurrence en utilisant la formule de Pascal.

Initialisation : pour n = 1, \binom{1}{0} - \binom{1}{1} = 1 - 1 = 0.

Hérédité : supposons que \displaystyle\sum_{k=0}^{n} (-1)^k \binom{n}{k} = 0 pour un certain n \geq 1. On calcule au rang n+1 :

\sum_{k=0}^{n+1} (-1)^k \binom{n+1}{k} = \binom{n+1}{0} + \sum_{k=1}^{n} (-1)^k \left[\binom{n}{k-1} + \binom{n}{k}\right] + (-1)^{n+1}\binom{n+1}{n+1}

On sépare les deux sommes et on réindexe la première (j = k - 1) :

 = 1 - \sum_{j=0}^{n-1} (-1)^j \binom{n}{j} + \sum_{k=1}^{n} (-1)^k \binom{n}{k} + (-1)^{n+1}

La première somme vaut \displaystyle\sum_{j=0}^{n} (-1)^j \binom{n}{j} - (-1)^n \binom{n}{n} = 0 - (-1)^n = -(-1)^n par hypothèse de récurrence. La deuxième vaut \displaystyle\sum_{k=0}^{n} (-1)^k \binom{n}{k} - \binom{n}{0} = 0 - 1 = -1. Donc :

= 1 + (-1)^n - 1 + (-1)^{n+1} = (-1)^n + (-1)^{n+1} = 0

Conclusion : par récurrence, \displaystyle\sum_{k=0}^{n} (-1)^k \binom{n}{k} = 0 pour tout n \geq 1.

Interprétation : dans un ensemble à n \geq 1 éléments, il y a autant de sous-ensembles de cardinal pair que de sous-ensembles de cardinal impair.

1. Soient n et k des entiers tels que 1 \leq k \leq n. Montrer les égalités suivantes :
   • \binom{n}{k} = (n-k+1)\,\dfrac{1}{k}\,\binom{n}{k-1}
   • \binom{n-1}{k-1}\binom{n}{k+1}\binom{n+1}{k} = \binom{n-1}{k}\binom{n}{k-1}\binom{n+1}{r+1}
2. Résoudre l’équation \binom{n}{1} + \binom{n}{2} + \binom{n}{3} = 5n d’inconnue n \geq 3.
3. On note S_n = \displaystyle\sum_{k=0}^{n} (-1)^k \binom{2n+1}{k}. En utilisant la formule de Pascal, montrer que S_n = (-1)^n \binom{2n}{n}.

FAQ