Sources

Help build the largest human-edited directory on the web.
Submit a site - Become an editor

Wikipedia. Licensed under the GNU Free Documentation License.

Are you an expert in this subject? Join the discussion and share your knowledge at Wikipedia.org.

Factorial

From Wikipedia, the free encyclopedia

(Redirected from Superfactorial)

Jump to: navigation, search

For factorial rings in mathematics, see unique factorization domain.

$n$	$n!$
0	1
1	1
2	2
3	6
4	24
5	120
6	720
7	5040
8	40320
9	362880
10	3628800
15	1307674368000
20	2432902008176640000
25	15511210043330985984000000
50	3.04140932... × 10⁶⁴
70	1.19785717... × 10¹⁰⁰
450	1.73336873... × 10^1,000
3249	6.41233768... × 10^10,000
25206	1.205703438... × 10^100,000
100000	2.8242294079... × 10^456,573

The first few and selected larger members of the sequence of factorials (sequence A000142 in OEIS)

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 \$

where n! represents n factorial. The notation n! was introduced by Christian Kramp in 1808.

1 Definition
2 Applications
3 Number theory
4 Rate of growth
5 Computation
6 The gamma function
- 6.1 Applications of the gamma function
7 Factorial-like products
8 See also
9 References
10 External links

The factorial function is formally defined by

$n!=\prod_{k=1}^n k \qquad \forall n \in \mathbb{N}.\!$

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, clearly, 1.

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

${n\choose k}={n!\over k!(n-k)!}.$

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:

${}_nP_r = \frac{n!}{(n-r)!}.$

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):

$n! = n \times (n-1)!.\,$

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 \ ({\rm mod}\ n).$

A stronger result is Wilson's theorem, which states that

$(p-1)!\ \equiv\ -1 \ ({\rm mod}\ 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_{i=1}^{\infty} \lfloor n/p^i \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.

Plot of the natural logarithm of the factorial

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{2\pi n}\left(\frac{n}{e}\right)^n.$

A weak version that can easily be proved with mathematical induction is

$\left({n \over 3}\right)^n < n! < \left({n \over 2}\right)^n\ \mbox{if}\ n\geq 6.\,$

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_{k=1}^n{\log k}.$

Note that this function, if graphed, is approximately linear, for small values; but the factor ${\log n!} \over n$ , and thereby the slope of the graph, does grow arbitrarily large, although quite slowly. The graph of $l o g (n!)$ 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

$\log n! \approx n\log n - n + \frac {\log n} {2} + \frac {\log(2\pi)} {2}.$

A much better approximation for log n! was given by Srinivasa Ramanujan:

$\log n! \approx n\log n - n + \frac {\log(n(1+4n(1+2n)))} {6} + \frac {\log(\pi)} {2}.$

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).

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 100$ . Computer programs such as Microsoft Excel and Google Calculator can handle factorials as large as $170!$ , which is the largest factorial less than $16256$ ( $10100$ in hexadecimal) and corresponds to a 1024 bit integer. $11!$ and $20!$ are respectively the largest factorials that can be stored in 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 \times 2 \times ... \times 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)²), 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]

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

$\Gamma(z)=\int_{0}^{\infty} t^{z-1} e^{-t}\, \mathrm{d}t. \!$

Euler's original formula for the Gamma function was

$\Gamma(z)=\lim_{n\to\infty}\frac{n^zn!}{\prod_{k=0}^n(z+k)}. \!$

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 $Γ(1) = 1$ this yields the equation for any nonnegative integer $n$ :

$\Gamma(n+1)=n!\,\!$

$\left (\frac{1}{2}\right )! = \frac{\sqrt{\pi}}{2}$

Based on the Gamma function's value for 1/2, the specific example of half-integer factorials is resolved to

$\left (n+\frac{1}{2}\right )!=\sqrt{\pi}\times \prod_{k=0}^n {2k + 1 \over 2}.$

For example

$3.5! = \sqrt{\pi} \cdot {1\over 2}\cdot{3\over2}\cdot{5\over2}\cdot{7\over2} \approx 11.63.$

The Gamma function is in fact defined for all complex numbers $z$ except for the nonpositive integers $(z = 0, - 1, - 2,...)$ . 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{2}{1}\right)^n\frac{1}{n+1}\right]\left[ \left(\frac{3}{2}\right)^n\frac{2}{n+2}\right]\left[ \left(\frac{4}{3}\right)^n\frac{3}{n+3}\right]...$

It can also be written as below:

$n! = \prod_{k = 1}^\infty {\frac{{(k + 1)!}}{{(k - 1)! (n + k)}}}$

The product converges quickly for small values of $n$ .

The volume of an $n$ -dimensional hypersphere can be expressed as:

$V_n={\pi^{n/2}R^n\over \Gamma((n/2)+1)}.$

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

