Factorial

Applications[edit]

The earliest uses of the factorial function involve counting permutations: there are ${\displaystyle n!}$ different ways of arranging ${\displaystyle n}$ distinct objects into a sequence.^[26] Factorials appear more broadly in many formulas in combinatorics, to account for different orderings of objects. For instance the binomial coefficients ${\displaystyle {\tbinom {n}{k}}}$ count the ${\displaystyle k}$-element combinations (subsets of ${\displaystyle k}$ elements) from a set with ${\displaystyle n}$ elements, and can be computed from factorials using the formula^[27] $${\displaystyle {\binom {n}{k}}={\frac {n!}{k!(n-k)!}}.}$$ The Stirling numbers of the first kind sum to the factorials, and count the permutations of ${\displaystyle n}$ grouped into subsets with the same numbers of cycles.^[28] Another combinatorial application is in counting derangements, permutations that do not leave any element in its original position; the number of derangements of ${\displaystyle n}$ items is the nearest integer to ${\displaystyle n!/e}$.^[29]


In algebra, the factorials arise through the binomial theorem, which uses binomial coefficients to expand powers of sums.^[30] They also occur in the coefficients used to relate certain families of polynomials to each other, for instance in Newton's identities for symmetric polynomials.^[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.^[19] In mathematical analysis, factorials frequently appear in the denominators of power series, most notably in the series for the exponential function,^[14] $${\displaystyle e^{x}=1+{\frac {x}{1}}+{\frac {x^{2}}{2}}+{\frac {x^{3}}{6}}+\cdots =\sum _{i=0}^{\infty }{\frac {x^{i}}{i!}},}$$ and in the coefficients of other Taylor series (in particular those of the trigonometric and hyperbolic functions), where they cancel factors of ${\displaystyle n!}$ coming from the ${\displaystyle n}$th derivative of ${\displaystyle x^{n}}$.^[33] This usage of factorials in power series connects back to analytic combinatorics through the exponential generating function, which for a combinatorial class with ${\displaystyle n_{i}}$ elements of size ${\displaystyle i}$ is defined as the power series^[34] $${\displaystyle \sum _{i=0}^{\infty }{\frac {x^{i}n_{i}}{i!}}.}$$


In number theory, the most salient property of factorials is the divisibility of ${\displaystyle n!}$ by all positive integers up to ${\displaystyle n}$, described more precisely for prime factors by Legendre's formula. It follows that arbitrarily large prime numbers can be found as the prime factors of the numbers ${\displaystyle n!\pm 1}$, leading to a proof of Euclid's theorem that the number of primes is infinite.^[35] When ${\displaystyle n!\pm 1}$ is itself prime it is called a factorial prime;^[36] relatedly, Brocard's problem, also posed by Srinivasa Ramanujan, concerns the existence of square numbers of the form ${\displaystyle n!+1}$.^[37] In contrast, the numbers ${\displaystyle n!+2,n!+3,\dots n!+n}$ must all be composite, proving the existence of arbitrarily large prime gaps.^[38] An elementary proof of Bertrand's postulate on the existence of a prime in any interval of the form ${\displaystyle [n,2n]}$, one of the first results of Paul Erdős, was based on the divisibility properties of factorials.^[39][40] The factorial number system is a mixed radix notation for numbers in which the place values of each digit are factorials.^[41]


Factorials are used extensively in probability theory, for instance in the Poisson distribution^[42] and in the probabilities of random permutations.^[43] In computer science, beyond appearing in the analysis of brute-force searches over permutations,^[44] factorials arise in the lower bound of ${\displaystyle \log _{2}n!=n\log _{2}n-O(n)}$ on the number of comparisons needed to comparison sort a set of ${\displaystyle n}$ items,^[45] and in the analysis of chained hash tables, where the distribution of keys per cell can be accurately approximated by a Poisson distribution.^[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. Quantum physics provides the underlying reason for why these corrections are necessary.^[47]