Utilisateur:KartikMistry/Factorios

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,

The value of 0! is 1, according to the convention for an empty product.

The factorial operation is encountered in many areas of mathematics, notably in combinatorics, algebra, and mathematical analysis. Its most basic occurrence is the fact that there are n! ways to arrange n distinct objects into a sequence (i.e., permutations of the set of objects). This fact was known at least as early as the 12th century, to Indian scholars. Fabian Stedman in 1677 described factorials as applied to change ringing. After describing a recursive approach, Stedman gives a statement of a factorial (using the language of the original):

Now the nature of these methods is such, that the changes on one number comprehends [includes] the changes on all lesser numbers, ... insomuch that a compleat Peal of changes on one number seemeth to be formed by uniting of the compleat Peals on all lesser numbers into one entire body;

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

The definition of the factorial function can also be extended to non-integer arguments, while retaining its most important properties; this involves more advanced mathematics, notably techniques from mathematical analysis.

Definition

The factorial function is formally defined by the product

or by the recurrence relation

The factorial function can also be defined by using the power rule as

$n!=D^{n}x^{n}\;$

All of the above definitions incorporate the instance

in the first case by the convention that the product of no numbers at all is 1. This is convenient 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 formulae, such as 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 {n}{n}}={\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 or Mathematica.

Applications

Although the factorial function has its roots in combinatorics, formulas involving factorials occur in many areas of mathematics.

• There are n! different ways of arranging n distinct objects into a sequence, the permutations of those objects.
• Often factorials appear in the denominator of a formula to account for the fact that ordering is to be ignored. A classical example is counting k-combinations (subsets of k elements) from a set with n elements. One can obtain such a combination by choosing a k-permutation: successively selecting and removing an element of the set, k times, for a total of

possibilities. This however produces the k-combinations in a particular order that one wishes to ignore; since each k-combination is obtained in k! different ways, the correct number of k-combinations is

This number is known as the binomial coefficient ${\tbinom {n}{k}}$, because it is also the coefficient of X^k in (1 + X)ⁿ.

• Factorials occur in algebra for various reasons, such as via the already mentioned coefficients of the binomial formula, or through averaging over permutations for symmetrization of certain operations.
• Factorials also turn up in calculus; for example they occur in the denominators of the terms of Taylor's formula, where they are used as compensation terms due to the n-th derivative of xⁿ being equivalent to n!.
• Factorials are also used extensively in probability theory.
• Factorials can be useful to facilitate expression manipulation. For instance the number of k-permutations of n can be written as

while this is inefficient as a means to compute that number, it may serve to prove a symmetry property of binomial coefficients:

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

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

if and only if p is prime.

Legendre's formula gives the multiplicity of the prime p occurring in the prime factorization of $n!$ as

or, equivalently,

where $s_{p}(n)$ denotes the sum of the standard base-p digits of 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 1! are even, as they are all multiples of 2. Also, all factorials from 5! upwards are multiples of 10 (and hence have a trailing zero as their final digit), because they are multiples of 5 and 2.

Series of reciprocals

The reciprocals of factorials produce a convergent series: (see e)

Although the sum of this series is an irrational number, it is possible to multiply the factorials by positive integers to produce a convergent series with a rational sum:

The convergence of this series to 1 can be seen from the fact that its partial sums are less than one by an inverse factorial. Therefore, the factorials do not form an irrationality sequence.

Rate of growth and approximations for large n

Plot of the natural logarithm of the factorial

As n grows, the factorial n! increases faster 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

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:

which gives us the estimate

Hence log n! is Θ(n log n) (see Big O notation). 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

It is sometimes practical to use weaker but simpler estimates. Using the above formula it is easily shown that for all n we have $(n/3)^{n}<n!$, and for all n ≥ 6 we have $n!<(n/2)^{n}$.

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

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

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

Another approximation for log n! is given by Srinivasa Ramanujan (Ramanujan 1988)

Thus it is even smaller than the next correction term ${\tfrac {1}{12n}}$ of Stirling's formula.

Hyperfactorial

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

For n = 1, 2, 3, 4, ... the values H(n) are 1, 4, 108, 27648,... suite A002109 de l'OEIS.

The asymptotic growth rate is

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

where A = 1.2824... is the Glaisher–Kinkelin constant. 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. Compared to the Pickover definition of the superfactorial, the hyperfactorial grows relatively slowly.

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.

Notes

[[Catégorie:Combinatoire]] [[Catégorie:Fonction gamma ou associée]]