Factorial

In mathematics, the factorial function gives the number of ways in which n labelled objects (for example the numbers from 1 to n) can be arranged in order. These are the permutations of the set of objects. The function is denoted by n!.

The factorial can be defined by a recurrence relation. If n labelled objects have to be assigned to n places, then the n-th object can be placed in one of n places: the remaining n-1 ojects then have to be placed in the remaining n-1 places, and this is the same problem for the smaller set. So we have

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

and it follows that

$n!=n\cdot (n-1)\cdots 2\cdot 1,\,$

which we could derive directly by noting that the first element can be placed in n ways, the second in n-1 ways, and so on until the last element can be placed in only one remaining way.

Since zero objects can be arranged in just one way ("do nothing") it is conventional to put 0! = 1.

The factorial function is found in many combinatorial counting problems. For example, the binomial coefficients, which count the number of subsets size r drawn from a set of n objects, can be expressed as

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

The factorial function can be extended to arguments other than positive integers: this gives rise to the Gamma function.

Stirling's formula

For large n there is an approximation due to Scottish mathematician James Stirling

$n!\approx {\sqrt {2\pi }}n^{n+1/2}e^{-n}.\,$

References

• Ronald L. Graham; Donald E. Knuth, Oren Patashnik (1989). Concrete Mathematics. Addison Wesley, 111,332. ISBN 0-201-14236-8.