You are often asked to count the possible arrangements of a set of distinct objects (e.g., “Four people sit down in 4 fixed chairs lined up in a row. How many different seating arrangements are possible?”) To count these arrangements, use factorials:
The number of ways of putting n distinct objects in order, if there are no restrictions, is n! (n factorial).
The term “n factorial” (n!) refers to the product of all the positive integers from n down to 1, inclusive:
n! = (n)(n − 1)(n − 2) … (3)(2)(1)
You should memorize the factorials through 6!:
| 1! = 1 | 4! = 4 × 3 × 2 × 1 = 24 | |
| 2! = 2 × 1 = 2 | 5! = 5 × 4 × 3 × 2 × 1 = 120 | |
| 3! = 3 × 2 × 1 = 6 | 6! = 6 × 5 × 4 × 3 × 2 × 1 = 720 |
The factorial expression n! counts the rearrangements of n distinct objects as a special, but very common, application of slots and labels. In this common scenario, you have n distinct objects, n slots, and n different labels for those slots. The number of objects, the number of slots, and the number of different labels are all the same.
For example, consider the case of n = 4, with 4 people and 4 fixed chairs. Let each slot represent a chair. The labels are the 4 positions of the chairs.
| _____ | _____ | _____ |
_____ |
|||
| First | Second | Third | Fourth |
Place any one of the 4 people in the first chair.
| __4__ | _____ | _____ |
_____ |
|||
| First | Second | Third | Fourth |
Now you have only 3 choices for the person in the second chair, because one of your people is already sitting in the first chair.
| __4__ | __3__ | _____ |
_____ |
|||
| First | Second | Third | Fourth |
Next, you have 2 choices for the third chair. Finally, you must put the last person in the fourth chair. You only have 1 choice, so a 1 goes in the fourth slot.
| __4__ | __3__ | __2__ |
__1__ |
|||
| First | Second | Third | Fourth |
Now multiply together all those separate choices:
| __4__ | × |
__3__ | × |
__2__ |
× |
__1__ |
= | 4! = 24 |
| First | Second | Third | Fourth |
This is why the formula works. When you put n different people or things in n distinct slots or positions, you have n choices for the first slot, n − 1 choices for the second slot, n − 2 choices for the third slot, and so on down the line until you reach the last slot, where you have just 1 choice (there's just 1 person or thing left to pick).
| _n_ | × |
_n − 1_ | × |
_n − 2_ |
× … × |
__1__ |
= | n! |
| First | Second | Third | … |
Last |
You can certainly use slots and labels the first few times to ensure that you grasp this formula. Then try to graduate to using the formula directly.
Here's another example:
In staging a house, a real estate agent must place 6 different books on a bookshelf. In how many different orders can she arrange the books?
Using the Fundamental Counting Principle, you have 6 choices for the book that goes first, 5 choices for the book that goes next, and so forth. You can draw out all 6 slots. Or you can just compute 6 factorial.
6! = 6 × 5 × 4 × 3 × 2 × 1 = 720 different orders
Note that if you don't place all the people or things into slotted positions, then you shouldn't use the plain factorial formula. That's because the factorial formula assumes that you place everyone or everything into position. So you go all the way from n down to 1.
But sometimes you only pick some of the people or things, and the rest are left out. In this case, go ahead and draw slots. Just realize you'll stop before you get all the way down to 1.
Let's study an example:
If 7 people board an airport shuttle with only 3 available seats, and these seats are all different, how many different seating arrangements are possible? (Assume that exactly 3 of the 7 will actually take the seats.)
The 3 different seats are your 3 different slots.
| _____ | _____ | _____ |
||
| First | Second | Third |
Fill in the slots with the number of choices you have at each stage. You can pick from all 7 people for the first slot. Once you've made that pick, then you only have 6 people to choose from for the second slot. Once you've made your first two picks, you only have 5 people to choose from for the third slot.
| __7__ | __6__ | __5__ |
||
| First | Second | Third |
Finally, multiply across:
| __7__ | × |
__6__ | × |
__5__ |
= | 210 possible seating arrangements |
| First | Second | Third |
In how many different ways can the 5 Olympic rings be colored Black, Red, Green, Yellow, and Blue, with one color for each ring and without changing the arrangement of the rings themselves?
In how many different ways can the letters of the word DEPOSIT be arranged (meaningful or nonsense)?