Section courante

A propos

Section administrative du site

Coefficient binomial

Le coefficient binomial est une notion fondamentale de la combinatoire permettant de déterminer le nombre de façons de choisir un certain nombre d'éléments parmi un ensemble, sans tenir compte de leur ordre. Il intervient dans de nombreux domaines des mathématiques et de l'informatique, notamment les probabilités, les statistiques, l'analyse des algorithmes, le développement du binôme de Newton, les structures récursives, les chemins dans une grille et la génération de combinaisons.

Contrairement aux permutations et aux arrangements, dans lesquels l'ordre des éléments est important, le coefficient binomial compte uniquement les groupes distincts pouvant être formés. Ainsi, choisir les éléments A, B et C produit la même combinaison que choisir C, A et B. Cette distinction permet de réduire considérablement le nombre de résultats possibles et de résoudre efficacement de nombreux problèmes de dénombrement.

Définition

Le coefficient binomial représente le nombre de façons de choisir k éléments parmi un ensemble contenant n éléments distincts.

Il est généralement noté :

C(n,k)

ou :

(n)
(k)

Cette seconde notation se lit :

En français, on rencontre également les formulations :

Combinaison de n éléments pris k à la fois

ou :

k éléments choisis parmi n

Formule du coefficient binomial

Le coefficient binomial est défini par la formule suivante :

C(n,k) = n! / (k!(n-k)!)

où :

Cette formule est valable lorsque :

0 ≤ k ≤ n

Exemple simple

Supposons que l'on possède quatre lettres :

A, B, C et D

et que l'on souhaite en choisir deux.

Les combinaisons possibles sont :

AB
AC
AD
BC
BD
CD

Il existe donc six combinaisons.

La formule donne :

C(4,2) =
4! / (2! × 2!)

En développant les factorielles :

C(4,2) =
24 / (2 × 2)

Le résultat est :

C(4,2) = 6

Différence entre combinaison et permutation

Une combinaison ne tient pas compte de l'ordre des éléments.

Ainsi :

AB

et :

BA

représentent la même combinaison.

Dans une permutation ou un arrangement, ces deux ordres seraient considérés comme différents.

Opération Ordre important Formule
Permutation complète Oui n!
Arrangement de k éléments Oui n! / (n-k)!
Combinaison de k éléments Non n! / (k!(n-k)!)

Cette différence est essentielle dans tous les problèmes de dénombrement.

Pourquoi diviser par k!

Le nombre d'arrangements de k éléments parmi n est :

n! / (n-k)!

Cependant, chaque groupe de k éléments est compté plusieurs fois, une fois pour chaque ordre possible.

Comme les k éléments peuvent être ordonnés de :

k!

façons différentes, il faut diviser le nombre d'arrangements par k!.

On obtient donc :

C(n,k) =
[n! / (n-k)!] / k!

ce qui donne :

C(n,k) =
n! / (k!(n-k)!)

Valeurs particulières

Certains coefficients binomiaux possèdent des valeurs immédiates.

Choisir aucun élément

C(n,0) = 1

Il existe exactement une manière de ne choisir aucun élément : former l'ensemble vide.

Choisir tous les éléments

C(n,n) = 1

Il existe une seule façon de sélectionner tous les éléments de l'ensemble.

Choisir un seul élément

C(n,1) = n

Il existe autant de choix possibles que d'éléments disponibles.

Choisir tous les éléments sauf un

C(n,n-1) = n

Choisir tous les éléments sauf un revient à déterminer lequel doit être exclu.

Propriété de symétrie

Les coefficients binomiaux possèdent la propriété suivante :

C(n,k) = C(n,n-k)

Cette identité signifie que choisir k éléments revient à choisir les n-k éléments qui ne seront pas retenus.

Par exemple :

C(10,3) = C(10,7)

Dans le premier cas, on choisit trois éléments.

