Factorial

discrete-math

Definition

Factorial

The factorial of a non-negative integer $n$ is the product of all positive integers up to $n$:

$$n!:=\prod _{k=1}^{n}k,0!:=1.$$

Equivalently, the factorial function is defined recursively by

$$\begin{array}{rlrl}0!& =1,& & \\ n!& =n(n-1)!& & \text{for }n\ge 1.\end{array}$$

Combinatorial Meaning

For a finite set $X$ with $|X|=n$, the value $n!$ is the number of permutations of its elements:

$$n!=|\{\pi :X\to X\mid \pi \text{ is bijective}\}|.$$

To construct a permutation, there are $n$ choices for its first position, $n-1$ for its second, and so on. The product rule therefore gives

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

Why Zero Factorial Is One

The empty set has exactly one permutation: the empty arrangement. Hence $0!=1$. This value is also forced by the recurrence,

$$1!=1\cdot 0!,$$

which requires $0!=1$.

Examples

Arranging four objects

Four distinct objects can be ordered in

$$4!=4\cdot 3\cdot 2\cdot 1=24$$

different ways.