Factorial

[1] Factorials have been discovered in several ancient cultures, notably in Indian mathematics in the canonical works of Jain literature, and by Jewish mystics in the Talmudic book Sefer Yetzirah.

The factorial operation is encountered in many areas of mathematics, notably in combinatorics, where its most basic use counts the possible distinct sequences – the permutations – of

Much of the mathematics of the factorial function was developed beginning in the late 18th and early 19th centuries.

Although directly computing large factorials using the product formula or recurrence is not efficient, faster algorithms are known, matching to within a constant factor the time for fast multiplication algorithms for numbers with the same number of digits.

In a 1494 treatise, Italian mathematician Luca Pacioli calculated factorials up to 11!, in connection with a problem of dining table arrangements.

[12] Christopher Clavius discussed factorials in a 1603 commentary on the work of Johannes de Sacrobosco, and in the 1640s, French polymath Marin Mersenne published large (but not entirely correct) tables of factorials, up to 64!, based on the work of Clavius.

[13] The power series for the exponential function, with the reciprocals of factorials for its coefficients, was first formulated in 1676 by Isaac Newton in a letter to Gottfried Wilhelm Leibniz.

by Abraham de Moivre in 1721, a 1729 letter from James Stirling to de Moivre stating what became known as Stirling's approximation, and work at the same time by Daniel Bernoulli and Leonhard Euler formulating the continuous extension of the factorial function to the gamma function.

, in which the argument of the factorial was half-enclosed by the left and bottom sides of a box, was popular for some time in Britain and America but fell out of use, perhaps because it is difficult to typeset.

[17] The word "factorial" (originally French: factorielle) was first used in 1800 by Louis François Antoine Arbogast,[18] in the first work on Faà di Bruno's formula,[19] but referring to a more general concept of products of arithmetic progressions.

There are several motivations for this definition: The earliest uses of the factorial function involve counting permutations: there are

[26] Factorials appear more broadly in many formulas in combinatorics, to account for different orderings of objects.

[31] Their use in counting permutations can also be restated algebraically: the factorials are the orders of finite symmetric groups.

[32] In calculus, factorials occur in Faà di Bruno's formula for chaining higher derivatives.

[33] This usage of factorials in power series connects back to analytic combinatorics through the exponential generating function, which for a combinatorial class with

[43] In computer science, beyond appearing in the analysis of brute-force searches over permutations,[44] factorials arise in the lower bound of

[46] Moreover, factorials naturally appear in formulae from quantum and statistical physics, where one often considers all the possible permutations of a set of particles.

In statistical mechanics, calculations of entropy such as Boltzmann's entropy formula or the Sackur–Tetrode equation must correct the count of microstates by dividing by the factorials of the numbers of each type of indistinguishable particle to avoid the Gibbs paradox.

[49] More carefully bounding the sum both above and below by an integral, using the trapezoid rule, shows that this estimate needs a correction factor proportional to

[51] The binary logarithm of the factorial, used to analyze comparison sorting, can be very accurately estimated using Stirling's approximation.

, and the exponent given by this formula can also be interpreted in advanced mathematics as the p-adic valuation of the factorial.

[61] For almost all numbers (all but a subset of exceptions with asymptotic density zero), it coincides with the largest prime factor of

It can be extended to the non-integer points in the rest of the complex plane by solving for Euler's reflection formula

It has a nonzero value at all complex numbers, except for the non-positive integers where it has simple poles.

[69][70] In the p-adic numbers, it is not possible to continuously interpolate the factorial function directly, because the factorials of large integers (a dense subset of the p-adics) converge to zero according to Legendre's formula, forcing any continuous function that is close to their values to be zero everywhere.

[75] If efficiency is not a concern, computing factorials is trivial: just successively multiply a variable initialized to

[84] The exact computation of larger factorials involves arbitrary-precision arithmetic, because of fast growth and integer overflow.

[87] However, computing the factorial involves repeated products, rather than a single multiplication, so these time bounds do not apply directly.

from its prime factorization, based on the principle that exponentiation by squaring is faster than expanding an exponent into a product.

Again, at each level of recursion the numbers involved have a constant fraction as many bits (because otherwise repeatedly squaring them would produce too large a final result) so again the amounts of time for these steps in the recursive calls add in a geometric series to