Factorial

In mathematics, the factorial of a positive integer n, denoted n!, is the product of the positive integers less than or equal to n. E.g.,

5! = 5 × 4 × 3 × 2 × 1 = 120

10! = 10 × 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 3,628,800

That 0! is 1 follows from the relationship n! = n × (n-1)!. Anyone even slightly interested in theoretical mathematics should also note that 0! is an instance of the empty product, and that also implies that it must be 1. The fact that 0! = 1 entails that many identities in combinatorics do not have exceptional cases that would otherwise have to be attended to one-by-one.

Usually, n! is read as "n factorial".

Factorials are important in combinatorics because there are n! different ways of arranging n distinct objects in a sequence (see permutation). They also turn up in formulas in calculus, such as in Taylor's theorem, for instance, because the n-th derivative of the function xⁿ is n!.

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

$n!\sim {\sqrt {2\pi n}}\cdot (n/e)^{n}.$

The related gamma function Γ(z) can be defined for all complex numbers z except for z = 0, -1, -2, -3, ... It has the property

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

when n is a non-negative integer. By using this relation, we can extend the definition of factorials and define z! for all complex numbers z except the negative integers.

Algorithm

Factorial numbers can be calculated using a recursive algorithm like following Scheme code.

(define fact
  (lambda (x)
    (if (= x 0)
      1
      (* x (fact (- x 1))))))

This algorithm is not efficient in terms of runtime performance. More sophisticated code can improve performence.

An imperative way of calculating factorial may be more understandable. In Python code:

def fact(x):
    result = 1
    while x > 1:
        result *= x   # multiply result by x
        x -= 1        # decrease x by 1
    return result