Three objects in a line

How many ways are there to arrange three objects in a line? (I’ll use numbers \(1,2,3\) to represent the objects; pretend I painted the numbers onto the respective objects.) For example, \(1,2,3\) is one way to arrange the three objects; \(1,3,2\) is another; and so on.

To be completely concrete, let’s say I have three same-sized cubes and I have three same-sized boxes to place them in; the boxes are arranged into one row and can’t be moved (they’re too heavy), but the cubes are made of balsa wood and can be moved freely. The number \(1\) is painted on one cube; \(2\) on another; and \(3\) on the third. How many ways are there to arrange the cubes into the fixed boxes?

Have a think about this, then reveal the answer and a possible way of getting the answer.

• \(1,2,3\)

• \(1,3,2\)

• \(2,1,3\)

• \(2,3,1\)

• \(3,1,2\)

• \(3,2,1\)

I’ve listed them in an order that hopefully makes it fairly easy to see that there are no more possibilities. First I listed every possible way \(1\) could come at the beginning; then every possible way \(2\) could; then every possible way \(3\) could.

If you got the answer \(6\) through some other method, that’s (probably) fine: there are many ways to think about this problem. <div><div>

How about arranging four objects in a line? (That is, four cubes into four fixed boxes.)

The total number of ways is \(24\). The complete list of possible options is:

• \(1,2,3,4\)

• \(1,2,4,3\)

• \(1,3,2,4\)

• \(1,3,4,2\)

• \(1,4,2,3\)

• \(1,4,3,2\)

• \(2,1,3,4\)

… I got bored.

How could we do this without listing all the possibilities? I promise the answer really is \(24\), but you should think about this for a bit before continuing.

How to arrange four objects

There’s an insight that makes everything much easier.

Once we’ve placed a cube into the leftmost box, all we have left to do is fit the remaining three cubes into the remaining three boxes.

We’ve already seen above that there are \(6\) ways to arrange three cubes among three boxes!

So the total number of ways of doing four cubes among four boxes is:

• \(6\) ways where the leftmost box contains cube \(1\) (and I actually listed all of those above before I got bored);

• \(6\) ways where the leftmost box contains cube \(2\);

• \(6\) ways where the leftmost box contains cube \(3\);

• \(6\) ways where the leftmost box contains cube \(4\).

That comes to \(24\) in total.

Interlude: Exercise

Can you work out how many ways there are to arrange five cubes into five fixed boxes? Take a hint from how we did four boxes above.

Then to arrange five cubes among five boxes:

• \(24\) ways where the leftmost box contains cube \(1\)

• \(24\) ways where the leftmost box contains cube \(2\)

• \(24\) ways where the leftmost box contains cube \(3\)

• \(24\) ways where the leftmost box contains cube \(4\)

• \(24\) ways where the leftmost box contains cube \(5\)

That comes to \(120\) in total. <div><div>

In general

OK, that was all well and good. But if we didn’t already know how to arrange four objects into four boxes, how could we jump straight to arranging five objects into five boxes?

Well, you might have noticed a pattern already.

• To arrange five boxes, we added the four-boxes number to itself five times; that is, we multiplied the four-boxes number by \(5\).

• To arrange four boxes, we added the three-boxes number to itself four times; that is, we multiplied the three-boxes number by \(4\).

Perhaps you can see that this will always work: to arrange \(n\) boxes, we add the \(n-1\)-boxes number to itself \(n\) times. That is, we multiply the \(n-1\)-boxes number by \(n\). Indeed, there are \(n\) possible ways to fill the leftmost box noteWe can do it with the number \(1\), or the number \(2\), or… or the number \(n\); that’s \(n\) ways. and once we’ve done that, there are “the \(n-1\)-boxes number” ways to fill the remaining \(n-1\) boxes.

But this still doesn’t help us jump straight to how to arrange five objects into five boxes. Here comes the clever bit.

Let’s write \(5!\) (with an exclamation mark) for the number that is “how many ways to arrange five objects into five boxes”. noteWe already know this number is actually \(120\). Similarly, \(4!\) is “how many ways to arrange four objects into four boxes”, and in general \(n!\) is “how many ways to arrange \(n\) objects into \(n\) boxes”.

Then the patterns we noted earlier become:

• \(5! = 5 \times 4!\)

• \(4! = 4 \times 3!\)

(Notice how much cleaner that is than “To arrange five boxes, we added the four-boxes number to itself five times; that is, we multiplied the four-boxes number by \(5\)”. This is why mathematicians use notation: to make everything easier to say.)

And the general rule is: noteBeing careful to put \(n-1\) in brackets, because otherwise it looks like \(n \times n - 1!\), which means \((n \times n)-1!\) according to the order of operations. \($n! = n \times (n-1)!\)$

OK, we have

• \(n! = n \times (n-1)!\), and

• \((n-1)! = (n-1) \times (n-2)!\), and

• \((n-2)! = (n-2) \times (n-3)!\), and so on.

So \($n! = n \times (n-1)! = n \times (n-1) \times (n-2)! = n \times (n-1) \times (n-2) \times (n-3)!\)$ and so on.

If we just keep going, we’ll eventually reach \($n \times (n-1) \times (n-2) \times \dots \times 5 \times 4 \times 3!\)$ and we already know that \(3! = 6\), which I’ll write as \(3 \times 2 \times 1\) for reasons which are about to become obvious.

So we have the following formula, which is how we define the factorial:

“$n!$” is read out loud as “$n$ factorial”, and it means “the number of ways to arrange \(n\) objects into any order”.

Edge cases

We’ve seen \(3!\), but never \(2!\) or \(1!\).

• It’s easy to see that there are two ways to arrange two objects into an order: \(1,2\) or \(2,1\). So \(2! = 2\).

• It’s also easy (if a bit weird) to see that there is just one way of arranging one object into an order: \(1\) is the only possible way. So \(1! = 1\).

• How about arranging no objects into an order? This is even weirder, but the answer is \(1\). There is a way to arrange no objects into an order: just don’t put down any objects. This is something which you should just accept without thinking about it too hard, and it almost never crops up. Anyway, \(0! = 1\).