Jorge Valle

What is the factorial?

Formula

The factorial of an integer is the product of all integers from that integer down to one. It's denoted by an exclamation mark immediately following the integer. When read aloud, it's voiced as "n factorial".

$$ 5! = 5 \times 4 \times 3 \times 2 \times 1 = 120 $$
Figure 1: Voiced as "five factorial".

Formally, the factorial of an integer $n$ is defined as follows.

$$ n! = n \times (n - 1) \times (n - 2) \times (n - 3) \cdots 2 \times 1 $$
Figure 2: Mathematical definition of factorial.

So we multiply all the terms from $n$ down to one, and the factorial is the result. Simple.

Why is it useful?

Factorials are useful because they afford us an easy way to calculate permutations: the different sequential combinations of $n$ objects that can be achieved.

By way of example, let's say we have three objects: $A, B, C$. Here are all the ways we could sequentially arrange them.

$$ A, B, C \\ A, C, B \\ B, A, C \\ B, C, A \\ C, A, B \\ C, B, A $$
Figure 3: Permutations of three objects.

We can arrange them in six different ways. An easy way to find that out, without having to draw the permutations by hand, would be to calculate the factorial of three: $3!$

$$ 3! = 3 \times 2 \times 1 = 6 $$
Figure 4: Three factorial.

Intractability

Notice that factorials get very large, very quickly.

$$ 5! = 120 \\ 6! = 720 \\ 7! = 5,040 \\ 8! = 40,320 \\ 9! = 362,880 $$
Figure 5: Factorials quickly get massive.

Therefore, in the domain of algorithm analysis, an algorithm running in factorial time is said to be intractable.