Factorial

From Wikipedia, the free encyclopedia

For the experimental technique, see factorial experiment.

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	5,040
8	40,320
9	362,880
10	3,628,800
11	39,916,800
12	479,001,600
13	6,227,020,800
14	87,178,291,200
15	1,307,674,368,000
20	2,432,902,008,176,640,000
25	15,511,210,043,330,985,984,000,000
50	3.04140932... × 10⁶⁴
70	1.19785717... × 10¹⁰⁰
450	1.73336873... × 10^1,000
1754	1.979262... × 10^4,930
3,249	6.41233768... × 10^10,000
25,206	1.205703438... × 10^100,000
47,176	8.4485731495... × 10^200,001
100,000	2.8242294079... × 10^456,573
1,000,000	8.2639316883... × 10^5,565,708
10³⁰⁵	10^{3.045657055180967... × 10³⁰⁷}

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

In mathematics, the factorial of a positive integer n,^[1] 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 \$

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

The factorial function can also be defined for non-integer values, which involves more advanced mathematics, especially mathematical analysis.

[edit] Definition

The factorial function is formally defined by

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

or recursively defined by

$n! = \begin{cases} 1 & \text{ if } n = 0 \\ n ((n-1)!) & \text{ if } n > 0 \\ \end{cases} \qquad \forall n \in \mathbb{N}.$

Both of the above definitions incorporate the instance

$0! = 1, \$

a result of the fact that the product of no numbers at all is 1. This is useful because:

there is exactly one permutation of zero objects (with nothing to permute, "everything" is left in place);
the recurrence relation (n + 1)! = n! × (n + 1), valid for n > 0, extends to n = 0;
it allows for the expression of many formulas, like the exponential function as a power series:

$e^x = \sum_{n = 0}^{\infty}\frac{x^n}{n!};$

it makes many identities in combinatorics valid for all applicable sizes. The number of ways to choose 0 elements from the empty set is $\tbinom{0}{0} = \tfrac{0!}{0!0!} = 1$ . More generally, the number of ways to choose (all) n elements among a set of n is $\tbinom nn = \tfrac{n!}{n!0!} = 1$ ;

The factorial function can also be defined for non-integer values using more advanced mathematics, detailed in the section below. This more generalized definition is used by advanced calculators and mathematical software such as Maple.

[edit] 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

$^nC_k=C(n,k)={n\choose k}={n!\over k!(n-k)!}.$

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

${}^nP_r= P(n,r)= \frac{n!}{(n-r)!}.$

Factorials are used in binomial series expansion. The nth term of (1 + x)ⁿ is given by

$\frac{n!}{r!(n-r)!} x^{n-1}.$

Factorials also turn up in calculus. For example, Taylor's theorem expresses a function ƒ(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)!.\,$

[edit] 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 \ ({\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} \left \lfloor \frac{n}{p^i} \right \rfloor .$

This fact is based on counting the number of factors p of the integers from 1 to n. The number of multiples of p in the numbers 1 to n are given by $\textstyle \left \lfloor \frac{n}{p} \right \rfloor$ ; however, this formula counts those numbers with two factors of p only once. Hence another $\textstyle \left \lfloor \frac{n}{p^2} \right \rfloor$ factors of p must be counted too. Similarly for three, four, five factors, to infinity. The sum is finite since pⁱ is less than or equal to n for only finitely many values of i, and the floor function results in 0 when applied to pⁱ > n.

The only factorial that is also a prime number is 2, but there are many primes of the form n ± 1, called factorial primes.

All factorials greater than 0! and 1! are even, as they are all multiples of 2.

[edit] 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 (but slower than double exponential functions) in n.

Most approximations for n! are based on approximating its natural logarithm

$\log n! = \sum_{x=1}^n \log x.$

The graph of the function f(n)=log n! is shown in the figure on the right. It looks approximately linear for all reasonable values of n, but this intuition is false. We get one of the simplest approximations for log n! by bounding the sum with an integral from above and below as follows:

$\int_1^n \log x \, dx \leq \sum_{x=1}^n \log x \leq \int_0^n \log (x+1) \, dx$

which gives us the estimate

$n\log\left(\frac{n}{e}\right)+1 \leq \log n! \leq (n+1)\log\left( \frac{n+1}{e} \right) + 1.$

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

From the bounds on log n! deduced above we get that

$e\left(\frac ne\right)^n \leq n! \leq e\left(\frac{n+1}e\right)^{n+1}.$

For large n we get a better estimate for the number n! using Stirling's approximation:

$n!\approx \sqrt{2\pi n}\left(\frac{n}{e}\right)^n.$

In fact, it can be proved that for all n we have

$n! > \sqrt{2\pi n}\left(\frac{n}{e}\right)^n.$

A much better approximation for log n! was given by Srinivasa Ramanujan (Ramanujan 1988)

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

[edit] 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 69! < 10¹⁰⁰ < 70!. Calculators that use 3-digit exponents can compute larger factorials, up to, for example, 253! ≈ 5.2×10⁴⁹⁹ on HP calculators and 449! ≈ 3.9×10⁹⁹⁷ on the TI-86. The calculator seen in Mac OS X, Microsoft Excel and Google Calculator can handle factorials up to 170!, which is the largest factorial that can be represented as a 64-bit IEEE 754 floating-point value. The scientific calculator in Windows XP is able to calculate factorials up to at least 100000!. This calculator can display exponents of more than 1,000,000, although exponent input is limited to 10000. 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)²), provided that a fast multiplication algorithm is used (for example, the Schönhage-Strassen algorithm).^[2] Peter Luschny presents source code and benchmarks for several efficient factorial algorithms, with or without the use of a prime sieve.^[3]

