Let's say we have two books: The Odyssey and The Iliad. We should probably have more books, but if we're only going to have two, these are a good two to have. There are two possible ways to order these books on a shelf. We can have either of these orders:
The Odyssey, The Iliad
The Iliad, The Odyssey
Now let's add a third book to the shelf. We consider adding something by John Grisham, but then we decide that now isn't the time to announce that particular guilty pleasure to the world. We go with Beowulf instead. For each of the two orders above, there are three places where we could add Beowulf. We could add it at the beginning of the shelf, in the middle, or at the end:
Beowulf, The Odyssey, The Iliad
The Odyssey, Beowulf, The Iliad
The Odyssey, The Iliad, Beowulf
Beowulf, The Iliad, The Odyssey
The Iliad, Beowulf, The Odyssey
The Iliad, The Odyssey, Beowulf
The number of ways to order three books is three times the number of ways to order two books: that is, 3 × 2 = 6.
Now let's add Hamlet to the shelf. Our right brain is loving this, but it's making things awfully tough on our left brain. How many ways are there now to order these four books? Short answer: a lot. If we have three books already on the shelf, there are four places to add Hamlet: at the beginning, between the first and second books, between the second and third books, or at the end.
Here are all the possible orders:
Hamlet, Beowulf, The Odyssey, The Iliad
Beowulf, Hamlet, The Odyssey, The Iliad
Beowulf, The Odyssey, Hamlet, The Iliad
Beowulf, The Odyssey, The Iliad, Hamlet
Hamlet, The Odyssey, Beowulf, The Iliad
The Odyssey, Hamlet, Beowulf, The Iliad
The Odyssey, Beowulf, Hamlet, The Iliad
The Odyssey, Beowulf, The Iliad, Hamlet
Hamlet, The Odyssey, The Iliad, Beowulf
The Odyssey, Hamlet, The Iliad, Beowulf
The Odyssey, The Iliad, Hamlet, Beowulf
The Odyssey, The Iliad, Beowulf, Hamlet
Hamlet, Beowulf, The Iliad, The Odyssey
Beowulf, Hamlet, The Iliad, The Odyssey
Beowulf, The Iliad, Hamlet, The Odyssey
Beowulf, The Iliad, The Odyssey, Hamlet
Hamlet, The Iliad, Beowulf, The Odyssey
The Iliad, Hamlet, Beowulf, The Odyssey
The Iliad, Beowulf, Hamlet, The Odyssey
The Iliad, Beowulf, The Odyssey, Hamlet
Hamlet, The Iliad, The Odyssey, Beowulf
The Iliad, Hamlet, The Odyssey, Beowulf
The Iliad, The Odyssey, Hamlet, Beowulf
The Iliad, The Odyssey, Beowulf, Hamlet
The number of ways to order 4 books is
4 × (number of ways to order 3 books) = 4 × 3 × 2.
As we add more and more books to the shelf, the number of ways to order the books grows bigger and bigger. Yikes. We wouldn't need to deal with this if we had a Kindle.
Anyway, if there are 5 books, the number of possible orders is
5 × 4 × 3 × 2 × 1. (Multiplying by 1 doesn't change anything).
If there are n books, the number of possible orders is
n × (n – 1) × ... × 3 × 2 × 1.
This is the product of all the numbers from n down to 1, or from 1 up to n. The fancy math name for this product is a factorial, and the fancy symbol is an exclamation mark. We like to think the symbol is an exclamation mark because this mathematical operation is so exciting!
n factorial is defined by
n! = n × (n – 1) × ... × 3 × 2 × 1.
For example, 3! = 3 × 2 × 1, and 5! = 5 × 4 × 3 × 2 × 1.
We say that 0! = 1. This sort of makes sense, because if you have no books, there's only one order in which you can put them on the shelf. True, and also a little depressing.
As you might imagine, factorials get big really fast. Just like you and your siblings in your parents' eyes. Oy, where have the years gone?
Before we go any further, here's a neat factorial trick. If we divide one factorial by another, a lot of stuff cancels out. For example,
The fancy math word for order (yes, there's a fancy math word for basically everything) is permutation. If your hairdresser messed up royally, you might go back in to complain about your perm mutation, but we're talking about something else entirely. Sorry about your hair, though. It looks like the 1980s threw up all over you.
There are two permutations of The Odyssey and The Iliad. One permutation is
The Odyssey, The Iliad
and the other permutation is
The Iliad, The Odyssey.
Here's another way to think of permutations, which may be helpful very soon. Hint, hint, wink, wink. We want to order 3 books on a shelf, so we must have 3 spaces on the shelf:
There are three choices of book for the first space:
Once we fill the first space, we have two books left to put on the shelf. There are two choices for the middle space:
There's only one choice for the last space, since there's only one book we haven't put on the shelf yet:
If we multiply these numbers together, we find the number of permutations (orders) of the books:
To make things a little more interesting, what if we have too many books for the shelf space? What if we have 4 books, but room for only 3? Aside from changing our carpenter for building us the world's smallest bookcase, what are our options?
Now there are 4 choices for the first space:
Once we fill the first space there are 3 choices left for the second space:
and two choices left for the third space:
We multiply these numbers together for our final answer. There are
ways to order 3 books when we have 4 books to choose from.
What if we have 8 books, but room for only 5? Clearly, our carpenter is still not getting it, but besides that...what do we know?
There are
possible permutations. By the handy factorial trick, we know that
If you don't believe us, work out 
to see expression on the left-hand side of the equation. If you do blindly believe us no matter what we say, then...don't forget about that $100 you owe us.
There's a formula for this stuff, of course. If we have n things to choose from and r places to fill, the number of possible permutations is:
If we have 8 books and 5 places, n = 8 and r = 5, so the formula says the number of permutations should be
which agrees with what we found earlier. Just one of the factorials of life.
The number (n – r) is the number of objects we'll have left over after we fill all available spaces. Also, n! is the number of permutations if we use all n objects; dividing by (n – r)! accounts for the spaces we can't fill because we don't have them to begin with. We should be getting them any day, though. Amazon has them on back-order.
We abbreviate "the number of permutations possible with n objects and r places" in symbols by
.
No, we're not giving National Public Radio a shoutout. Although it might not be so bad if we were, all things considered.
The n comes first, because we start with n objects. Then we permute (abbreviated by the letter P) using r places. In other words, we can use the formula we had earlier:
.
Sample Problem
What is 7P5?
Translation time: 7P5 means "the number of permutations possible with 7 objects and 5 spaces." Here n = 7 and r = 5, so
So far we've been looking at permutations without replacement or without repetition. So far we've been looking at permutations without replacement or without repetition. Wait...did we say that already?
When we put an object in a space, we have fewer objects left to choose from for the next space. We wouldn't put The Odyssey on the bookshelf twice, because we only have one copy of The Odyssey and we can't repeat it. Nor do we have a copy of the modern adaptation of the masterpiece: Coming Homer.
There are also permutations with replacement or with repetition. For these permutations, it's more like you look at an object, put it back, and look at an object (that may be the same as the first) again. Rather than choosing a new object, you may be doing a double-take. However, if you double-take a book in a bookstore, you're going to be double-charged.
We could look at The Odyssey, put it back, and then look at The Odyssey again. If we have The Odyssey and The Iliad, and we want to look at a book, put it back, and look at another book, there are four possibilities:
The Odyssey, The Odyssey
The Odyssey, The Iliad
The Iliad, The Iliad
The Iliad, The Odyssey
We had two books to choose from, we chose two, and we got 4 = 22 permutations.
To summarize, if we have n objects and we choose r of them, with repetition allowed, there are
nr possible permutations.