Énumération des permutations⚓︎

On note \(n!\) la factorielle d'un entier naturel \(n\), c'est le produit des nombres entiers strictement positifs qui sont inférieurs ou égaux à \(n\).

\[n! = 1×2×3×4×...×n\]

\(0! = 1\), c'est un produit vide, donc égal à \(1\)
\(1! = 1\), c'est un produit avec \(1\) comme seul facteur.
\(2! = 1×2 = 2\)
\(3! = 1×2×3 = 6\)
\(4! = 1×2×3×4 = 24\)

La factorielle joue un rôle important en algèbre combinatoire. par exemple, il y a \(n!\) façons différentes de permuter \(n\) objets. Elle apparait dans de nombreuses formules en mathématiques, comme la formule du binôme.

Nombre de façons de placer 10 personnes à table

Par exemple, la factorielle 10 exprime le nombre de combinaisons possibles de placement des 10 convives autour d'une table (on dit la permutation des convives). Le premier convive s'installe sur l'une des 10 places à sa disposition. Chacun de ses 10 placements ouvre 9 nouvelles possibilités pour le deuxième convive, celles-ci 8 pour le troisième, et ainsi de suite.

Il y a \(10! = 3\,628\,800\) façons de placer 10 personnes à table.

Formule récursive

Pour \(i>0\) on a \(i! = (i-1)! × i\), comme on peut le constater sur les exemples

\(5! = 1×2×3×4×5 = 4! × 5\)
\(6! = 1×2×3×4×5×6 = 5! × 6\)
\(7! = 1×2×3×4×5×6×7 = 6! × 7\)

Ceci conduit à une fonction récursive classique

🐍 Script Python

def factorielle(n):
    """Renvoie la factorielle de n positif"""
    if n == 0:
        return 1
    else:
        return n * factorielle(n - 1)

On souhaite calculer \(n!\) et mémoriser dans une liste factorielle_mem les nombres factoriels calculés. Cela permet une utilisation intensive de la fonction, ce qui est souvent le cas en combinatoire. On propose ici une fonction non récursive factorielle dont voici le principe :

factorielle_mem est initialisé à [1] de sorte que \(0!\) est égal à factorielle_mem[0]
factorielle(n) fait plusieurs actions :
- Elle remplit, si nécessaire, factorielle_mem avec une boucle.
- Elle renvoie \(n!\) en utilisant factorielle_mem[n] qui sera donc de taille au moins n + 1 à la fin de l'appel.
- On utilisera la variable fact_i pour \(i!\)
- On utilisera la variable fact_im1 pour \((i-1)!\)

Exemples

🐍 Console Python

>>> factorielle(5)
120
>>> factorielle(10)
3628800

###

# testsbksl-nlbksl-nlassert factorielle(5) == 120bksl-nlassert factorielle(10) == 3628800bksl-nlbksl-nl# autres testsbksl-nlbksl-nlbksl-nldef f(n):bksl-nl if n == 0:bksl-nl return 1bksl-nl else:bksl-nl return n py-str f(n - 1)bksl-nlbksl-nlbksl-nlfor n in [0, 1, 2, 3, 4, 17, 42, 11, 42, 31]:bksl-nl attendu = f(n)bksl-nl assert factorielle(n) == attendu, f"Erreur avec {n=}"bksl-nlbksl-nl 5/5

factoriellepy-undmem = [1]bksl-nlbksl-nlbksl-nldef factorielle(n):bksl-nl i = len(factoriellepy-undmem)bksl-nl while n >= i:bksl-nl factpy-undim1 = ...bksl-nl factpy-undi = ...bksl-nl factoriellepy-undmem.append(...)bksl-nl i = ...bksl-nl return ...bksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nlassert factorielle(5) == 120bksl-nlassert factorielle(10) == 3628800bksl-nlbksl-nlfactoriellepy-undmem = [1]bksl-nlbksl-nlbksl-nldef factorielle(n):bksl-nl i = len(factoriellepy-undmem)bksl-nl while n >= i:bksl-nl factpy-undim1 = factoriellepy-undmem[i - 1]bksl-nl factpy-undi = factpy-undim1 py-str ibksl-nl factoriellepy-undmem.append(factpy-undi)bksl-nl i += 1bksl-nl return factoriellepy-undmem[n]bksl-nlbksl-nl

A

Au début du code, i est le premier indice absent de factorielle_mem. Ainsi le prochain nombre à ajouter est \(i!\).

Cette propriété est conservée à la fin de la boucle while ; on parle alors d'invariant de boucle.

En sortie de boucle, on a n < i or i est le premier indice absent, ce qui prouve que l'indice n est présent. On peut alors répondre.

Version raccourcie⚓︎

Parfois une version raccourcie peut être plus explicite.

🐍 Script Python

factorielle_mem = [1]

def factorielle(n):
    i = len(factorielle_mem)
    while n >= i:
        factorielle_mem.append(factorielle_mem[i - 1] * i)
        i += 1
    return factorielle_mem[n]

Z

Le module math est désactivé pour cet exercice.