In mathematics, the factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n. For example, In statistics, a factorial experiment is an experiment whose design consists of two or more factors, each with discrete possible values or levels, and whose experimental units take on all possible combinations of these levels across all such factors. ... UFD redirects here, but this abbreviation can also mean USB flash drive, an electronic device. ... For the Internet company, see Google. ... For other senses of this word, see sequence (disambiguation). ... The On-Line Encyclopedia of Integer Sequences (OEIS) is an extensive searchable database of integer sequences, freely available on the Web. ... For other meanings of mathematics or uses of math and maths, see Mathematics (disambiguation) and Math (disambiguation). ... A negative number is a number that is less than zero, such as −2. ... Not to be confused with Natural number. ...

and

where n! represents n factorial. The notation n! was introduced by Christian Kramp in 1808. Christian Kramp (July 8, 1760 - May 13, 1826) was a French mathematician, who worked primarily with factorials. ... Year 1808 (MDCCCVIII) was a leap year starting on Friday (link will display the full calendar) of the Gregorian calendar (or a leap year starting on Wednesday of the 12-day slower Julian calendar). ...

Definition

The factorial function is formally defined by

The above definition incorporates the instance

as an instance of the fact that the product of no numbers at all is 1. This fact for factorials is useful, because In mathematics, an empty product, or nullary product, is the result of multiplying no numbers. ...

• the recursive relation works for n = 0;
• it allows simple construction of expressions for infinite polynomials, e.g. ;
• this definition makes many identities in combinatorics valid for zero sizes.
  • In particular, the number of combinations or permutations of an empty set is, simply, 1.

This article is about the concept of recursion. ... Combinatorics is a branch of pure mathematics concerning the study of discrete (and usually finite) objects. ...

Applications

• Factorials are used in combinatorics. For example, there are n! different ways of arranging n distinct objects in a sequence. (The arrangements are called permutations.) And the number of ways one can choose k objects from among a given set of n objects (the number of combinations), is given by the so-called binomial coefficient

• In permutations, if r objects can be chosen from a total of n objects and arranged in different ways, where r ≤ n, then the total number of distinct permutations is given by:

• Factorials also turn up in calculus. For example, Taylor's theorem expresses a function f(x) as a power series in x, basically because the n^th derivative of xⁿ is n!.

• Factorials are also used extensively in probability theory.

• Factorials are often used as a simple example, along with Fibonacci numbers, when teaching recursion in computer science because they satisfy the following recursive relationship (if n ≥ 1):

Combinatorics is a branch of pure mathematics concerning the study of discrete (and usually finite) objects. ... Permutation is the rearrangement of objects or symbols into distinguishable sequences. ... In combinatorial mathematics, a combination of members of a set is a subset. ... In mathematics, particularly in combinatorics, a binomial coefficient is a coefficient of any of the terms in the expansion of the binomial (x+1)n. ... Permutation is the rearrangement of objects or symbols into distinguishable sequences. ... For other uses, see Calculus (disambiguation). ... In calculus, Taylors theorem gives a sequence of approximations of a differentiable function near a given point by polynomials (the Taylor polynomials of that function) whose coefficients depend only on the derivatives of the function at that point. ... In mathematics, a power series (in one variable) is an infinite series of the form where the coefficients an, the center c, and the argument x are usually real or complex numbers. ... For other uses, see Derivative (disambiguation). ... Probability theory is the branch of mathematics concerned with analysis of random phenomena. ... A tiling with squares whose sides are successive Fibonacci numbers in length In mathematics, the Fibonacci numbers are a sequence of numbers named after Leonardo of Pisa, known as Fibonacci. ... A common method of simplification is to divide a problem into subproblems of the same type. ... Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ...

Number theory

Factorials have many applications in number theory. In particular, n! is necessarily divisible by all prime numbers up to and including n. As a consequence, n > 5 is a composite number if and only if Number theory is the branch of pure mathematics concerned with the properties of numbers in general, and integers in particular, as well as the wider classes of problems that arise from their study. ... In mathematics, a prime number (or a prime) is a natural number greater than 1 which has exactly two distinct natural number divisors: 1 and itself. ... A composite number is a positive integer which has a positive divisor other than one or itself. ... ↔ ⇔ ≡ logical symbols representing iff. ...

A stronger result is Wilson's theorem, which states that In mathematics, Wilsons theorem (also known as Al-Haythams theorem) states that p > 1 is a prime number if and only if (see factorial and modular arithmetic for the notation). ...