Dans le second, on choisit les sept éléments qui seront conservés, ce qui revient à exclure les trois autres.

Cette propriété est également utile pour optimiser les calculs.

Relation de Pascal

Les coefficients binomiaux satisfont la relation récursive suivante :

C(n,k) =
C(n-1,k-1) + C(n-1,k)

Cette identité peut être expliquée en choisissant un élément particulier.

Pour former un groupe de k éléments parmi n :

S'il est sélectionné, il reste à choisir :

k - 1

éléments parmi :

n - 1

S'il n'est pas sélectionné, il reste à choisir :

k

éléments parmi :

n - 1

Le nombre total de combinaisons est donc la somme de ces deux possibilités.

Triangle de Pascal

Le triangle de Pascal est une disposition triangulaire contenant les coefficients binomiaux.

Les premières lignes sont :

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

Chaque valeur intérieure est obtenue en additionnant les deux valeurs situées directement au-dessus.

Par exemple :

6 = 3 + 3

La ligne correspondant à n = 4 contient :

C(4,0), C(4,1), C(4,2), C(4,3), C(4,4)

soit :

1, 4, 6, 4, 1

Algorithme récursif

La relation de Pascal permet de construire un algorithme récursif.

MODULE CoefficientBinomial(n,k)

   SI k = 0 OU k = n ALORS
      RETOURNER 1
   FIN SI

   RETOURNER
      CoefficientBinomial(n-1,k-1)
      +
      CoefficientBinomial(n-1,k)

Cet algorithme correspond directement à la définition récursive.

Il est toutefois très lent pour les grandes valeurs, car les mêmes calculs sont répétés de nombreuses fois.

Exemple de récursion

Pour calculer :

C(5,2)

l'algorithme effectue :

C(5,2) =
C(4,1) + C(4,2)

Puis :

C(4,2) =
C(3,1) + C(3,2)

et ainsi de suite.

Le nombre d'appels augmente rapidement, ce qui rend cette méthode peu efficace sans mémorisation.

Programmation dynamique

Une méthode plus efficace consiste à construire progressivement le triangle de Pascal.

MODULE CoefficientBinomial(n,k)

   Créer tableau C[0..n][0..k]

   POUR i ← 0 JUSQU'A n
      POUR j ← 0 JUSQU'A minimum(i,k)
         SI j = 0 OU j = i ALORS
            C[i][j] ← 1
         SINON
            C[i][j] ←
               C[i-1][j-1] + C[i-1][j]
         FIN SI
      FIN POUR
   FIN POUR

   RETOURNER C[n][k]

Cette méthode évite de recalculer plusieurs fois les mêmes valeurs.

Optimisation de la mémoire

Il n'est pas nécessaire de conserver tout le triangle de Pascal.

Une seule ligne suffit :

MODULE CoefficientBinomial(n,k)

   SI k > n-k ALORS
      k ← n-k
   FIN SI

   Créer tableau C[0..k]
   C[0] ← 1

   POUR i ← 1 JUSQU'A n
      POUR j ← minimum(i,k) JUSQU'A 1 EN DESCENDANT
         C[j] ← C[j] + C[j-1]
      FIN POUR
   FIN POUR

   RETOURNER C[k]

Le parcours doit être effectué de droite à gauche afin de ne pas écraser les valeurs encore nécessaires.

La mémoire utilisée devient proportionnelle à :

O(k)

Calcul multiplicatif

Le coefficient binomial peut également être calculé sans déterminer séparément les factorielles.

On utilise :

C(n,k) =
n(n-1)(n-2)...(n-k+1)
/
k!

Par exemple :

C(10,3) =
(10 × 9 × 8)
/
(3 × 2 × 1)

Le résultat est :

C(10,3) = 120

Cette méthode réduit les risques de dépassement de capacité par rapport à la formule utilisant directement n!.

Algorithme multiplicatif

