Calculateur factoriel

Comprendre les factoriels

Le factoriel d'un entier n non négatif, écrit n!, est le produit de tous les entiers positifs de 1 à n. La définition:n! = n x (n-1) x (n-2) x ... x 2 x 1. cas particulier:0 est égal à 1par définition (pas par calcul) -- ceci est nécessaire pour que les formules combinatoires fonctionnent de manière cohérente.

5! = 120; 10! = 3.628.800; 15! = 1.307.674.368.000; 20! ~ 2.43 x 10^18; 100! ~ 9.33 x 10^157. Le nombre 170! est approximativement 7.26 x 10^306, ce qui est le plus grand factoriel représenté comme un nombre à virgule flottante à 64 bits (double précision). Notre calculatrice utilise l'arithmétique BigInt pour des résultats entiers exacts jusqu'à 170 !

La définition récursive du factoriel est: n! = n x (n-1)! pour n > 0, avec 0! = 1 comme cas de base. Cette structure récursive fait du factoriel un exemple d'introduction classique en informatique pour l'enseignement de la récursion, de la programmation dynamique et de la mémorisation. Le calcul factoriel par itération est également standard: initialiser le résultat = 1, puis multiplier par chaque entier de 2 à n.

La notation "n!" a été introduite par Christian Kramp en 1808 comme un raccourci pratique pour le produit 1 x 2 x 3 x ... x n. Avant cela, diverses autres notations étaient utilisées.

Les factoriels en combinatoire et en probabilité

Le factoriel est la pierre angulaire de la combinatoire, la branche des mathématiques qui traite du comptage, de l'arrangement et de la sélection.

Permutations (arrangements ordonnés):Le nombre de façons d'arranger n objets distincts dans une rangée est n! -- appelées permutations n-factorielles. Avec 4 livres sur une étagère: 4! = 24 arrangements. Avec 10 coureurs dans une course, le nombre de possibilités de classement pour la 1ère, 2ème et 3ème place est P10,(3) = 10!/(10-3)! = 10!/7! = 720.

