Encyclopedia
In
mathematics, the
factorial of a natural number
n is the product of all positive integers less than or equal to
n. This is written as
n! and pronounced "
n factorial", or colloquially "
n shriek", "
n bang" or "
n crit". The notation
n! was introduced by Christian Kramp in 1808.
The sequence of factorials for
n = 0, 1, 2,... starts:
- 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 6227020800, 87178291200, 1307674368000, 20922789888000, 355687428096000, 6402373705728000, 121645100408832000, 2432902008176640000, ...
This shows how quickly factorial numbers grow. Already 70! = 1.19785717... × 10
100 is larger than a googol.
Definition
The factorial function is formally defined by
For example,
The above definition incorporates the convention that
as an instance of the convention that the product of no numbers at all is 1. This fact for factorials is useful, because
- the recursive relation ! = n! × works for n = 0;
- this definition makes many identities in combinatorics valid for zero sizes.
- In particular, the number of arranging or permutations of an empty set is in just one way.
Non-integer factorials
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 and for
z > −1 defined by
The Gamma function is related to factorials in that it satisfies a similar recursive relationship:
Together with 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
For example
The Gamma function is in fact defined for all
complex numbers
z except for the nonpositive integers where it goes to infinity. It is often thought of as a generalization of the factorial function to the complex domain, which is justified for the following reasons:
- Shared meaning. The canonical definition of the factorial function is the mentioned recursive relationship, shared by both.
- Context. The Gamma function is generally used in a context similar to that of the factorials .
- Uniqueness . The Gamma function is the only function which satisfies the mentioned recursive relationship for the domain of complex numbers and is holomorphic and whose restriction to the positive real axis is log-convex. That is, it is the only function that could possibly be a generalization of the factorial function.
Applications
- Factorials are important in combinatorics. For example, there are n! different ways of arranging n distinct objects in a sequence. And the number of ways one can choose k objects from among a given set of n objects , is given by the so-called binomial coefficient
- In Permutations, if r objects can be chosen and arranged in r different ways from a total of n objects, where r <= n, then the total number of distinct permutations is given by :
P
=
- The volume of an n-dimensional hypersphere can be expressed as:
Note that the Gamma function is required for odd dimensions and that its value cancels out the apparent fractional power of in those cases.
- Factorials are also used extensively in probability theory.
...
s, when teaching
recursion in computer science because they satisfy the following recursive relationship :
Number theory
Factorials have many applications in number theory. Factorial numbers are highly abundant numbers. In particular,
n! is necessarily divisible by all prime numbers up to and including
n. As a consequence,
n > 4 is a composite number if and only if
.
A stronger result is Wilson's theorem, which states that
if and only if
n 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
which is finite since the
floor function removes all .
The only factorial that is also a prime number is 2, but there are many primes of the form . These are called factorial primes.
Rate of growth
As
n grows, the factorial
n! becomes larger than all
polynomials and
exponential functions in
n.
When
n is large,
n! can be estimated quite accurately using
Stirling's approximation:
A weak version that can be proved with
mathematical induction is
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. log
n! can easily be calculated as follows:
Note that this function, if graphed, is approximately
linear, for small values; but the factor does grow arbitrarily large, although quite slowly. The graph of log for
n between 0 and 20,000 is shown in the figure on the right.
A simple approximation for log
n! based on Stirling's approximation is
A much better approximation for log
n! was given by
Srinivasa RamanujanOne can see from this that log is
?. This result plays a key role in the analysis of the computational complexity of sorting algorithms .
Computation
The numeric value of
n! can be calculated by repeated multiplication if
n is not too large. That is basically what pocket calculators do. The largest factorial that most calculators can handle is 69!, because 70! > 10
100. In practice, most software applications use only small factorials which can be computed 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.
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 is inefficient; it is better to recursively split the sequence so that the size of each subproduct is minimized.
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, provided that a fast multiplication algorithm is used . Peter Luschny presents source code and benchmarks for several efficient factorial algorithms, with or without the use of a prime sieve.
Factorial-like products
Primorial
The
primorial is similar to the factorial, but with the product taken only over the prime numbers.
Multifactorials
A common related notation is to use multiple exclamation points to denote a
multifactorial, the product of integers in steps of two , three , or more.
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 for
n = 0, 1, 2,... starts as
- 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
n= -1, -3, -5, -7,... starts as
- 1, -1, 1/3, -1/15 ...
while the double factorial of negative even integers is infinity.
Some identities involving double factorials are:
where is the
Gamma function. The last equation above may be used to define the double factorial as a function of any complex number
n, 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 ! and is a much larger number . Some mathematicians have suggested an alternative notation of
n!
2 for the double factorial and similarly
n!
k for other multifactorials, but this has not come into general use.
The double factorial is the most commonly used variant, but one can similarly define the triple factorial and so on. In general, the
k-th factorial, denoted by
n!
, is defined recursively as
The
quadruple factorial, however, is a much larger number given by .
Superfactorials
Neil Sloane and Simon Plouffe defined the
superfactorial in 1995 as the product of the first
n factorials. So the superfactorial of 4 is
In general
The sequence of superfactorials starts as
- 1, 1, 2, 12, 288, 34560, 24883200, ...
This idea was extended in 2000 by Henry Bottomley to the
superduperfactorial as the product of the first
n superfactorials, starting as
- 1, 1, 2, 24, 6912, 238878720, 5944066965504000, ...
and thus
recursively to any
multiple-level factorial where the
mth-level factorial of
n is the product of the first
n th-level factorials, i.e.
where for and .
Superfactorials
Clifford Pickover in his 1995 book
Keys to Infinity defined the
superfactorial of
n, written as
n$ as
,
or as,
where the
notation denotes the hyper4 operator, or using Knuth's up-arrow notation,
This sequence of superfactorials starts:
Hyperfactorials
- Main article: Hyperfactorial
Occasionally the
hyperfactorial of
n is considered. It is written as
H and defined by
For
n = 1, 2, 3, 4,... the values of
H are 1, 4, 108, 27648,... .
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.
See also
- Alternating factorial
- Digamma function
- Exponential factorial
- Factorial prime
- Factoradic
References
External links