MODULE CoefficientBinomial(n,k)

   SI k < 0 OU k > n ALORS
      RETOURNER 0
   FIN SI

   k ← minimum(k,n-k)

   résultat ← 1

   POUR i ← 1 JUSQU'A k

      résultat ← résultat × (n-k+i) / i
   FIN POUR

   RETOURNER résultat

Grâce à la propriété de symétrie, l'algorithme choisit la plus petite valeur entre k et n-k.

Cela réduit le nombre d'itérations nécessaires.

Exemple en Java

L'exemple suivant calcule un coefficient binomial avec la méthode multiplicative :

  1. import java.math.BigInteger;
  2.  
  3. public class CoefficientBinomialSample {
  4.  
  5.     public static BigInteger coefficientBinomial(
  6.         int n,
  7.         int k
  8.     ) {
  9.         if (n < 0 || k < 0 || k > n) {
  10.             return BigInteger.ZERO;
  11.         }
  12.  
  13.         k = Math.min(k, n - k);
  14.  
  15.         BigInteger resultat = BigInteger.ONE;
  16.  
  17.         for (int i = 1; i <= k; i++) {
  18.             resultat = resultat.multiply(
  19.                 BigInteger.valueOf(n - k + i)
  20.             );
  21.  
  22.             resultat = resultat.divide(
  23.                 BigInteger.valueOf(i)
  24.             );
  25.         }
  26.  
  27.         return resultat;
  28.     }
  29.  
  30.     public static void main(String[] args) {
  31.         System.out.println(
  32.             "C(5,2) = "
  33.             + coefficientBinomial(5,2)
  34.         );
  35.  
  36.         System.out.println(
  37.             "C(10,3) = "
  38.             + coefficientBinomial(10,3)
  39.         );
  40.  
  41.         System.out.println(
  42.             "C(100,50) = "
  43.             + coefficientBinomial(100,50)
  44.         );
  45.     }
  46. }

La classe BigInteger permet d'éviter les dépassements de capacité pour les grandes valeurs.

Résultat de l'exemple

Le programme affiche notamment :

C(5,2) = 10

C(10,3) = 120

C(100,50) =
100891344545564193334812497256

La dernière valeur montre que les coefficients binomiaux peuvent devenir extrêmement grands.

Développement du binôme de Newton

Les coefficients binomiaux apparaissent dans le développement de :

(a+b)n

La formule du binôme de Newton est :

(a+b)n = ∑k=0n C(n,k)an-kbk

Par exemple :

(a+b)3

donne :

a3 + 3a2b + 3ab2 + b3

Les coefficients :

1, 3, 3, 1

correspondent à la ligne n = 3 du triangle de Pascal.

Exemple de développement

Pour :

(x+1)4

les coefficients sont :

1, 4, 6, 4, 1

Le développement est donc :

x4 + 4x3 + 6x2 + 4x + 1

Cette relation explique le nom de coefficient binomial : ces valeurs sont les coefficients apparaissant dans la puissance d'un binôme.

Somme d'une ligne du triangle de Pascal

La somme des coefficients d'une ligne vaut :

∑k=0n C(n,k) = 2n

Par exemple, pour la ligne :

1, 4, 6, 4, 1

la somme vaut :

1 + 4 + 6 + 4 + 1 = 16

et :

24 = 16

Cette identité s'explique également par le fait qu'un ensemble de n éléments possède :

2n

sous-ensembles.

Somme alternée

Une autre identité importante est :

∑k=0n (-1)k C(n,k) = 0

pour tout entier :

n > 0

Cette identité correspond au développement de :

(1-1)n

Comme :

(1-1)n = 0

la somme alternée des coefficients binomiaux est également nulle.

Nombre de sous-ensembles

Un ensemble contenant n éléments possède :

2n

sous-ensembles.

En effet, chaque élément peut être :

Il existe donc deux possibilités pour chacun des n éléments.

Le nombre de sous-ensembles contenant exactement k éléments est :