La formule de permutation partielle: P ((n,r) = n!/ ((n-r)! compte les sélections ordonnées d'éléments r à partir de n. La formule de permutations totales n! est le cas particulier r = n.

Combinaisons (sélections non ordonnées):C ((n,r) = n!/(r!(n-r)!), également écrit nCr ou "n choisir r" ou comme coefficient binomiale. Cela compte le nombre de façons de sélectionner r éléments de n où l'ordre n'a pas d'importance. De 52 cartes, le nombre de mains à 5 cartes = C ((52,5) = 52!/(5!x47!) = 2,598,960. La probabilité d'être distribué une couleur royale = 4/2,598,960 ~ 0,000154%.

Coefficients à plusieurs termes:n!/(n1! x n2! x ... x nk!) compte les arrangements de n éléments où n1 sont de type 1, n2 de type 2, etc. En arrangeant les lettres dans MISSISSIPPI: 11!/(1!x4!x4!x2!) = 34 650 arrangements distincts.

Le tableau factoriel: n! pour n = 0 à 20

Voici la table factorielle complète pour les petites valeurs de n. La mémorisation des 10 premiers factoriels est utile pour des calculs combinatoire mentaux rapides.

La croissance explosive est frappante: de 10! = 3,6 millions à 20! = 2,4 quintillions en seulement 10 étapes.Cette croissance rapide est la raison pour laquelle le factoriel apparaît dans les dénominateurs des séries de Taylor (assurant la convergence) et dans les facteurs de normalisation des distributions de probabilité.

L'approximation de Stirling et les grands facteurs

Pour un grand n, calculer des factoriels exacts est peu pratique -- 100! a 158 chiffres.Approximation de Stirlingfournit une excellente estimation: n! ~ √(2πn) x (n/e) ^ n, où e ~ 2.71828 est le nombre d'Euler.

Précision de l'approximation de Stirling: pour n=10, exact = 3.628.800; Stirling donne ~ 3.598.696, une erreur inférieure à 1%. Pour n=100, l'erreur relative est inférieure à 0,1%. Plus n est grand, plus l'approximation devient précise - l'erreur relative de l'approximation est O(1/n).

En statistique et en apprentissage automatique, les log-probabilités sont utilisées au lieu des probabilités brutes pour éviter le sous-flux numérique (la multiplication de nombreux petits nombres ensemble entraîne rapidement un sous-flux à 0 en arithmétique à virgule flottante).

LeFonction gammaΓ(n) est l'extension continue du factoriel à tous les nombres complexes à l'exception des entiers non positifs: Γ(n) = (n-1)! pour les entiers positifs. Cela apparaît dans les distributions de probabilité (distribution gamma, distribution Chi-carré, distribution bêta) et dans de nombreuses formules de physique.

Les factoriels dans les distributions de probabilité

La plupart des distributions de probabilité les plus importantes en statistique utilisent des factoriels dans leurs formules, reliant la combinatoire pure à l'analyse des données du monde réel.

Distribution binaire:P ((X = k) = C ((n,k) x p^k x (1-p) ^ ((n-k). Modélise le nombre de succès dans n essais indépendants avec une probabilité p chacun. C ((n,k) = n!/(k!(n-k)!) est le coefficient combinatoire. La somme sur tous les k de ces termes est égale à 1 (probabilité totale).

Distribution de Poisson:P ((X = k) = (λ^k x e^(-λ)) / k!. Modélise le nombre d'événements rares survenant dans un intervalle fixe lorsque le taux moyen est λ. Le k! dans le dénominateur normalise la distribution. Utilisé pour: arrivées à l'hôpital par heure, réclamations d'assurance par jour, mutations par réplication du génome.

Répartition normaleLe théorème de la limite centrale - que les sommes de variables aléatoires indépendantes approchent une distribution normale - peut être prouvé en utilisant l'approximation de Stirling de n ! Cette connexion entre les mondes discrets (factoriels) et continus (distribution normale) est l'un des résultats les plus profonds de la théorie des probabilités.

Problème d' anniversaire:La probabilité que toutes les 23 personnes dans une pièce aient des anniversaires différents est égale à 365!/(365-23)! ÷ 365^23 ~ 49.3%. Il y a donc plus de 50% de chances qu'au moins deux personnes aient le même anniversaire - un résultat contre-intuitif célèbre qui utilise des permutations partielles.

Le factoriel en théorie des nombres: les zéros et le théorème de Wilson

La factorielle interagit abondamment avec la théorie des nombres premiers, donnant des résultats élégants sur la divisibilité et la détection des nombres premiers.

Les zéros suivants en n:Le nombre de zéros en arrière dans n! est égal au nombre de facteurs de 10, qui est égal au nombre de facteurs de 5 (puisque les facteurs de 2 sont toujours plus abondants). La formule: count = n/5 + n/25 + n/125 + ... (summe alors que la puissance de 5 <= n). Pour 100!: 100/5 + 100/25 = 20 + 4 = 24 zéros en arrière.

La formule de Legendre:La puissance la plus élevée de p premier divisant n! est n/p + n/p2 + n/p3 + ... Cela vous indique la factorisation primaire exacte de n!, ce qui est essentiel en théorie des nombres et en combinatoire.

Le théorème de Wilson:Un entier p > 1 est premier si et seulement si (p-1)! -1 (mod p). Pour p=5: 4! = 24 4 -1 (mod 5). Pour p=6 (composite): 5! = 120 0 (mod 6). Bien que le théorème de Wilson soit théoriquement beau, il est impraticable pour les grands nombres puisque le calcul (p-1)! est exponentiellement coûteux.

Les nombres premiers factoriels:Un premier factoriel est un premier de la forme n! + 1 ou n! - 1. Exemples: 2! - 1 = 1 (pas premier), 3! - 1 = 5 (premier), 3! + 1 = 7 (premier), 4! - 1 = 23 (premier).

Comment utiliser cette calculatrice factorielle

Entrez un entier non négatif n (de 0 à 170) et cliquez sur Calculer. La calculatrice renvoie la valeur factorielle exacte comme un entier entier en utilisant le BigInt de JavaScript pour les grandes valeurs, évitant l'imprécision de virgule flottante qui corromprait les résultats pour n >= 19.

Les notes:

• L'entrée doit être un entier non négatif. La calculatrice tronque l'entrée décimale au nombre entier le plus proche.
• Maximum n = 170 pour le calcul exact (170! ~ 7,26 x 10^306, juste dans la plage de double précision pour l'affichage).
• Pour n = 0, le résultat est 1 (par définition).
• Pour les très grands factoriels (n > 100), le résultat est un nombre de plus de 150 chiffres - affiché en entier par notre implémentation BigInt.
• Pour les applications nécessitant ln(n!), utilisez l'identité: ln(n!) = Σ ln(k) pour k = 1 à n.

Les factoriels en informatique: algorithmes et complexité

La factorielle est intimement liée à la théorie de la complexité computationnelle - l'étude de la difficulté des problèmes à résoudre algorithmiquement. Comprendre la factorielle aide à expliquer pourquoi certains problèmes sont "difficiles" dans un sens mathématique précis.

LeProblème du marchand itinérantdemande: étant donné n villes et les distances entre chaque paire, trouver la route la plus courte visitant toutes les villes exactement une fois. Une approche de force brute naïve vérifie tous les ordres possibles: (n-1)!/2 routes (divisant par 2 pour la symétrie, fixant la ville de départ). Pour n=20 villes: 19!/2 ~ 6 x 10^16 routes. Même à 1 billion de routes/seconde, cela prendrait plus de 60 000 ans. Cette explosion factorielle est la raison pour laquelle TSP est "NP-hard" et pourquoi les algorithmes heuristiques (au lieu de solutions exactes) sont utilisés en pratique pour les grandes instances.

Leproblème de tria également des connexions factorielles: n! est le nombre d'ordonnances possibles de n éléments. Un algorithme de tri basé sur la comparaison optimale doit distinguer entre tous les n! cas, nécessitant au moins log2 ((n!) comparaisons. Par l'approximation de Stirling, log2 ((n!) ~ nxlog2 ((n), c'est pourquoi les comparaisons minimales théoriques pour le tri sont O ((n log n) - réalisées par le tri par fusion et le tri par tas.

In programmation dynamique, les sous-problèmes factoriels peuvent être mémorisés: une fois que vous calculez k!, vous pouvez obtenir (k+1)! = (k+1) x k! sans recomputer à partir de zéro. Cela réduit le coût de calcul de tous les factoriels de 1 à n de O ((n2) à O ((n), une optimisation clé dans les applications nécessitant de nombreuses valeurs factorielles telles que la génération de tables de probabilité.