factorial function

In mathematics, the factorial of a non-negative denoted is the product of all positive integers less than or equal The factorial also equals the product of $n$ with the next smaller factorial:
$\begin n! &= n \times (n-1) \times (n-2) \times (n-3) \times \cdots \times 3 \times 2 \times 1 \\ &= n\times(n-1)!\\ \end$
For example,
$5! = 5\times 4! = 5 \times 4 \times 3 \times 2 \times 1 = 120.$
The value of 0! is 1, according to the convention for an empty product.

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 $n$ distinct objects: there In mathematical analysis, factorials are used in power series for the exponential function and other functions, and they also have applications in algebra, number theory, probability theory, and computer science.

Much of the mathematics of the factorial function was developed beginning in the late 18th and early 19th centuries.
Stirling's approximation provides an accurate approximation to the factorial of large numbers, showing that it grows more quickly than exponential growth. Legendre's formula describes the exponents of the prime numbers in a prime factorization of the factorials, and can be used to count the trailing zeros of the factorials. Daniel Bernoulli and Leonhard Euler interpolated the factorial function to a continuous function of complex numbers, except at the negative integers, the (offset) gamma function.

Many other notable functions and number sequences are closely related to the factorials, including the binomial coefficients, double factorials, falling factorials, primorials, and subfactorials. Implementations of the factorial function are commonly used as an example of different computer programming styles, and are included in scientific calculators and scientific computing software libraries. 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.

History

The concept of factorials has arisen independently in many cultures:
*In Indian mathematics, one of the earliest known descriptions of factorials comes from the Anuyogadvāra-sūtra, one of the canonical works of Jain literature, which has been assigned dates varying from 300 BCE to 400 CE. It separates out the sorted and reversed order of a set of items from the other ("mixed") orders, evaluating the number of mixed orders by subtracting two from the usual product formula for the factorial. The product rule for permutations was also described by 6th-century CE Jain monk Jinabhadra.. Revised by K. S. Shukla from a paper in ''Indian Journal of History of Science'' 27 (3): 231–249, 1992, . See p. 363. Hindu scholars have been using factorial formulas since at least 1150, when Bhāskara II mentioned factorials in his work Līlāvatī, in connection with a problem of how many ways Vishnu could hold his four characteristic objects (a conch shell, discus, mace, and lotus flower) in his four hands, and a similar problem for a ten-handed god.
*In the mathematics of the Middle East, the Hebrew mystic book of creation '' Sefer Yetzirah'', from the Talmudic period (200 to 500 CE), lists factorials up to 7! as part of an investigation into the number of words that can be formed from the Hebrew alphabet. Factorials were also studied for similar reasons by 8th-century Arab grammarian Al-Khalil ibn Ahmad al-Farahidi. Arab mathematician Ibn al-Haytham (also known as Alhazen, c. 965 – c. 1040) was the first to formulate Wilson's theorem connecting the factorials with the prime numbers.
*In Europe, although Greek mathematics included some combinatorics, and Plato famously used 5040 (a factorial) as the population of an ideal community, in part because of its divisibility properties, there is no direct evidence of ancient Greek study of factorials. Instead, the first work on factorials in Europe was by Jewish scholars such as Shabbethai Donnolo, explicating the Sefer Yetzirah passage. In 1677, British author Fabian Stedman described the application of factorials to change ringing, a musical art involving the ringing of several tuned bells.

From the late 15th century onward, factorials became the subject of study by western mathematicians. In a 1494 treatise, Italian mathematician Luca Pacioli calculated factorials up to 11!, in connection with a problem of dining table arrangements. 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. 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. Other important works of early European mathematics on factorials include extensive coverage in a 1685 treatise by John Wallis, a study of their approximate values for large values of $n$ 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. Adrien-Marie Legendre included Legendre's formula, describing the exponents in the factorization of factorials into prime powers, in an 1808 text on number theory.

The notation $n!$ for factorials was introduced by the French mathematician Christian Kramp in 1808. Many other notations have also been used. Another later notation, 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. The word "factorial" (originally French: ''factorielle'') was first used in 1800 by Louis François Antoine Arbogast, in the first work on Faà di Bruno's formula, but referring to a more general concept of products of arithmetic progressions. The "factors" that this name refers to are the terms of the product formula for the factorial.

Definition

The factorial function of a positive integer $n$ is defined by the product of all positive integers not greater than $n$
$n! = 1 \cdot 2 \cdot 3 \cdots (n-2) \cdot (n-1) \cdot n.$
This may be written more concisely in product notation as
$n! = \prod_^n i.$

If this product formula is changed to keep all but the last term, it would define a product of the same form, for a smaller factorial. This leads to a recurrence relation, according to which each value of the factorial function can be obtained by multiplying the previous value
$n! = n\cdot (n-1)!.$
For example,

Factorial of zero

The factorial or in symbols, There are several motivations for this definition:
* For the definition of $n!$ as a product involves the product of no numbers at all, and so is an example of the broader convention that the empty product, a product of no factors, is equal to the multiplicative identity.
* There is exactly one permutation of zero objects: with nothing to permute, the only rearrangement is to do nothing.
* This convention makes many identities in combinatorics valid for all valid choices of their parameters. For instance, the number of ways to choose all $n$ elements from a set of $n$ is $\tbinom = \tfrac = 1,$ a binomial coefficient identity that would only be valid
* With the recurrence relation for the factorial remains valid Therefore, with this convention, a recursive computation of the factorial needs to have only the value for zero as a base case, simplifying the computation and avoiding the need for additional special cases.
* Setting $0!=1$ allows for the compact expression of many formulae, such as the exponential function, as a power series:
* This choice matches the gamma function and the gamma function must have this value to be a continuous function.

Applications

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

In algebra, the factorials arise through the binomial theorem, which uses binomial coefficients to expand powers of sums. 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. Their use in counting permutations can also be restated algebraically: the factorials are the orders of finite symmetric groups. In calculus, factorials occur in Faà di Bruno's formula for chaining higher derivatives. In mathematical analysis, factorials frequently appear in the denominators of power series, most notably in the series for the exponential function, $e^x=1+\frac+\frac+\frac+\cdots=\sum_^\frac,$
and in the coefficients of other Taylor series (in particular those of the trigonometric and hyperbolic functions), where they cancel factors of $n!$ coming from the This usage of factorials in power series connects back to analytic combinatorics through the exponential generating function, which for a combinatorial class with $n_i$ elements of is defined as the power series $\sum_^ \frac.$

In number theory, the most salient property of factorials is the divisibility of $n!$ by all positive integers up 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
$n!\pm 1$, leading to a proof of Euclid's theorem that the number of primes is infinite. When $n!\pm 1$ is itself prime it is called a factorial prime; relatedly, Brocard's problem, also posed by Srinivasa Ramanujan, concerns the existence of square numbers of the form In contrast, the numbers $n!+2,n!+3,\dots n!+n$ must all be composite, proving the existence of arbitrarily large prime gaps. An elementary proof of Bertrand's postulate