C(n,k)

La somme de tous ces nombres est :

C(n,0) + C(n,1) + ... + C(n,n)

soit :

2n

Chemins dans une grille

Les coefficients binomiaux permettent de compter le nombre de chemins possibles dans une grille lorsque les déplacements sont limités à certaines directions.

Supposons qu'un déplacement nécessite :

Le trajet contient alors :

m+n

déplacements.

Il suffit de choisir les positions des m déplacements vers la droite, ou celles des n déplacements vers le bas.

Le nombre de chemins est :

C(m+n,m)

ou, de façon équivalente :

C(m+n,n)

Exemple de chemin

Pour parcourir une grille nécessitant :

3 déplacements vers la droite

et :

2 déplacements vers le bas

le nombre total de déplacements est :

5

Le nombre de chemins possibles est :

C(5,2)

soit :

10

Probabilités binomiales

Le coefficient binomial intervient dans la loi binomiale.

La probabilité d'obtenir exactement k succès lors de n essais indépendants est :

P(X=k) = C(n,k)pk(1-p)n-k

où :

Cette formule est utilisée dans les probabilités, les statistiques et l'analyse de données.

Nombre de chaînes binaires

Le coefficient binomial permet également de compter les chaînes binaires contenant un nombre précis de bits égaux à 1.

Le nombre de chaînes binaires de longueur n contenant exactement k bits égaux à 1 est :

C(n,k)

Par exemple, les chaînes binaires de longueur 4 contenant exactement deux bits égaux à 1 sont :

0011
0101
0110
1001
1010
1100

Il y en a :

C(4,2) = 6

Complexité des méthodes

Les principales méthodes de calcul peuvent être comparées ainsi :

Méthode Temps Mémoire
Récursion naïve Exponentiel Proportionnelle à la profondeur
Triangle complet O(nk) O(nk)
Programmation dynamique sur une ligne O(nk) O(k)
Méthode multiplicative O(k) O(1), hors taille du résultat

La méthode multiplicative est généralement la plus efficace pour calculer une seule valeur.

La programmation dynamique est préférable lorsqu'une grande partie du triangle de Pascal doit être construite.

Dépassement de capacité

Les coefficients binomiaux croissent très rapidement.

Même pour des valeurs modérées, le résultat peut dépasser les limites des types numériques standards.

Par exemple :

C(67,33)

dépasse la capacité maximale d'un entier signé de 64 bits.

Il est donc recommandé d'utiliser :

Dans certains algorithmes, il n'est pas nécessaire de connaître la valeur complète du coefficient binomial.

On souhaite uniquement calculer :

C(n,k) MOD m

Cette situation apparaît fréquemment dans les problèmes de programmation compétitive et en cryptographie.

Selon la valeur de m, plusieurs méthodes peuvent être utilisées :

Le choix dépend notamment du fait que m soit premier ou composé.

Applications

Les coefficients binomiaux sont utilisés dans de nombreux domaines :

Ils interviennent également dans les fonctions génératrices, les identités combinatoires et plusieurs structures récursives.

Avantages

Le coefficient binomial présente plusieurs avantages :

Limites et précautions

Plusieurs précautions doivent être prises :

Remarque

Le coefficient binomial constitue l'un des principaux outils de la combinatoire et relie plusieurs notions importantes des mathématiques appliquées. Il permet de compter les sélections sans ordre, de construire le triangle de Pascal, de développer les puissances d'un binôme et d'étudier les probabilités associées à des essais répétés. En informatique, il apparaît dans les algorithmes de génération de combinaisons, la programmation dynamique, le comptage de chemins, l'analyse de structures discrètes et les calculs modulaires. Sa compréhension prépare naturellement à l'étude des nombres harmoniques, des suites de Fibonacci, des fonctions génératrices et de l'analyse avancée des algorithmes.



Dernière mise à jour : Jeudi, le 16 juillet 2026