Un binôme sans factorielles

Exercice · niveau 3 (difficile) · mathématiques approfondies (ECG 1re année), chapitre 1 — Raisonnement et vocabulaire ensembliste · Coefficients binomiaux

Énoncé

Écrire une fonction Python binomial(n, p) qui calcule $(p n)$ sans passer par les factorielles. Comparer, sur $(50 100)$ , la taille des nombres manipulés par les deux approches.

Corrigé


def binomial(n, p):
    if p < 0 or p > n:
        return 0
    p = min(p, n - p)              # symetrie : moins d'iterations
    r = 1
    for i in range(p):
        r = r * (n - i) // (i + 1)  # division EXACTE a chaque tour
    return r

Le principe. On utilise $(p n) = \prod_{i = 0}^{p - 1} \frac{n - i}{i + 1}$ , en effectuant la division à chaque tour. Elle tombe toujours juste : après $i$ tours, r vaut $(i n)$ , qui est entier — c'est ce qui autorise le //.

Les tailles en jeu. Pour $(50 100)$ :

$(50 100) \approx 1, 009 \times 1 0^{29} (30 chiffres), 100! \approx 9, 33 \times 1 0^{157} (158 chiffres) .$

La voie factorielle construit donc un nombre de $158$ chiffres pour en obtenir un de $30$ , avant de tout simplifier. Notre boucle ne dépasse jamais le résultat final.

Ce que cela change. En Python, les entiers sont de taille arbitraire : les deux méthodes donnent le même résultat exact, seule la vitesse souffre. Dans un langage à entiers $64$ bits, la version factorielle déborderait dès $21!$ et rendrait un résultat faux sans le moindre avertissement, là où celle-ci reste juste jusqu'à $(31 62) \approx 4, 5 \times 1 0^{17}$ .

La ligne $p = min (p, n - p)$ exploite $(p n) = (n - p n)$ : pour $(99 100)$ , elle ramène $99$ tours à un seul.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.