Permutations and Combinations

Permutations
When the order does matter it is called Permutation. In other words, a Permutation is an ordered Combination.

We should really call this a "Permutation Lock"!

There are basically two types of permutation:

• Repetition is Allowed: such as the lock above. It could be "00000".
• No Repetition: for example the first three people in a running race. You can't be first and second.

1. Permutations with Repetition
These are the easiest to calculate. When a thing has n different types... we have n choices each time!

For example: choosing 3 of those things, the permutations are:

n × n × n

(n multiplied 3 times)

More generally: choosing r of something that has n different types, the permutations are:

n × n × ... (r times)

So, the formula is:
n^r (where n is the number of things to choose from, and we choose r of them. Repetition is allowed,
and order matters.)

2. Permutations without Repetition
In this case, we have to reduce the number of available choices each time.

Example: what order could 16 pool balls be in?
After choosing, say, number "14" we can't choose it again.

So, our first choice has 16 possibilities, and our next choice has 15 possibilities, then 14, 13, 12, 11, ... etc. And the total permutations are:

16 × 15 × 14 × 13 × ... = 20,922,789,888,000

 But maybe we don't want to choose them all, just 3 of them, and that is then:

16 × 15 × 14 = 3,360

In other words, there are 3,360 different ways that 3 pool balls could be arranged out of 16 balls.

Without repetition, our choices get reduced each time.

So, the formula is:

Here n is the number of things to choose from, and we choose r of them, no repetitions, order matters.


Combinations
When the order doesn't matter, it is a Combination.

There are also two types of combinations (remember the order does not matter now):

• Repetition is Allowed: such as coins in your pocket (5,5,5,10,10)
• No Repetition: such as lottery numbers (2,14,15,27,30,33)

1. Combinations with Repetition
Let us say there are five flavours of ice cream: banana, chocolate, lemon, strawberry and vanilla.

We can have three scoops. How many variations will there be?

Let's use letters for the flavours: {b, c, l, s, v}. Example selections include
{c, c, c} (3 scoops of chocolate)
{b, l, v} (one each of banana, lemon and vanilla)
{b, v, v} (one of banana, two of vanilla)

So, what about our example, what is the answer?

There are 35 ways of having 3 scoops from five flavours of ice cream.

2. Combinations without Repetition
 let's say we just want to know which 3 pool balls are chosen, not the order. We already know that 3 out of 16 gave us 3,360 permutations. But many of those are the same to us now, because we don't care what order!
For example, let us say balls 1, 2 and 3 are chosen. These are the possibilities:

So, the permutations have 6 times as many possibilities.
So we adjust our permutations formula to reduce it by how many ways the objects could be in order. That formula is so important it is often just written in big parentheses like this:

where n is the number of things to choose from, and we choose r of them, no repetition, order doesn't matter.