When Order Matters

Pascal’s Triangle gives us a way to count combinations: groupings when the order does not matter. There are other methods of counting worthy of investigation, including occasions when order does not matter and when it does.

Sometimes order is important. With lunch lines and horse races, the order matters. If there are a limited number of specials, your spot in a lunch line could very well determine what you eat for lunch. For some, the outcome of a horse race determines whether or not they can afford a lunch.

How many ways are there for five people (or horses) to be in order in a line?

If we think beyond the lunch line for a moment, the line could be arranged by height, birthday, or shoe size. It could be arranged by the clothes being worn. Or, if this was a lunch line, it would likely be arranged by some good, old fashioned “I was here first.” These arrangements will be included in the count, and I am curious about all of the possible permutations, even the seemingly random ones.

It often takes more than a quick glance or first impression to answer the question posed above. If you read Brain Pickings, then you may be familiar with Pascal’s take on the role of intuition. Intuition is a powerful guide, especially in matters of human relationship, where logic may fail us. But, when it comes to questions of quantity, intuition alone can lead us astray. Inquiry and reasoning are powerful allies of intuition.

An exploration with friends may help guide a pathway to the answer. It may even build your intuition about permutations. Find four friends, get in line, and start rearranging. Be sure to take notes or photos. (I encourage you to at least take a few moments and imagine you and four friends rearranging your order in line.)

When your friends tire of rearranging, I suggest you indulge in the power of paper and pen. Whatever your friends’ names are, you could use names that have friendly first initials: Abel, Boris, Charles, Dylan, and Eric. That way, one small abstraction will save a lot of writing.

a b c d e
a c b d e
c a b d e
b a c d e
b c a d e
c b a d e
.
.
.

The list has only just begun. Though there are rational ways to organize the list, we still are using “brute force” in our attempt to answer the question . Let’s see if we can find a shortcut.

Instead of putting everyone in line, you and your friends could decide to focus on who gets to be first in line. Being first strikes some folks deep; emotion may disrupt logic and reason temporarily. Once you recover, a question awaits you:

How many choices do you have for who gets to be first in line?

Five

With that spot taken (and one of you now in line),
how many choices are left for the next spot?

Four

The spot after that?

Three

And, so on.

What to do with this sequence of 5, 4, 3, 2, 1? When I pose this question to a class, there are usually students who know what to do. They say we should multiply. I ask why. They say their teacher told them. (It stings a bit, though I am sure my students have un-leashed the same un-reason on subsequent teachers.) The students are right. We should multiply. But, why?

If a line only has one person in it, the line cannot be rearranged. There is just one way to put one person in order.

There are two ways to put two people in order in a line: {a, b} or {b, a}.

If we consider adding a third person c to a two-person line, there are three spots where we could put c in line: behind both a and b, in between a and b, or in front of both a and b.

a b c
a c b
c a b

But, that is not all of the possibilities for three people. For each of those arrangements, there are 2 ways a and b could be ordered. This means there are 2 + 2 + 2… OR… 3 times 2 ways to put three people in order in a line. This is where the multiplication arises. Multiplication is merely repeated addition.

a b c       b a c
a c b       b c a
c a b       c b a

The line of reasoning continues when d is added to the line. Place d at the end, and you can see the other three folks still have 6 ways to be arranged in line.

a b c d
a c b d
c a b d
b a c d
b c a d
c b a d

This is the case for each position d may hold. If I move d to second to last, there are still 6 ways to rearrange the other three folks. Our fourth friend d has four possible positions. So, there are 4 ⋅ 6 or 4 ⋅ 3 ⋅ 2 = 24 ways to put four people in order in a line.

I have been leaving 1 off, and it is time to put it back in line. If I am putting four people in order in line, I have four choices for the first placement, three for the next, and so on, including the one choice I have for the last person to get in line. Thus, there are 4 ⋅ 3 ⋅ 2 ⋅ 1 = 24 ways to put four people in order in a line. We use an exclamation mark to signify this operation of multiplying by decreasing values.

4! = 4 ⋅ 3 ⋅ 2 ⋅ 1

“4!” is read “four factorial”.

Factorial plays an important role in the Taylor Series. It also appears in its more powerful form, the gamma function, in formulations of the Riemann Zeta Function. For now, we will focus on factorial as shorthand for multiplication of decreasing values and a tool for answering problems about counting.

Back to the original question.

How many ways are there for five people to be in order in a line?

I think you already know.

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

If you are skeptical, check it out with four friends or with pen and paper. Factorial is powerful.

Before you go, just for fun, calculate how many ways seven people can be in order in line. It is pretty impressive how fast factorial grows.

Three people in a line is different than three people hanging out. You may wonder about the analog to 5 choose 3 when order matters. What if we did not want to put all five people in line? What if we wanted to pick from the 5 and only put 3 people in line? How many distinct ways could that be done? The next post will endeavor to answer the question.

How many distinct permutations of 3 objects can be made
when picking from a set of 5 objects?

Another question to consider:

How many ways are there for zero people to be in order in a line?

Sometimes, things don’t go as planned.