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
deffactorielle(n):"""Renvoie la factorielle de n positif"""ifn==0:return1else:returnn*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)!\)
Contrainte
Le module math est désactivé pour cet exercice.
Exemples
>>> factorielle(5)120>>> factorielle(10)3628800
###(Dés-)Active le code après la ligne # Tests (insensible à la casse) (Ctrl+I)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
# Tests(insensible à la casse)(Ctrl+I)