Permutations

Background

We know how to figure out the number of ways to organize distinct things if there are sufficient places for them (such as books on a shelf) from the Factorials entry. But what if there are more spots than there are things? Or more things than spots?

Question

An action figure collector has ten figures to put into a display case, but the case only holds eight figures. In how many ways can the collector display eight figures in the case? 

What if the collector has a display case that holds twelve figures? Now how many ways can the collector display the collection? 

Answer

 

Analysis

Remember from the Factorials entry that we can figure out the number of ways to arrange things by multiplying all the natural numbers up to the number given. For instance, if there were ten spots in the case, we could simply say that there are 10! = 3,628,800 ways to arrange the figurines. Unfortunately, we don't have 10 spots - we only have 8.

So how would this work? Well... we can put any of the 10 figures into that first display slot. And then any of the remaining 9 in the next slot. And then any of the remaining 8 in the next slot. And so on. We end up with:

10 x 9 x 8 x 7 x 6 x 5 x 4 x 3

which will take a minute to work out on a calculator, but we can do it the long way:

10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 = 1,814,400

What would be great is if we could use factorials to calculate this. And it turns out we can.

Remember that 10! = 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1

To get from 10! to what we want, we need to get rid of the 2 x 1. Notice that that is the same as 2!. And so we can get to the number we want by doing this:



Ideally, it'd be great to put this into terms that are in the question - 10 figurines and 8 spots. Well, we can:



If we call the number of figurines n and the number of spots k, we can express the general formula this way:



This is called a permutation and we can notate the calculation this way (there are several ways it can be notated - this is just one):



Another way to do it is this way:

nPk

And so our first question can be expressed as:



So what happens if the reverse happens and there are 10 figurines but 12 slots?

Well... we can't simply do what we did above - that will leave 2 display slots unaccounted for. But what we can do is to look at the problem in reverse and see that when we place the first figurine, there are 12 spots we can put it into. And then we place the next figure and there are 11 slots to choose from. And so on, so that we end up with:

12 x 11 x 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3

and this is the same thing as:



This highlights an important concept: 

Vocabulary used:

• Factorial - the calculation that allows for multiplying counting numbers up to a given number n, symbolized as n!

For more information check out these links (comment to add your favourite link):

Where might you have come from?

Fact-orials Index

Combinatorics:

• Factorials

Where might we go?

Combinatorics:

• Superpermutations