Factorial
|
|
- This article is not about factorial experiments.
In mathematics, the factorial of a natural number n is the product of the positive integers less than or equal to n. This is written as n! and pronounced "n factorial". The notation n! was introduced by Christian Kramp in 1808.
Since the exclamation mark, "!", is sometimes pronounced "bang" or "shriek", these words are occasionally used colloquially for "factorial" in pronouncing terms like n!.
| Contents |
Definition
The factorial function is formally defined by
- <math>n!=\prod_{k=1}^n k\qquad\mbox{for all }n \ge 0 \!<math>
For example,
- <math>5! = 5 \times 4 \times 3 \times 2 \times 1 = 120<math>
We have
- <math>0! = 1<math>
because the product of no numbers at all is 1. This fact for factorials is useful, because
- the recursive relation (n + 1)! = n! × (n + 1) works for n = 0;
- this definition makes many identities in combinatorics valid for zero sizes.
The sequence of factorials Template:OEIS for n = 0, 1, 2,... starts:
Non-integer factorials
The factorial function can also be defined (for non-integer in addition to the usual integer values of z), via the gamma function:
- <math>z!=\Gamma(z+1)=\int_{0}^{\infty} t^z e^{-t}\, dt \!<math>
The latter representation points at a generalization of the notion of factorial for the set of complex numbers, with the exception of negative integers.
This resolves for the specific example of and a half factorials to
- <math>n!=\sqrt(\pi)\times \prod_{k=0.5}^n k<math>
For example
- <math>3.5! = \sqrt(\pi) \times 3.5 \times 2.5 \times 1.5 \times 0.5<math>
Properties
All factorials are highly abundant numbers.
Applications
- Factorials are important 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
- <math>{n\choose k}={n!\over k!(n-k)!}.<math>
- 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 xn is n!.
- The volume of an n-dimensional hypersphere can be expressed as:
- <math>V_n={\pi^{n/2}R^n\over (n/2)!}<math>
Note that the Gamma function is required for odd dimensions and that its value cancels out the apparent fractional power of <math>\pi<math> in those cases.
- Factorials are also used extensively in probability theory.
- Factorials are often used as a simple example when teaching recursion in computer science because they satisfy the following recursive relationship (if n ≥ 1):
- <math> n! = n \times (n-1)! \,<math>
Calculating factorials
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! > 10100.
When n is large, n! can be estimated quite accurately using Stirling's approximation:
- <math>n!\sim \sqrt{2\pi n}\left(\frac{n}{e}\right)^n<math>
Here is a simple weak version that can be proved using secondary-school mathematics; the essential tool is mathematical induction:
- <math>\left({n \over 3}\right)^n < n! < \left({n \over 2}\right)^n\ \mbox{if}\ n\geq 6\,<math>
Logarithm of the factorial
Log-factorial.PNG
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:
- <math>\sum_{k=1}^n{\log k}<math>
Note that this function, if graphed, is approximately linear, for small values; but the factor <math>{\log n!} \over n<math> 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 good approximation for log n! is to take the logarithm of Stirling's approximation:
- <math>\ln(n!) \approx n\ln(n) - n + \ln(n)/2 + \ln(2 \pi)/2<math>
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.
Generalizations
The gamma function
The related gamma function Γ(z) is defined for all complex numbers z except for the nonpositive integers (z = 0, −1, −2, −3, ...). It is related to factorials in that it satisfies a recursive relationship similar to that of the factorial function:
- <math>n!=n(n-1)! \,<math>
- <math>\Gamma(n+1)=n\Gamma(n) \,<math>
Together with the definition Γ(1) = 1 this yields the equation
- <math>\Gamma(n+1)=n!\qquad\mbox{for all }n\in\mathbb{N},n \ge 1<math>
Because of this relationship, the gamma function is often thought of as a generalization of the factorial function to the domain of complex numbers. This is justified for the following reasons.
- Shared meaning—The canonical definition of the factorial function is the mentioned recursive relationship, shared by both.
- 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.
- 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).
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.
n!! denotes the double factorial of n and is defined recursively by
- <math>
n!!=
\left\{
\begin{matrix}
1,\qquad\quad\ &&\mbox{if }n=0\mbox{ or }n=1;
\\
n(n-2)!!&&\mbox{if }n\ge2.\qquad\qquad
\end{matrix}
\right.
<math>
For example, 8!! = 2 · 4 · 6 · 8 = 384 and 9!! = 1 · 3 · 5 · 7 · 9 = 945. The sequence of double factorials Template:OEIS for n = 0, 1, 2,... starts
Some identities involving double factorials are:
- <math>n!=n!!(n-1)!! \,<math>
- <math>(2n)!!=2^nn! \,<math>
- <math>(2n+1)!!={(2n+1)!\over(2n)!!}={(2n+1)!\over2^nn!}<math>
- <math>\Gamma\left(n+{1\over2}\right)=\sqrt\pi{(2n-1)!!\over2^n}<math>
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 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
- <math>
n!^{(k)}=
\left\{
\begin{matrix}
1,\qquad\qquad\ &&\mbox{if }0\le n
Hyperfactorials
- Main article: Hyperfactorial
Occasionally the hyperfactorial of n is considered. It is written as H(n) and defined by
- <math>
H(n)
=\prod_{k=1}^n k^k
=1^1\cdot2^2\cdot3^3\cdots(n-1)^{n-1}\cdot n^n
<math>
For n = 1, 2, 3, 4,... the values of H(n) are 1, 4, 108, 27648,... Template:OEIS.
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.
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
- <math> \mathrm{sf}(4)=1! \times 2! \times 3! \times 4!=288 \,<math>
In general
- <math>
\mathrm{sf}(n)
=\prod_{k=1}^n k! =\prod_{k=1}^n k^{n-k+1}
=1^n\cdot2^{n-1}\cdot3^{n-2}\cdots(n-1)^2\cdot n^1.
<math>
The sequence of superfactorials starts (from n = 0) as
- 1, 1, 2, 12, 288, 34560, 24883200, ... Template: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
- 1, 1, 2, 24, 6912, 238878720, 5944066965504000, ... Template:OEIS
and thus recursively to any multiple-level factorial where the mth-level factorial of n is the product of the first n (m − 1)th-level factorials, i.e.
- <math>\mathrm{mf}(n,m) = \mathrm{mf}(n-1,m)\mathrm{mf}(n,m-1)
=\prod_{k=1}^n k^{n-k+m-1 \choose n-k} <math>
where <math>\mathrm{mf}(n,0)=n<math> for <math>n>0<math> and <math>\mathrm{mf}(0,m)=1<math>.
Superfactorials (alternative definition)
Clifford Pickover in his 1995 book Keys to Infinity defined the superfactorial of n, written as n$ (the $ should really be a factorial sign ! with an S superimposed) as
- <math>n$\equiv \begin{matrix} \underbrace{ n!^{{n!}^{{\cdot}^{{\cdot}^{{\cdot}^{n!}}}}}} \\ n! \end{matrix} \,<math>,
or as,
- <math>n$=n^{(4)}n \,<math>
where the (4) notation denotes the hyper4 operator, or using Knuth's up-arrow notation,
- <math>n$=(n!)\uparrow\uparrow(n!) \,<math>
This sequence of superfactorials starts:
- <math>1$=1 \,<math>
- <math>2$=2^2=4 \,<math>
- <math>3$=6\uparrow\uparrow6=6^{6^{6^{6^{6^6}}}} \!<math>
Prime factorization of factorials
The power of p occurring in the prime factorization of n! is
- <math>\sum_{i=1}^{\infty} \lfloor n/p^i \rfloor<math>
See also
External links
- table of 2! - 256! (exact) (http://membres.lycos.fr/rsirdey/facttabl.htm)
- The Homepage of Factorial Algorithms shows several interesting algorithms to compute the factorial function. (http://www.luschny.de/math/factorial/FastFactorialFunctions.htm)
- http://factorielle.free.fr
- The Dictionary of Large Numbers (http://home.earthlink.net/~mrob/pub/math/largenum-2.html)cs:Faktoriál
da:Fakultet (matematik)
de:Fakultät (Mathematik)
et:Faktoriaal
es:Factorial
fr:Factorielle
id:Faktorial
io:Faktorialo
is:Aðfeldi
it:Fattoriale
he:עצרת
lt:Faktorialas
nl:Faculteit (wiskunde)
ja:階乗
no:Fakultet (matematikk)
pl:Silnia
pt:Fatorial
ru:Факториал
th:แฟกทอเรียล
fi:Kertoma
uk:Факторіал
zh:階乘