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 :

Besoin	Solution
Calcul direct fiable	math.comb(n, k)
Comprendre la formule	factorielles
Éviter de très grosses factorielles intermédiaires	formule multiplicative
Construire beaucoup de valeurs	triangle de Pascal ou DP

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.

Pour des entiers non négatifs, math.comb renvoie déjà 0 lorsque k > n. Il n’est pas nécessaire d’ajouter une fonction intermédiaire :

import math

print(math.comb(5, 8))  # 0
print(math.comb(0, 0))  # 1

En revanche, un argument négatif provoque une ValueError, et un argument qui n’est pas entier provoque une TypeError. Ce sont les comportements définis par la documentation officielle de math.comb.

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é

Méthode	Temps	Remarque
math.comb	optimisé en C	choix recommandé
factorielle	dépend de la taille des entiers	simple mais intermédiaires énormes
multiplicative	O(k)	bonne version pédagogique
triangle de Pascal	O(n²)	utile pour construire beaucoup de valeurs
DP table complète	O(n_max²)	pratique si requêtes nombreuses

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

Pour des entiers n et k non négatifs, math.comb(n, k) renvoie 0 si k > n. Distinguez ce cas d’un argument négatif, qui provoque une ValueError.

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

Un parcours pour continuer à apprendre Python

Pour choisir la suite selon votre niveau, consultez notre parcours de ressources Python : exercices gratuits et livres. Vous y trouverez des exercices à faire sur le blog et des critères pour choisir un livre adapté à votre objectif.

Pour vous exercer à traduire des problèmes en programmes, examinez 15 énigmes ludiques pour s’initier à la programmation Python de Pascal Lafourcade et Malika More. Notre page de ressources détaille le niveau visé et renvoie au sommaire de l’éditeur.

Lien affilié : en tant que Partenaire Amazon, je réalise un bénéfice sur les achats remplissant les conditions requises.

Rechercher cette édition sur Amazon