The primorial (sequence A002110 in OEIS) is similar to the factorial, but with the product taken only over the prime numbers.

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

$n!!= \left\{ \begin{array}{ll} 1, &\mbox{if }n=-1\mbox{ or }n=0\mbox{ or }n=1; \\ n(n-2)!! &\mbox{if }n\ge2.\qquad\qquad \end{array} \right.$

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 $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:

$(n-2)!!=\frac{n!!}{n}$

The sequence of double factorials for $n= -1, -3, -5, -7, \dots\,$ starts as

1, - 1,1 / 3, - 1 / 15...

while the double factorial of negative even integers is infinite.

Some identities involving double factorials are:

$n!=n!!(n-1)!! \,$

$(2n)!!=2^nn! \,$

$(2n+1)!!={(2n+1)!\over(2n)!!}={(2n+1)!\over2^nn!}$

$(2n-1)!!={(2n-1)!\over(2n-2)!!}={(2n)!\over2^nn!}$

$\Gamma\left(n+{1\over2}\right)=\sqrt{\pi}\,\,{(2n-1)!!\over2^n}$

$\Gamma\left({n\over2}+1\right)=\sqrt{\pi}\,\,{n!!\over2^{(n+1)/2}}$

where $Γ$ 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$ ).

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

$n!^{(k)}= \left\{ \begin{matrix} 1,\qquad\qquad\ &&\mbox{if }0\le n<k; \\ n(n-k)!^{(k)},&&\mbox{if }n\ge k.\quad\ \ \, \end{matrix} \right.$

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 quadruple factorial, however, is not a multifactorial; it is a much larger number given by $\frac{(2n)!}{n!}$ .

Neil Sloane and Simon Plouffe defined the superfactorial in 1995 as the product of the first $n$ factorials. So the superfactorial of 4 is

$\mathrm{sf}(4)=1! \times 2! \times 3! \times 4!=288 \,$

In general

$\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.$

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

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.

$\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}$

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

Clifford Pickover in his 1995 book Keys to Infinity defined the superfactorial of $n$ as

$n\mathrm{S}\!\!\!\!\!\;\,{!}\equiv \begin{matrix} \underbrace{ n!^{{n!}^{{\cdot}^{{\cdot}^{{\cdot}^{n!}}}}}} \\ n! \end{matrix}, \,$

or as,

$n\mathrm{S}\!\!\!\!\!\;\,{!}=n!^{(4)}n! \,$

where the ⁽⁴⁾ notation denotes the hyper4 operator, or using Knuth's up-arrow notation,

$n\mathrm{S}\!\!\!\!\!\;\,{!}=(n!)\uparrow\uparrow(n!) \,$

This sequence of superfactorials starts:

$1\mathrm{S}\!\!\!\!\!\;\,{!}=1 \,$

$2\mathrm{S}\!\!\!\!\!\;\,{!}=2^2=4 \,$

$3\mathrm{S}\!\!\!\!\!\;\,{!}=6\uparrow\uparrow6=6^{6^{6^{6^{6^6}}}}$

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

$H(n) =\prod_{k=1}^n k^k =1^1\cdot2^2\cdot3^3\cdots(n-1)^{n-1}\cdot n^n.$

For n = 1, 2, 3, 4, ... the values H(n) are 1, 4, 108, 27648,... (sequence A002109 in 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. 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.

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.

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

^ Peter Borwein. "On the Complexity of Calculating Factorials". Journal of Algorithms 6, 376-380 (1985)
^ Peter Luschny, The Homepage of Factorial Algorithms.

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

Factorial Up to 170!
Factorial Calculator Utility Up to 984!
"Factorial" by Ed Pegg, Jr. and Rob Morris, The Wolfram Demonstrations Project, 2007.

Factorial lists

Retrieved from "http://en.wikipedia.org/wiki/Factorial"

Categories: Combinatorics | Number theory | Gamma and related functions | Factorial and binomial topics

Searching reference...

Reference

Related Directory Categories

Sources

Factorial

From Wikipedia, the free encyclopedia

Contents

Top Matching Results

Sponsored Links
This section contains paid listings which have been purchased by companies that want to have their sites appear for specific search terms and related content. These listings are administered, sorted and maintained by a third party and are not endorsed by Search.com.

Search Results

Searching reference...

Reference

Related Directory Categories

Sources

Factorial

From Wikipedia, the free encyclopedia

Contents

Top Matching Results

Sponsored Links This section contains paid listings which have been purchased by companies that want to have their sites appear for specific search terms and related content. These listings are administered, sorted and maintained by a third party and are not endorsed by Search.com.

Search Results

Sponsored Links
This section contains paid listings which have been purchased by companies that want to have their sites appear for specific search terms and related content. These listings are administered, sorted and maintained by a third party and are not endorsed by Search.com.