if and only if p is prime.

Adrien-Marie Legendre found that the multiplicity of the prime p occurring in the prime factorization of n! can be expressed exactly as Adrien-Marie Legendre (September 18, 1752 – January 10, 1833) was a French mathematician. ...

This fact is based on counting the number of factors p between and and 1 and n. All multiples of p from 1 to n are obviously be found with , however we have not counted those with two factors of p. Hence we must now count . We can easily generalize this to infinity. This is finite since the floor function removes all pⁱ > n. The floor and fractional part functions In mathematics, the floor function of a real number x, denoted or floor(x), is the largest integer less than or equal to x (formally, ). For example, floor(2. ...

The only factorial that is also a prime number is 2, but there are many primes of the form , called factorial primes. A factorial prime is a number that is one less or one more than a factorial and is also a prime number. ...

All factorials greater than 0! and 1! are even, as they are all multiples of 2. In mathematics, any integer (whole number) is either even or odd. ...

Rate of growth

Plot of the natural logarithm of the factorial

As n grows, the factorial n! becomes larger than all polynomials and exponential functions in n. Image File history File links This is a lossless scalable vector image. ... Image File history File links This is a lossless scalable vector image. ... In mathematics, a polynomial is an expression that is constructed from one variable or more variables and constants, using only the operations of addition, subtraction, multiplication, and constant positive whole number exponents. ... The exponential function is one of the most important functions in mathematics. ...

When n is large, n! can be estimated quite accurately using Stirling's approximation: The ratio of (ln n!) to (n ln n − n) approaches unity as n increases. ...

A weak version that can easily be proved with mathematical induction is Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers. ...

The logarithm of the factorial can be used to calculate the number of digits in a given base the factorial of a given number will take. It satisfies the identity:-1...

Note that this function, if graphed, is approximately linear, for small values; but the factor , and thereby the slope of the graph, does grow arbitrarily large, although quite slowly. The graph of log(n!) for n between 0 and 20,000 is shown in the figure on the right. A linear function is a mathematical function term of the form: f(x) = m x + c where c is a constant. ...

A simple approximation for log n! based on Stirling's approximation is The ratio of (ln n!) to (n ln n − n) approaches unity as n increases. ...

A much better approximation for log n! was given by Srinivasa Ramanujan^{[citation needed]}: Ramanujan redirects here. ...

One can see from this that log n! is Ο(n log n). This result plays a key role in the analysis of the computational complexity of sorting algorithms (see comparison sort). In computational complexity theory, big O notation is often used to describe how the size of the input data affects an algorithms usage of computational resources (usually running time or memory). ... As a branch of the theory of computation in computer science, computational complexity theory investigates the problems related to the amounts of resources required for the execution of algorithms (e. ... In computer science and mathematics, a sorting algorithm is an algorithm that puts elements of a list in a certain order. ... A comparison sort is a particular type of sorting algorithm; a number of well-known algorithms are comparison sorts. ...

Computation

The value of n! can be calculated by repeated multiplication if n is not too large. The largest factorial that most calculators can handle is 69!, because 70! > 10¹⁰⁰ (except for most HP calculators which can handle 253! as their exponent can be up to 499). The calculator seen in Mac OS X, Microsoft Excel and Google Calculator can handle factorials up to 170!, which is the largest factorial less than 2¹⁰²⁴ (10¹⁰⁰ in hexadecimal) and corresponds to a 1024 bit integer. The values 12! and 20! are the largest factorials that can be stored in, respectively, the 32 bit and 64 bit integers commonly used in personal computers. In practice, most software applications will compute these small factorials by direct multiplication or table lookup. Larger values are often approximated in terms of floating-point estimates of the Gamma function, usually with Stirling's formula. Microsoft Excel (full name Microsoft Office Excel) is a spreadsheet application written and distributed by Microsoft for Microsoft Windows and Mac OS. It features calculation and graphing tools which, along with aggressive marketing, have made Excel one of the most popular microcomputer applications to date. ... This article is about the search engine. ... In mathematics and computer science, hexadecimal, base-16, or simply hex, is a numeral system with a radix, or base, of 16, usually written using the symbols 0–9 and A–F, or a–f. ... This article or section is in need of attention from an expert on the subject. ... The Gamma function along part of the real axis In mathematics, the Gamma function (represented by the capitalized Greek letter Γ) is an extension of the factorial function to real and complex numbers. ... In mathematics, Stirlings approximation (or Stirlings formula) is an approximation for large factorials. ...

For number theoretic and combinatorial computations, very large exact factorials are often needed. Bignum factorials can be computed by direct multiplication, but multiplying the sequence 1 × 2 × ... × n from the bottom up (or top-down) is inefficient; it is better to recursively split the sequence so that the size of each subproduct is minimized. Number theory is the branch of pure mathematics concerned with the properties of numbers in general, and integers in particular, as well as the wider classes of problems that arise from their study. ... Combinatorics is a branch of pure mathematics concerning the study of discrete (and usually finite) objects. ... A bignum package in a computer or program allows internal representation of very large integers, rational numbers, decimal numbers, or floating-point numbers (limitted only by available memory), and provides a set of arithmetic operations on such numbers. ...

The asymptotically-best efficiency is obtained by computing n! from its prime factorization. As documented by Peter Borwein, prime factorization allows n! to be computed in time O(n(log n log log n)²), provided that a fast multiplication algorithm is used (for example, the Schönhage-Strassen algorithm).^[1] Peter Luschny presents source code and benchmarks for several efficient factorial algorithms, with or without the use of a prime sieve.^[2] Peter B. Borwein is a Canadian mathematician, co-developer of an algorithm for calculating Ï€ to the nth digit, co-discoverer of the billionth, four billionth, 40th billionth, and quadrillionth digits of Ï€, and professor at Simon Fraser University. ... In computational complexity theory, big O notation is often used to describe how the size of the input data affects an algorithms usage of computational resources (usually running time or memory). ... A multiplication algorithm is an algorithm (or method) to multiply two numbers. ... In mathematics, the Schönhage-Strassen algorithm is an asympotically fast method for multiplication of large integer numbers. ... In mathematics, a prime sieve or prime number sieve is an algorithm for finding prime numbers. ...

Extension of factorial to non-integer values of argument

The gamma function

Main article: Gamma function

The Gamma function, as plotted here along the real axis, extends the factorial to a smooth function defined for all non-integer values.

The factorial function can also be defined for non-integer values, but this requires more advanced tools from mathematical analysis. The function that "fills in" the values of the factorial between the integers is called the Gamma function, denoted Γ(z) for integers z no less than 1, defined by The Gamma function along part of the real axis In mathematics, the Gamma function (represented by the capitalized Greek letter Γ) is an extension of the factorial function to real and complex numbers. ... Image File history File links Gamma_plot. ... Image File history File links Gamma_plot. ... ... Analysis has its beginnings in the rigorous formulation of calculus. ... The Gamma function along part of the real axis In mathematics, the Gamma function (represented by the capitalized Greek letter Γ) is an extension of the factorial function to real and complex numbers. ...

Euler's original formula for the Gamma function was Euler redirects here. ...

The Gamma function is related to factorials in that it satisfies a similar recursive relationship:

Together with Γ(1) = 1 this yields the equation for any nonnegative integer n:

Based on the Gamma function's value for 1/2, the specific example of half-integer factorials is resolved to In mathematics, a half-integer is a number of the form , where is an integer. ...

For example

The Gamma function is in fact defined for all complex numbers z except for the nonpositive integers . It is often thought of as a generalization of the factorial function to the complex domain, which is justified for the following reasons: A complex number can be visually represented as a pair of numbers forming a vector on a diagram called an Argand diagram In mathematics, the complex numbers are the extension of the real numbers obtained by adjoining an imaginary unit, denoted i, which satisfies:[1] Every complex number can be...

• Shared meaning. The canonical definition of the factorial function shares the same recursive relationship with the Gamma function.
• Context. The Gamma function is generally used in a context similar to that of the factorials (but, of course, where a more general domain is of interest).
• Uniqueness (Bohr–Mollerup theorem). The Gamma function is the only function which satisfies the aforementioned recursive relationship for the domain of complex numbers, is meromorphic, and is log-convex on the positive real axis. That is, it is the only smooth, log-convex function that could be a generalization of the factorial function to all complex numbers.

Euler also developed a convergent product approximation for the non-integer factorials, which can be seen to be equivalent to the formula for the Gamma function above: In mathematical analysis, the Bohr–Mollerup theorem is named after the Danish mathematicians Harald Bohr and Johannes Mollerup, who proved it. ... A meromorphic function is a function that is holomorphic on an open subset of the complex number plane C (or on some other connected Riemann surface) except at points in a set of isolated poles, which are certain well-behaved singularities. ... A function is log-concave, if its natural log , is concave. ...

It can also be written as below:

The product converges quickly for small values of n.

Applications of the gamma function

• The volume of an n-dimensional hypersphere is

For other uses, see Volume (disambiguation). ... For other uses, see Dimension (disambiguation). ... 2-sphere wireframe as an orthogonal projection Just as a stereographic projection can project a spheres surface to a plane, it can also project a 3-spheres surface into 3-space. ...

Factorial at the complex plane

Amplitude and phase of factorial of complex argument.

Representation through the Gamma-function allows evaluation of factorial of complex argument. Equilines of amplitude and phase of factorial are shown in figure. Let . Several levels of constant modulus (amplitude) ρ = const and constant phase are shown. The grid covers range , with unit step. Equilines are dense in vicinity of singularities along negative integer values of the argument. Image File history File links Metadata No higher resolution available. ... Image File history File links Metadata No higher resolution available. ...

Factorial-like products

There are several other integer sequences similar to the factorial that are used in mathematics:

Primorial

The primorial (sequence A002110 in OEIS) is similar to the factorial, but with the product taken only over the prime numbers. For n ≥ 2, the primorial n# is the product of all prime numbers less than or equal to n. ... The On-Line Encyclopedia of Integer Sequences (OEIS) is an extensive searchable database of integer sequences, freely available on the Web. ... In mathematics, a prime number (or a prime) is a natural number greater than 1 which has exactly two distinct natural number divisors: 1 and itself. ...

Double factorial

n!! denotes the double factorial of n and is defined recursively by

For example, 8!! = 2 · 4 · 6 · 8 = 384 and 9!! = 1 · 3 · 5 · 7 · 9 = 945. The sequence of double factorials (sequence A006882 in OEIS) for starts as Three hundred and eighty four is an even composite positive integer. ... The On-Line Encyclopedia of Integer Sequences (OEIS) is an extensive searchable database of integer sequences, freely available on the Web. ...

1, 1, 2, 3, 8, 15, 48, 105, 384, 945, 3840, ...

The above definition can be used to define double factorials of negative numbers:

The sequence of double factorials for starts as

while the double factorial of negative even integers is undefined.

Some identities involving double factorials are:

where Γ is the Gamma function. The last equation above can be used to define the double factorial as a function of any complex number , just as the Gamma function generalizes the factorial function. One should be careful not to interpret n!! as the factorial of n!, which would be written (n!)! and is a much larger number (for n > 2). The Gamma function along part of the real axis In mathematics, the Gamma function (represented by the capitalized Greek letter Γ) is an extension of the factorial function to real and complex numbers. ...

Multifactorials

A common related notation is to use multiple exclamation points to denote a multifactorial, the product of integers in steps of two (n!!), three (n!!!), or more. The double factorial is the most commonly used variant, but one can similarly define the triple factorial (n!!!) and so on. In general, the k^th factorial, denoted by n!^(k), is defined recursively as

Some mathematicians have suggested an alternative notation of n!₂ for the double factorial and similarly n!_k for other multifactorials, but this has not come into general use.

Quadruple factorial

The so-called quadruple factorial, however, is not a multifactorial; it is a much larger number given by . In combinatorial mathematics, the Catalan numbers form a sequence of natural numbers that occur in various counting problems, often involving recursively defined objects. ...

Superfactorials

This section contains information which may be of unclear or questionable importance or relevance to the article's subject matter. Please help improve this article by clarifying or removing superfluous information. (talk)

Neil Sloane and Simon Plouffe defined the superfactorial in 1995 as the product of the first n factorials. So the superfactorial of 4 is Image File history File links No higher resolution available. ... Neil James Alexander Sloane is a US-American mathematician. ... Simon Plouffe is a Quebec mathematician born on June 11, 1956 in St-Jovite. ...

In general

The sequence of superfactorials starts (from n = 0) as

1, 1, 2, 12, 288, 34560, 24883200, ... (sequence A000178 in OEIS)

This idea was extended in 2000 by Henry Bottomley to the superduperfactorial as the product of the first n superfactorials, starting (from n = 0) as The On-Line Encyclopedia of Integer Sequences (OEIS) is an extensive searchable database of integer sequences, freely available on the Web. ...

1, 1, 2, 24, 6912, 238878720, 5944066965504000, ... (sequence A055462 in OEIS)

and thus recursively to any multiple-level factorial where the m^th-level factorial of n is the product of the first n (m − 1)^th-level factorials, i.e. The On-Line Encyclopedia of Integer Sequences (OEIS) is an extensive searchable database of integer sequences, freely available on the Web. ... This article is about the concept of recursion. ...

where mf(n,0) = n for n > 0 and mf(0,m) = 1.

Superfactorials (alternative definition)

This section contains information which may be of unclear or questionable importance or relevance to the article's subject matter. Please help improve this article by clarifying or removing superfluous information. (talk)

Clifford Pickover in his 1995 book Keys to Infinity defined the superfactorial of n as Image File history File links No higher resolution available. ... Clifford A. Pickover is a writer in the fields of science, mathematics, and science fiction. ...

or as,

where the ⁽⁴⁾ notation denotes the hyper4 operator, or using Knuth's up-arrow notation, Tetration (also exponential map, hyperpower, power tower, super-exponentiation, and hyper4) is iterated exponentiation, the first hyper operator after exponentiation. ... In mathematics, an operator is a function that performs some sort of operation on a number, variable, or function. ... In mathematics, Knuths up-arrow notation is a notation for very large integers introduced by Donald Knuth in 1976. ...

This sequence of superfactorials starts:

Hyperfactorials

Occasionally the hyperfactorial of n is considered. It is written as H(n) and defined by

For n = 1, 2, 3, 4, ... the values H(n) are 1, 4, 108, 27648,... (sequence A002109 in OEIS). The On-Line Encyclopedia of Integer Sequences (OEIS) is an extensive searchable database of integer sequences, freely available on the Web. ...

The hyperfactorial function is similar to the factorial, but produces larger numbers. The rate of growth of this function, however, is not much larger than a regular factorial. However, H(14) = 1.85...×10⁹⁹ is already almost equal to a googol, and H(15) = 8.09...×10¹¹⁶ is almost of the same magnitude as the Shannon number, the theoretical number of possible chess games. For the Internet company, see Google. ... The Shannon number, 1078, is an estimation of the game-tree complexity of chess. ...

The hyperfactorial function can be generalized to complex numbers in a similar way as the factorial function. The resulting function is called the K-function. A complex number can be visually represented as a pair of numbers forming a vector on a diagram called an Argand diagram In mathematics, the complex numbers are the extension of the real numbers obtained by adjoining an imaginary unit, denoted i, which satisfies:[1] Every complex number can be... In mathematics, the K-function, typically denoted K(z), is a generalization of the hyperfactorial to complex numbers, similar to the generalization of the factorial to the Gamma function. ...

See also

• Alternating factorial
• Digamma function
• Exponential factorial
• Factoradic
• Factorial prime
• Factorion
• Stirling's approximation
• Trailing zeros of factorial
• Triangular number, the additive analogue of factorial

An alternating factorial is the sum of the first n factorials with the odd-indexed factorials multiplied by −1 if n is even, and the even-indexed factorials multiplied by −1 if n is odd, resulting in an alternation of signs of the summands (or alternation of addition and subtraction... In mathematics, the digamma function is defined as the logarithmic derivative of the gamma function: It is the first of the polygamma functions. ... An exponential factorial is a positive integer n raised to the power of n - 1, which in turn was raised to the power of n - 2, and so on and so forth, that is, . The exponential factorial can also be defined with the recurrence relation . ... The factorial based radix or factoradic is a factorial based mixed radix numeral scheme: radix: 5! 4! 3! 2! 1! decimal: 120 24 6 2 1 In this numbering system, the rightmost digit may be 0 or 1, the next 0, 1, or 2, and so on. ... A factorial prime is a number that is one less or one more than a factorial and is also a prime number. ... A factorion is a natural number that equals the sum of the factorials of its decimal digits. ... The ratio of (ln n!) to (n ln n − n) approaches unity as n increases. ... In mathematics, trailing zeros are a sequence of 0s in the decimal representation (or more generally, in any positional representation) of a number, after which no other digits follow. ... A triangular number is the sum of the n natural numbers from 1 to n. ...

References

External links

• Approximation formulas
• All about factorial notation n!
• The Dictionary of Large Numbers
• Eric W. Weisstein, Factorial at MathWorld.
• "Factorial Factoids" by Paul Niquette
• Factorial at PlanetMath.

Factorial calculators and algorithms

• Fast Online Factorial Calculator Instantly computes factorials up to 5000!
• Factorial calculator up to 2000!
• Factorial Calculator Utility Up to 999!
• "Factorial" by Ed Pegg, Jr. and Rob Morris, The Wolfram Demonstrations Project, 2007.
• Fast Factorial Functions (with source code in Java and C#)