[edit] Extension of factorial to non-integer values of argument

[edit] The Gamma and Pi functions

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, generalized to all complex numbers except negative integers. For example, 0! = 1! = 1, (−0.5)! = √π, (0.5)! = √π/2.

Besides nonnegative integers, the factorial function can also be defined for non-integer values, but this requires more advanced tools from mathematical analysis. One function that "fills in" the values of the factorial (but with a shift of 1 in the argument) is called the Gamma function, denoted Γ(z), defined for all complex numbers z except the non-positive integers, and given when the real part of z is positive by

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

Its relation to the factorials is that for any natural number n

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

Euler's original formula for the Gamma function was

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

It is worth mentioning that there is an alternative notation which was originally introduced by Gauss and which is sometimes used is the Pi function, denoted Π(z) for real numbers z no less than 0, defined by

$\Pi(z)=\int_0^\infty t^{z} e^{-t}\, \mathrm{d}t. \!$

which in terms of the Gamma function is

$\Pi(z) = \Gamma(z+1) \,$

so that it truly extends the factorial:

$\Pi(n) = n!\text{ for }n \in \mathbf{N}. \,$

In addition to this, the Pi function satisfies the same recurrence as factorials do, but at every complex value z where it is defined

$\Pi(z) = z\Pi(z-1)\,$

(in fact this is no longer a recurrence relation but a functional equation). Expressed in terms of the Gamma function this functional equation takes the form

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

Since the factorial is extended by the Pi function, for every complex value z where it is defined, we can write:

$z! = \Pi(z)\,$

The values of these functions at half-integer values is therefore determined by a single one of them; one has

$\Gamma\left (\frac{1}{2}\right )=\Pi\left (-\frac{1}{2}\right )=\left (-\frac{1}{2}\right )! = \sqrt{\pi}.$

from which it follows that for n ∈ N,

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

For example

$3.5! = \Pi(3.5) = {P(7,4) \over 2^7} \sqrt{\pi} = {7! \over 2^7 3!} \sqrt{\pi} = {1\over 2}\cdot{3\over2}\cdot{5\over2}\cdot{7\over2} \sqrt{\pi} = {105 \over 16} \sqrt{\pi} \approx 11.63.$

The Pi function is certainly not the only way to extend factorials to a function defined at almost all complex values, and not even the only one that is analytic wherever it is defined. Nonetheless it is usually considered the most natural way to extend the values of the factorials to a complex function. For instance, the Bohr–Mollerup theorem states that the Gamma function is the only function that takes the value 1 at 1, satisfies the functional equation Γ(n + 1) = nΓ(n), is meromorphic on the complex numbers, and is log-convex on the positive real axis. A similar statement holds for the Pi function as well, using the Π(n) = nΠ(n − 1) functional equation.

