Dictionary Definition
factorial adj : of or relating to factorials n :
the product of all the integers up to and including a given
integer; "1, 2, 6, 24, and 120 are factorials"
User Contributed Dictionary
English
Pronunciation
- /fækˈtɔːɹiəl/, /f
Extensive Definition
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,
- 5 ! = 1 \times 2 \times 3 \times 4 \times 5 = 120 \
- and
- 6 ! = 1 \times 2 \times 3 \times 4 \times 5 \times 6 = 720 \
Definition
The factorial function is
formally defined by
- n!=\prod_^n k \qquad \forall n \in \mathbb.\!
The above definition
incorporates the instance
- 0! = 1 \
as an instance of the fact
that the product of no
numbers at all is 1. This fact for factorials is useful,
because
- the recursive relation (n + 1)! = n! \times (n + 1) works for n = 0;
- 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.
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:
-
- _nP_r = \frac.
- 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 nth derivative of xn 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):
-
- n! = n \times (n-1)!.\,
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
- (n-1)!\ \equiv\ 0 \ (\ n).
A stronger result is Wilson's
theorem, which states that
- (p-1)!\ \equiv\ -1 \ (\ p)
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
- \sum_^ \left \lfloor \frac \right \rfloor ,
which is finite since the
floor
function removes all p^i > n.
The only factorial that is
also a prime number is 2, but there are many primes of the form
\scriptstyle n!\, \pm\, 1, called factorial
primes.
All factorials greater than 0!
and 1! are even,
as they are all multiples of 2.
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:
- n!\approx \sqrt\left(\frac\right)^n.
A weak version that can easily
be proved with mathematical
induction is
- \left(\right)^n
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:
- \log n! = \sum_^n.
Note that this function, if
graphed, is approximately linear,
for small values; but the factor \over n, 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 simple approximation for
based on Stirling's
approximation is
- \log n! \approx n\log n - n + \frac + \frac .
A much better approximation
for was given by Srinivasa
Ramanujan:
- \log n! \approx n\log n - n + \frac + \frac .
One can see from this that is
Ο(n log
n). This result plays a key role in the analysis of the
computational complexity of sorting
algorithms (see comparison
sort).
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! > 10100 (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 21024 (10100 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.
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.
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)2),
provided that a fast multiplication
algorithm is used (for example, the
Schönhage-Strassen algorithm). Peter Luschny presents source
code and benchmarks for several efficient factorial algorithms,
with or without the use of a prime
sieve.
Extension of factorial to non-integer values of argument
The gamma function
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 \Gamma(z) for integers z no less than 1,
defined by
- \Gamma(z)=\int_^ t^ e^\, \mathrmt. \!
Euler's
original formula for the Gamma function was
- \Gamma(z)=\lim_\frac. \!
The Gamma function is related
to factorials in that it satisfies a similar recursive
relationship:
- n!=n(n-1)! \,
- \Gamma(n+1)=n\Gamma(n) \,
Together with \Gamma(1)=1 this
yields the equation for any nonnegative integer n:
- \Gamma(n+1)=n!\,\!
- \left (\frac\right )! = \frac
- \left (n+\frac\right )!=\sqrt\times \prod_^n .
For example
- 3.5! = \sqrt \cdot \cdot\cdot\cdot \approx 11.63.
The Gamma function is in fact
defined for all complex
numbers z except for the nonpositive integers \scriptstyle(z\,
=\, 0,\, -1,\, -2,\, \dots). 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 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:
- n! \approx \left[ \left(\frac\right)^n\frac\right]\left[ \left(\frac\right)^n\frac\right]\left[ \left(\frac\right)^n\frac\right]\dots
It can also be written as
below:
n! = \prod_^\infty
.
The product converges quickly
for small values of n.
Applications of the gamma function
- The volume of an n-dimensional hypersphere is
-
- V_n=.
Factorial at the complex plane
Representation through the Gamma-function allows evaluation of factorial of complex argument. Equilines of amplitude and phase of factorial are shown in figure. Let f=\rho \exp(\varphi)=(x+y)!=\Gamma(x+y+1) . Several levels of constant modulus (amplitude) \rho =\rm const and constant phase \varphi=\rm const are shown. The grid covers range ~-3 \le x \le 3~, ~-2 \le y \le 2~ with unit step. Equilines are dence in vicinity of singularities along negative integer values of the argument.Factorial-like products
There are several other integer sequences similar to the factorial that are used in mathematics:Primorial
The primorial is similar to the factorial, but with the product taken only over the prime numbers.Double factorial
n!! denotes the double factorial of n and is defined recursively byn!!= \begin
1,&\mboxn=0\mboxn=1; \\ n\times(n-2)!!
&\mboxn\ge2.\qquad\qquad \end
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, \dots 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:
- (n-2)!!=\frac.
The sequence of double
factorials for n= -1, -3, -5, -7, \dots\, starts as
- 1, -1, \tfrac, -\tfrac, \dots
while the double factorial of
negative even integers is undefined.
Some identities involving
double factorials are:
- n!=n!!(n-1)!! \,
- (2n)!!=2^nn! \,
- (2n+1)!!==
- (2n-1)!!==
- \Gamma\left(n+\right)=\sqrt\,\,
- \Gamma\left(+1\right)=\sqrt\,\,
where \Gamma is the Gamma
function. The last equation above can be used to define the
double factorial as a function of any complex number n \neq 0, 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).
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 kth factorial, denoted by n!^, is defined recursively
as
n!^= \left\