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. In Mathematics, a sequence is an ordered list of objects (or events The On-Line Encyclopedia of Integer Sequences ( OEIS) also cited simply as Sloane's, is an extensive searchable Database of Integer sequences Mathematics is the body of Knowledge and Academic discipline that studies such concepts as Quantity, Structure, Space and A negative number is a Number that is less than zero, such as −2 The integers (from the Latin integer, literally "untouched" hence "whole" the word entire comes from the same origin but via French In Mathematics, a product is the Result of multiplying, or an expression that identifies factors to be multiplied For example,

and

where n! represents n factorial. The notation n! was introduced by Christian Kramp in 1808. Christian Kramp ( July 8, 1760 – May 13, 1826) was a French Mathematician, who worked primarily with Factorials Year 1808 ( MDCCCVIII) was a Leap year starting on Friday (link will display the full calendar of the Gregorian calendar (or a Leap year

Contents 1 Definition 2 Applications 3 Number theory 4 Rate of growth 5 Computation 6 Extension of factorial to non-integer values of argument 6.1 The gamma function 6.2 Applications of the gamma function 6.3 Factorial at the complex plane 7 Factorial-like products 7.1 Primorial 7.2 Double factorial 7.3 Multifactorials 7.4 Quadruple factorial 7.5 Superfactorials 7.6 Superfactorials (alternative definition) 7.7 Hyperfactorials 8 See also 9 References 10 External links

Definition

The factorial function is formally defined by

The above definition incorporates the instance

as an instance of the fact that the product of no numbers at all is 1. In Mathematics, an empty product, or nullary product, is the result of multiplying no numbers This fact for factorials is useful, because

• the recursive relation works for n = 0;
• this definition makes many identities in combinatorics valid for zero sizes. Recursion, in Mathematics and Computer science, is a method of defining functions in which the function being defined is applied within its own definition Combinatorics is a branch of Pure mathematics concerning the study of discrete (and usually finite) objects
  • In particular, the number of combinations or permutations of an empty set is, simply, 1.

Applications

• Factorials are used in combinatorics. Combinatorics is a branch of Pure mathematics concerning the study of discrete (and usually finite) objects For example, there are n! different ways of arranging n distinct objects in a sequence. (The arrangements are called permutations. In several fields of Mathematics the term permutation is used with different but closely related meanings ) 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:

• Factorials also turn up in calculus. In combinatorial mathematics, a combination is an un-ordered collection of distinct elements usually of a prescribed size and taken from a given set In Mathematics, the binomial coefficient \tbinom nk is the Coefficient of the x   k term in the Polynomial In several fields of Mathematics the term permutation is used with different but closely related meanings Calculus ( Latin, calculus, a small stone used for counting is a branch of Mathematics that includes the study of limits, Derivatives 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!. In Calculus, Taylor's theorem gives a sequence of approximations of a Differentiable function around a given point by Polynomials (the Taylor In Mathematics, a power series (in one variable is an Infinite series of the form f(x = \sum_{n=0}^\infty a_n \left( x-c \right^n = a_0 + In Calculus, a branch of mathematics the derivative is a measurement of how a function changes when the values of its inputs change

• Factorials are also used extensively in probability theory. Probability theory is the branch of Mathematics concerned with analysis of random phenomena

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

Number theory

Factorials have many applications in number theory. In Mathematics, the Fibonacci numbers are a Sequence of numbers named after Leonardo of Pisa, known as Fibonacci Recursion in computer science is a way of thinking about and solving problems Computer science (or computing science) is the study and the Science of the theoretical foundations of Information and Computation and their Number theory is the branch of Pure mathematics concerned with the properties of Numbers in general and Integers in particular as well as the wider classes In particular, n! is necessarily divisible by all prime numbers up to and including n. In Mathematics, a prime number (or a prime) is a Natural number which has exactly two distinct natural number Divisors 1 As a consequence, n > 5 is a composite number if and only if

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

if and only if p is prime. A composite number is a positive Integer which has a positive Divisor other than one or itself ↔ In Mathematics, Wilson's theorem states that p > 1 is a Prime number If and only if (p-1!\ \equiv\ -1\ (\mbox{mod}\ p

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 pⁱ > n. Adrien-Marie Legendre ( September 18 1752 – January 10 1833) was a French Mathematician. In Mathematics and Computer science, the floor and ceiling functions map Real numbers to nearby Integers The

The only factorial that is also a prime number is 2, but there are many primes of the form , called factorial primes. A factorial prime is a Prime number that is one less or one more than a Factorial (all factorials above 1 are even

All factorials greater than 0! and 1! are even, as they are all multiples of 2. In Mathematics, the parity of an object states whether it is even or odd

Rate of growth

As n grows, the factorial n! becomes larger than all polynomials and exponential functions in n. In Mathematics, a polynomial is an expression constructed from Variables (also known as indeterminates and Constants using the operations The exponential function is a function in Mathematics. The application of this function to a value x is written as exp( x)

When n is large, n! can be estimated quite accurately using Stirling's approximation:

A weak version that can easily 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. In Mathematics, Stirling's approximation (or Stirling's formula) is an approximation for large Factorials It is named in honour of James Stirling Mathematical induction is a method of Mathematical proof typically used to establish that a given statement is true of all Natural numbers It is done by proving that In Mathematics, the logarithm of a number to a given base is the power or Exponent to which the base must be raised in order to produce It satisfies the identity:

Note that this function, if graphed, is approximately linear, for small values; but the factor , and thereby the slope of the graph, does grow arbitrarily large, although quite slowly. In Mathematics, the term linear function can refer to either of two different but related concepts The graph of log(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

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

One can see from this that log n! is Ο(n log n). In Mathematics, Stirling's approximation (or Stirling's formula) is an approximation for large Factorials It is named in honour of James Stirling In mathematics big O notation (so called because it uses the symbol O) describes the limiting behavior of a function for very small or very large arguments This result plays a key role in the analysis of the computational complexity of sorting algorithms (see comparison sort). Computational complexity theory, as a branch of the Theory of computation in Computer science, investigates the problems related to the amounts of resources In Computer science and Mathematics, a sorting algorithm is an Algorithm that puts elements of a list in a certain order. A comparison sort is a type of Sorting algorithm that only reads the list elements through a single abstract comparison operation (often a "less than or equal to" operator

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! > 10¹⁰⁰ (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 2¹⁰²⁴ (10¹⁰⁰ in hexadecimal) and corresponds to a 1024 bit integer. In Computing, Microsoft Excel (full name Microsoft Office Excel) consists of a proprietary Spreadsheet -application written and distributed Google search is a Web search engine owned by Google Inc, and it is the most used search engine on the Web. In Mathematics and Computer science, hexadecimal (also base -, hexa, or hex) is a Numeral system with a 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. In Computing, floating point describes a system for numerical representation in which a string of digits (or Bits represents a Real number. In Mathematics, the Gamma function (represented by the capitalized Greek letter '''&Gamma''') is an extension of the Factorial function In Mathematics, Stirling's approximation (or Stirling's formula) is an approximation for large Factorials It is named in honour of James Stirling

For number theoretic and combinatorial computations, very large exact factorials are often needed. Number theory is the branch of Pure mathematics concerned with the properties of Numbers in general and Integers in particular as well as the wider classes Combinatorics is a branch of Pure mathematics concerning the study of discrete (and usually finite) objects Bignum factorials can be computed by direct multiplication, but multiplying the sequence 1 × 2 × . On a Computer, arbitrary-precision arithmetic, also called bignum arithmetic is a technique whereby Computer programs perform Calculations on . .  × 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). Peter Benjamin Borwein ( St Andrews, Scotland, 1953 is a Canadian Mathematician, co-developer of an algorithm for calculating π In mathematics big O notation (so called because it uses the symbol O) describes the limiting behavior of a function for very small or very large arguments A multiplication algorithm is an Algorithm (or method to multiply two numbers The Schönhage-Strassen algorithm is an asymptotically fast Multiplication algorithm for large Integers It was developed by Arnold Schönhage and Volker ^[1] Peter Luschny presents source code and benchmarks for several efficient factorial algorithms, with or without the use of a prime sieve. In Mathematics, a variety of Algorithms make it possible to generate Prime numbers efficiently ^[2]

Extension of factorial to non-integer values of argument

The gamma function

Main article: Gamma function

The factorial function can also be defined for non-integer values, but this requires more advanced tools from mathematical analysis. Analysis has its beginnings in the rigorous formulation of Calculus. 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

Euler's original formula for the Gamma function was

The Gamma function is related to factorials in that it satisfies a similar recursive relationship:

Together with Γ(1) = 1 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 . In Mathematics, the Gamma function (represented by the capitalized Greek letter '''&Gamma''') is an extension of the Factorial function In Mathematics, a half-integer is a Number of the form n + 1/2 where n is an Integer. Complex plane In Mathematics, the complex numbers are an extension of the Real numbers obtained by adjoining an Imaginary unit, denoted 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). In mathematical analysis, the Bohr–Mollerup theorem is named after the Danish mathematicians Harald Bohr and Johannes Mollerup, who proved 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. In Complex analysis, a meromorphic function on an open subset D of the Complex plane is a function that is holomorphic In Mathematics, a function f defined on an convex subset of a real Vector space and taking positive values is said to 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:

It can also be written as below:

The product converges quickly for small values of n.

Applications of the gamma function

• The volume of an n-dimensional hypersphere is

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 . Several levels of constant modulus (amplitude) ρ = const and constant phase are shown. The grid covers range , with unit step. Equilines are dense 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 (sequence A002110 in OEIS) is similar to the factorial, but with the product taken only over the prime numbers. The primorial has two similar but distinct meanings The name is attributed to Harvey Dubner and is a Portmanteau of prime and Factorial The On-Line Encyclopedia of Integer Sequences ( OEIS) also cited simply as Sloane's, is an extensive searchable Database of Integer sequences In Mathematics, a prime number (or a prime) is a Natural number which has exactly two distinct natural number Divisors 1

Double factorial

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. Three hundred eighty four is an even composite positive integer The sequence of double factorials (sequence A006882 in OEIS) for starts as

1, 1, 2, 3, 8, 15, 48, 105, 384, 945, 3840, . The On-Line Encyclopedia of Integer Sequences ( OEIS) also cited simply as Sloane's, is an extensive searchable Database of Integer sequences . .

The above definition can be used to define double factorials of negative numbers:

The sequence of double factorials for starts as

while the double factorial of negative even integers is undefined.

Some identities involving double factorials are:

where Γ is the Gamma function. In Mathematics, the Gamma function (represented by the capitalized Greek letter '''&Gamma''') is an extension of the Factorial function The last equation above can be used to define the double factorial as a function of any complex number , 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 k^th factorial, denoted by n!^(k), is defined recursively as

Some mathematicians have suggested an alternative notation of n!₂ for the double factorial and similarly n!_k for other multifactorials, but this has not come into general use.

Quadruple factorial

The quadruple factorial, however, is not a multifactorial; it is a much larger number given by . In combinatorial mathematics, the Catalan numbers form a Sequence of Natural numbers that occur in various Counting problems often involving

Superfactorials

Neil Sloane and Simon Plouffe defined the superfactorial in 1995 as the product of the first n factorials. Neil James Alexander Sloane is a British-[[United States|US]] Mathematician. Simon Plouffe is a Quebec Mathematician born on June 11 1956 in, Quebec. So the superfactorial of 4 is

In general

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, . The On-Line Encyclopedia of Integer Sequences ( OEIS) also cited simply as Sloane's, is an extensive searchable Database of Integer sequences . . (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. The On-Line Encyclopedia of Integer Sequences ( OEIS) also cited simply as Sloane's, is an extensive searchable Database of Integer sequences Recursion, in Mathematics and Computer science, is a method of defining functions in which the function being defined is applied within its own definition e.

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

Superfactorials (alternative definition)

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

or as,

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

This sequence of superfactorials starts:

Hyperfactorials

Occasionally the hyperfactorial of n is considered. Clifford A Pickover is an American author editor and columnist in the fields of Science, Mathematics, and Science fiction, and is employed at the In Mathematics, tetration (also known as hyper -4 In Mathematics, an operator is a function which operates on (or modifies another function In Mathematics, Knuth's up-arrow notation is a method of notation of very large Integers introduced by Donald Knuth in 1976 It is written as H(n) and defined by

For n = 1, 2, 3, 4, . . . the values H(n) are 1, 4, 108, 27648,. . . (sequence A002109 in OEIS). The On-Line Encyclopedia of Integer Sequences ( OEIS) also cited simply as Sloane's, is an extensive searchable Database of Integer sequences

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. A googol is the Large number 10100 that is the digit 1 followed by one hundred zeros (in Decimal representation 09. . . ×10¹¹⁶ is almost of the same magnitude as the Shannon number, the theoretical number of possible chess games. The Shannon number, 10120 is an estimated lower bound on the Game-tree complexity of Chess, calculated by information theorist

The hyperfactorial function can be generalized to complex numbers in a similar way as the factorial function. Complex plane In Mathematics, the complex numbers are an extension of the Real numbers obtained by adjoining an Imaginary unit, denoted The resulting function is called the K-function. In Mathematics, the K-function, typically denoted K ( z) is a generalization of the Hyperfactorial to Complex numbers similar to

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

References

External links

• Approximation formulas
• All about factorial notation n!
• The Dictionary of Large Numbers
• Eric W. Weisstein, Factorial at MathWorld. Eric W Weisstein (born March 18, 1969, in Bloomington Indiana) is an Encyclopedist who created and maintains MathWorld MathWorld is an online Mathematics reference work created and largely written by Eric W
• "Factorial Factoids" by Paul Niquette
• Factorial at PlanetMath. PlanetMath is a free, collaborative online Mathematics Encyclopedia.

Factorial calculators and algorithms

• Factorial calculator up to 2000!
• Factorial Calculator Utility Up to 999!
• "Factorial" by Ed Pegg, Jr. and Rob Morris, The Wolfram Demonstrations Project, 2007. Ed Pegg Jr is an expert on mathematical Puzzles and is a self-described recreational mathematician
• Fast Factorial Functions (with source code in Java and C#)

© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
Dapyx Software network: MP3 Explorer | Ebook Manager | Zenithic