There exist however complex functions which are provably simpler in the sense of analytic function theory, and which interpolate the factorial values, for example Hadamard's 'Gamma'-function (Hadamard 1894) which, unlike the Gamma function, is an entire function.^[4]

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! = \Pi(n) = \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]\cdots.$

It can also be written as

$n! = \Pi(n) = \prod_{k = 1}^\infty \left(\frac{k+1}{k}\right)^n\!\!\frac{k}{n+k}.$

This formula does not however provide a very practical means of computing the Pi or Gamma function, as its rate of convergence is very slow.

[edit] Applications of the gamma function

The volume of an n-dimensional hypersphere of radius R is

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

[edit] 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 $f=\rho \exp({\rm i}\varphi)=(x+{\rm i}y)!=\Gamma(x+{\rm i}y+1)$ . Several levels of constant modulus (amplitude) $ρ = 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. The scratched line shows the level $\varphi=\pm \pi$ .

Thin lines show intermediate levels of constant modulus and constant phase. At poles $x+ {\rm i}y \in \rm (negative ~ integers)$ , phase and amplitude are not defined. Equilines are dense in vicinity of singularities along negative integer values of the argument.

For moderate values of $| z | < 1$ , the Taylor expansions can be used:

$z!=\sum_{n=0}^{\infty} g_n z^n.$

The first coefficients of this expansion are

$n$	$g n$	approximation
0	$1$	$1$
1	$- γ$	$- 0.5772156649$
2	$\frac{\pi^2}{12}+\frac{\gamma^2}{2}$	$0.9890559955$
3	$-\frac{\zeta(3)}{3}-\frac{\pi^2\gamma}{12}+\frac{\gamma^3}{6}$	$- 0.9074790760$

where $γ$ is the Euler constant and $ζ$ is the Riemann function. Computer algebra systems such as Mathematica can generate many terms of this expansion.

[edit] Approximations of factorial

For the large values of the argument, factorial can be approximated through the integral of the psi function, using the continued fraction representation ^[5].

$\mathrm{factorial}(z)=\exp\big(P(z))$

$P(z) = p(z) + \frac{\log(2\pi)}{2} - z + \left(z+\frac{1}{2}\right)\log(z);$

$p(z)=\cfrac{a_0}{z+ \cfrac{a_1}{z+ \cfrac{a_2}{z+ \cfrac{a_3}{z+\ddots}}}}$

The first coefficients in this continued fraction are

$\begin{array}{cc} n& a_n\\ 0&1/12 \\ 1&1/30 \\ 2&53/210 \\ 3&195/371 \\ 4&22999/22737 \\ 5&29944523/19773142 \\ 6&109535241009/48264275462 \\ 7&29404527905795295658/9769214287853155785 \\ 8&455377030420113432210116914702/113084128923675014537885725485 \end{array}$

There is common misconception, that $log(z!) = P (z)$ or $\log(\Gamma(z\!+\!1))=P(z)$ for any complex z ≠ 0. Indeed, the relation through the logarithm is valid only for specific range of values of z in vicinity of the real axis, while $|\Im(\Gamma(z\!+\!1))| < \pi$ . The larger is the real part of the argument, the smaller should be the imaginary part. However, the inverse relation, z! = exp(P(z)), is valid for the whole complex plane, the only, z in the continued fraction should not be zero, and the convergence is poor in vicinity of the negative part of the real axis. (It is difficult to have good convergence of any approximation in vicinity of the singularities). While $|\Im(z)| >2$ or $\Re(z)>2$ , the 8 coefficients above are sufficient for the evaluation of the factorial with the complex<double> precision.

[edit] Non-extendability to negative integers

The relation n ! = (n − 1)! × n allows one to compute the factorial for an integer given the factorial for a smaller integer. The relation can be inverted so that one can compute the factorial for an integer given the factorial for a larger integer:

$n! = \frac{(n+1)!}{n+1}.$

Note, however, that this recursion does not permit us to compute the factorial of a negative integer; use of the formula to compute (−1)! would require a division by zero, and thus blocks us from computing a factorial value for every negative integer. (Similarly, the Gamma function is not defined for non-positive integers, though it is defined for all other negative numbers.)

In particular, factorials for the negative integers are not based on multiplying integers that are sequentially closer to zero. That is,

$(-3)!\neq(-3)(-2)(-1)=-6. \,$

