Factorials

A factorial is an equation that is abbreviated by a number followed by an ! such as:
2!

The idea behind a factorial is very simple. It is a shorthand for a series of multiplications where each multiple is one less than the previous value.

For example:

1! = 1
2! = 2 * 1 = 2
3! = 3 * 2 * 1 = 6
4! = 4 * 3 * 2 * 1 = 24

Factorials are often used in problems of permutations.

Let's start with a situation where we won't need factorials. Assuming that we have 5 roles and 5 people and each person can take any role and can take as many roles as they want. How many different permutations are there?

There are 5 ways to divide up the first role, 5 ways to divide up the second role, and so on. The answer turns out to be: 5 * 5 * 5 *5 *5 = 5⁵ [If you need a review of exponents, review here]

What if we say that each person can only take one role. In other words, we are taking 5 people and dividing them up into 5 roles. In this case, the following happens:

There are 5 ways to divide up the first role, but only 4 ways to divide up the second role, and then 3 ways to divide up the third role, etc. The answer turns out to be 5 * 4 * 3 * 2 * 1 = 5!.

We can generalize this point and make it into an exact equation. For any set of n elements,
there are exactly n! ways of ordering it. This is easy to show.

Lemma 1: For a set of n elements, there are n! ways of ordering all n elements.

For the first element, we have n possible choices.
For the second element, we have n-1 possible choices.
And so on until we get the last element and we have only 1 choice.

So, the total number of thoices is n * (n-1) * (n-2) * ... * 1 which equals n!

QED

Lemma 2: For a set of n elements, there are n!/(n-m)! ways to to order m elements.

(1) There are two cases that need to be considered.

Case I: m = n
Case II: m is less than n

(2) For m = n, we know that there are n! ways to order the elements (Lemma 1)

n!/(n-n)! = n!/(0!) = n!/1 = n!. (Note: 0! is defined to equal 1)

This proves Case I.

(3) For m is less than n, we start by dividing all combinations by the first m elements.

(4) When we do this, we find that for each m sequence of elements, there are (n-m)! ways to select the remaining elements after we have selected the first m elements. (Lemma 1)

(5) Now, if each of these groups have (n-m)! elements, then we can get the total number of groups by diving n! by this value, that is: n!/(n-m)!.

QED

Lemma 3: For a set of n elements, there are n!/[m!(n-m)!] ways to select an unordered set.

(1) We can prove this using the same two cases:

Case I: m = n

Case II: m is less than n

(2) For Case I, there is only 1 way to select n items from a set of n elements.

n!/[n!(n-n)!] = n!/[n!0!] = n!/n! = 1.

(3) For case II, we take our n!/(n-m)! sets and organize them into groups where they have the same set of elements. For example, if we had 3 elements, would group {1,2,3} in the same group as {2,1,3} and {3,1,2} and {3,2,1}.

(4) For each group of m elements, there are m! ways to order them (Lemma 1)

(5) This means that the total number of groups in (3) is [n!/(n-m)!]/m! which is mathematically the same as: n!/[m!(n-m)!].

QED


Factorials are also used in the very important Binomial Theorem which I will talk about in a future blog.