Coefficients binomiaux en Python : math.comb, triangle de Pascal et DP

Un coefficient binomial compte le nombre de façons de choisir k éléments parmi n, sans tenir compte de l’ordre. On le note souvent C(n, k) ou “n choose k”.

En Python, la façon la plus simple et la plus fiable de le calculer est :

import math

print(math.comb(5, 2))  # 10

Il y a donc 10 façons de choisir 2 éléments parmi 5.

Même si math.comb suffit dans la plupart des cas, comprendre la formule, le triangle de Pascal et la programmation dynamique reste très utile en algorithmique, probabilités et combinatoire.

La réponse courte

Pour calculer un coefficient binomial en Python 3.8 ou plus :

import math

resultat = math.comb(n, k)

Exemple :

import math

print(math.comb(10, 3))  # 120

À retenir :

Comprendre C(n, k)

C(n, k) répond à la question :

Combien de groupes de k éléments peut-on former avec n éléments ?

Exemple avec 5 éléments :

A, B, C, D, E

Choisir 2 éléments donne :

AB, AC, AD, AE, BC, BD, BE, CD, CE, DE

Il y a 10 combinaisons.

L’ordre ne compte pas :

AB et BA représentent le même choix

Formule avec les factorielles

La formule classique est :

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

En Python :

import math


def coefficient_binomial_factoriel(n, k):
    if k < 0 or k > n:
        return 0

    return math.factorial(n) // (
        math.factorial(k) * math.factorial(n - k)
    )

Test :

print(coefficient_binomial_factoriel(5, 2))   # 10
print(coefficient_binomial_factoriel(10, 3))  # 120

Cette version est claire, mais elle calcule de très grandes factorielles intermédiaires. Pour un usage réel, math.comb est préférable.

Utiliser math.comb

math.comb est la solution standard en Python.

import math

print(math.comb(100, 50))

Avantages :

• lisible ;
• rapide ;
• exact sur les entiers ;
• gère les grands nombres ;
• évite d’écrire soi-même des détails fragiles.

Si k > n, Python lève une erreur :

math.comb(5, 8)  # ValueError

Si vous voulez une fonction qui renvoie 0 dans ce cas, enveloppez-la :

import math


def comb(n, k):
    if k < 0 or k > n:
        return 0
    return math.comb(n, k)

Formule multiplicative

La symétrie est importante :

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

Choisir 3 éléments parmi 10, c’est comme choisir les 7 éléments que l’on laisse de côté.

On peut donc réduire k :

def coefficient_binomial(n, k):
    if k < 0 or k > n:
        return 0

    k = min(k, n - k)
    resultat = 1

    for i in range(1, k + 1):
        resultat = resultat * (n - k + i) // i

    return resultat

Test :

print(coefficient_binomial(5, 2))    # 10
print(coefficient_binomial(10, 3))   # 120
print(coefficient_binomial(100, 50))

Cette version évite de calculer n!, k! et (n-k)! séparément.

Triangle de Pascal

Les coefficients binomiaux apparaissent dans le triangle de Pascal.

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 la somme des deux valeurs au-dessus :

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

En Python :

def ligne_pascal(n):
    ligne = [1]

    for _ in range(n):
        ligne = [1] + [
            ligne[i] + ligne[i + 1]
            for i in range(len(ligne) - 1)
        ] + [1]

    return ligne

Test :

print(ligne_pascal(5))  # [1, 5, 10, 10, 5, 1]

La valeur C(n, k) se lit alors :

print(ligne_pascal(5)[2])  # 10

Programmation dynamique

Si vous devez calculer beaucoup de coefficients binomiaux, vous pouvez construire une table dynamique.

def table_binomiale(n_max):
    table = [[0] * (n_max + 1) for _ in range(n_max + 1)]

    for n in range(n_max + 1):
        table[n][0] = 1
        table[n][n] = 1

        for k in range(1, n):
            table[n][k] = table[n - 1][k - 1] + table[n - 1][k]

    return table

Utilisation :

table = table_binomiale(10)

print(table[5][2])   # 10
print(table[10][3])  # 120

Cette approche coûte O(n_max²) en temps et en mémoire, mais elle est pratique si vous interrogez ensuite beaucoup de valeurs.

Applications

Les coefficients binomiaux apparaissent dans :

• les combinaisons ;
• les probabilités ;
• la loi binomiale ;
• le triangle de Pascal ;
• la programmation dynamique ;
• les chemins dans une grille ;
• le développement de (a + b)^n.

Exemple : nombre de chemins dans une grille.

Si vous devez aller de l’angle supérieur gauche à l’angle inférieur droit d’une grille, en ne bougeant que vers la droite ou vers le bas, le nombre de chemins est un coefficient binomial.

Pour une grille de m déplacements à droite et n déplacements vers le bas :

import math


def chemins_grille(droite, bas):
    return math.comb(droite + bas, droite)


print(chemins_grille(3, 2))  # 10

Complexité

Pour mieux lire ces notations, voir la complexité algorithmique en Python.

Erreurs fréquentes

Confondre combinaison et permutation

Dans une combinaison, l’ordre ne compte pas. Dans une permutation, l’ordre compte.

AB et BA : même combinaison, deux permutations

Ne pas gérer k > n

Mathématiquement, C(n, k) vaut 0 si k > n. Mais math.comb lève une erreur. À vous de choisir le comportement de votre fonction.

Calculer des factorielles énormes inutilement

La formule factorielle est claire, mais pas toujours la plus efficace. Utilisez math.comb ou la formule multiplicative.

Oublier la symétrie

Utiliser :

k = min(k, n - k)

réduit le nombre d’itérations.

Exercices rapides

Exercice 1

Calculez C(20, 5) avec math.comb.

Correction :

import math

print(math.comb(20, 5))  # 15504

Exercice 2

Vérifiez la symétrie :

import math

print(math.comb(20, 5) == math.comb(20, 15))

Exercice 3

Générez la ligne 8 du triangle de Pascal.

Correction :

print(ligne_pascal(8))

Pour aller plus loin

Les coefficients binomiaux sont un bon pont entre mathématiques et programmation : on part d’une formule simple, puis on découvre des enjeux d’efficacité, de grands entiers, de programmation dynamique et de modélisation combinatoire.

À lire ensuite :

• Complexité algorithmique en Python : comprendre O(n), O(log n) et O(n²)
• Méthode de Monte Carlo en Python
• Modulo en Python : comprendre %, // et divmod avec exemples

La règle à retenir : pour calculer un coefficient binomial en Python moderne, utilisez math.comb. Pour apprendre, implémentez aussi la formule multiplicative et le triangle de Pascal.

Références

• Documentation Python officielle : math.comb
• Documentation Python officielle : itertools.combinations
• Wikipedia : Binomial coefficient