[edit] Factorial-like products and functions

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

[edit] Primorial

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

[edit] Double factorial

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

$n!!= \begin{cases} 1,&\text{if }n=1; \\ n\times((n-2)!!) &\text{if }n > 1.\qquad\qquad \end{cases}$

For example, 9!! = 1 × 3 × 5 × 7 × 9 = 945. 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).

Sometimes n!! is defined for non-negative even numbers as well. One choice is the recursive definition

$n!!= \begin{cases} 1,&\text{if }n=0, \\ n\times((n-2)!!) &\text{if }n > 1.\qquad\qquad \end{cases}$

For example, with this definition, 8!! = 2 × 4 × 6 × 8 = 384. However, note that such use is inconsistent with the extension of the definition of $n!!$ to real and complex numbers $n$ that is achieved via the Gamma function; see below.

The sequence of double factorials for n = 1, 3, 5, 7, ... (sequence A001147 in OEIS) starts as

1, 3, 15, 105, 945, 10395, 135135, ....

The sequence for n = 0, 1, 2, 3, 4, ... (sequence A006882 in OEIS) starts as

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

The definition of the double factorial for positive odd numbers can be rewritten to define double factorials for negative odd numbers:

$n!!= \begin{cases} 1,&\text{if }n=1; \\ \frac{(n+2)!!}{n+2} &\text{if }n < 1.\qquad\qquad \end{cases}$

The sequence of double factorials for n = −1, −3, −5, −7, ... starts as

$1, -1, \frac{1}{3}, -\frac{1}{15}, \dots$

Some identities involving double factorials (with the above definition for even values of n) are:

$n!!= \begin{cases} n (n-2)\cdots 3\cdot 1 & \text{if }n\mbox{ is odd and }n>0\qquad\qquad \\ n (n-2)\cdots 4\cdot 2 & \text{if }n\mbox{ is even and }n>0\qquad\qquad \\ \end{cases}$

$n!!= \left(\frac{2}{\pi}\right)^{\frac{1-\cos \pi n}{4}}2^{\frac{n}{2}}\Gamma\left(\frac{n}{2}+1\right)$

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

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

$(2n+1)!! = {(2n+1)!\over(2n)!!} = {(2n+1)! \over 2^n n!} = 2^n n! {n+\frac 1 2 \choose n} = (-2)^{n+1} (n+1)! {-\frac 1 2 \choose n+1}.$

$(2n-1)!! = {(2n-1)!\over(2n-2)!!} = {P(2n,n) \over 2^n} = {(2n)! \over 2^n n!} = 2^n n! {n-\frac 1 2 \choose n} = (-2)^n n! {-\frac 1 2 \choose n}.$

[edit] Alternate extension of the double factorial

Disregarding the above definition of n!! for even values of n, the double factorial for odd integers can be extended to most real and complex numbers via the formula

$n!! = \frac{\int_0^\infty (2t)^{n/2}~e^{-t}~dt}{\int_0^\infty (2t)^{1/2}~e^{-t}~dt} = 2^{(n-1)/2} \frac{\Gamma(\frac{n}{2} + 1)}{\Gamma(\frac{1}{2} + 1)} = \sqrt{\frac{2^{n+1}}{\pi}} \Gamma\left(\frac{n}{2}+1\right),\,$

where $Γ$ is the Gamma function. This bears similarity to the Gamma function generalization of the factorial function. With this definition, n!! is defined for all complex numbers except the negative even numbers. With this definition, the volume of an n-dimensional hypersphere of radius R is

$V_n=\frac{2 (2\pi)^{(n-1)/2}}{n!!} R^n.$

[edit] 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. One can define the k^th factorial, denoted by $n! (k)$ , recursively for non-negative integers 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.$

though see the alternative definition below.

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.

With the above definition, $(k n)! (k) = k n n!.$

In the same way that $n!$ is not defined for negative integers, and $n!!$ is not defined for negative even integers, $n! (k)$ is not defined for negative integers evenly divisible by $k$ .

Alternatively, the multifactorial $n! (k)$ can be defined for the complex number $n$ (except for the negative integers evenly divisible by $k$ ) with

$n!^{(k)} = \frac{\int_{0}^{\infty} (kt)^{n/k}~e^{-t}~dt}{\int_{0}^{\infty} (kt)^{1/k}~e^{-t}~dt} = k^{(n-1)/k} \frac{\Gamma\left(\frac{n}{k}+1\right)}{\Gamma\left(\frac{1}{k}+1\right)}\,,$

where $Γ(z)$ is the Gamma function. This definition is consistent with the earlier definition only for those integers $n$ satisfying $(n mod k) = 1.$ In addition to extending $n! (k)$ to complex values for $n$ , this definition has the feature of working for all positive real values of $k$ .

[edit] Quadruple factorial

The so-called quadruple factorial, however, is not the multifactorial n!⁽⁴⁾; it is a much larger number given by (2n)!/n!, starting as

1, 2, 12, 120, 1680, 30240, 665280, ... (sequence A001813 in OEIS).

It is also equal to

$\begin{align} 2^n\frac{(2n)!}{n!2^n} & = 2^n \frac{(2\cdot 4\cdots 2n) (1\cdot 3\cdots (2n-1))}{2\cdot 4\cdots 2n} \\[8pt] & = (1\cdot 2)\cdot (3 \cdot 2) \cdots((2n-1)\cdot 2)=(4n-2)!^{(4)}. \end{align}$

[edit] Superfactorial

Main article: Large numbers

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)

[edit] Alternative definition

Clifford Pickover in his 1995 book Keys to Infinity used a new notation, n$, to define the superfactorial

$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^{6^6}}}}.$

Here, as is usual for compound exponentiation, the grouping is understood to be from right to left:

$a^{b^c}=a^{(b^c)}.\,$

[edit] Hyperfactorial

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 asymptotic growth rate is

$H(n) \sim A n^{(6n^2 + 6n + 1)/12} e^{-n^2/4}$

where A = 1.2824... is the Glaisher–Kinkelin constant.^[6] H(14) = 1.8474...×10⁹⁹ is already almost equal to a googol, and H(15) = 8.0896...×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.

[edit] 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

[edit] Notes

^ Weisstein, Eric W., "Factorial" from MathWorld.
^ Peter Borwein. "On the Complexity of Calculating Factorials". Journal of Algorithms 6, 376-380 (1985)
^ Peter Luschny, Fast-Factorial-Functions: The Homepage of Factorial Algorithms.
^ Peter Luschny, Hadamard versus Euler - Who found the better Gamma function?.
^ M.Abramowitz, I.Stegun. Handbook on special functions, formula (6.1.48), http://www.math.sfu.ca/~cbm/aands/page_258.htm
^ Weisstein, Eric W., "Glaisher–Kinkelin Constant" from MathWorld.

[edit] References

Hadamard, M. J. (1894) (in French), Sur L’Expression Du Produit 1·2·3· · · · ·(n-1) Par Une Fonction Entière, OEuvres de Jacques Hadamard, Centre National de la Recherche Scientifiques, Paris, 1968, http://www.luschny.de/math/factorial/hadamard/HadamardFactorial.pdf
Ramanujan, Srinivasa (1988), The lost notebook and other unpublished papers, Springer Berlin, p. 339

[edit] External links

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

Factorial calculators and algorithms

Exact Factorial Calculator: computes factorials up to 200,000!.
Factorial Calculator: instantly finds factorials up to 10^14!
Animated Factorial Calculator: shows factorials calculated as if by hand using common elementary school aglorithms
"Factorial" by Ed Pegg, Jr. and Rob Morris, Wolfram Demonstrations Project, 2007.
Fast Factorial Functions (with source code in Java and C#)

[0] Weisstein, Eric W., "Factorial" from MathWorld.

[1] Peter Borwein. "On the Complexity of Calculating Factorials". Journal of Algorithms 6, 376-380 (1985)

[2] Peter Luschny, Fast-Factorial-Functions: The Homepage of Factorial Algorithms.

[3] Peter Luschny, Hadamard versus Euler - Who found the better Gamma function?.

[IRENE6.1.48-4] M.Abramowitz, I.Stegun. Handbook on special functions, formula (6.1.48), http://www.math.sfu.ca/~cbm/aands/page_258.htm

[5] Weisstein, Eric W., "Glaisher–Kinkelin Constant" from MathWorld.

[1]

[2]

[3]

[4]

[5]

[6]