Permutations


Martin McBride, 2021-10-20
Tags permutations
Categories statistics probability

Imagine we have 4 cards, numbered 1 to 4, and we place them on a table, side by side:

We can arrange those same 4 cards in a different order, for example:

Each different way of ordering the cards is called a permutation of the set of cards.

Number of permutations of n objects

How many different permutations are possible? With 4 different cards there are 24 different permutations:

There is an easy way to work this out. Let's assume we start with the 4 cards and place them on the table, one by one.

For the first card, we have 4 possible cards to choose from, so there are 4 possibilities for the first card:

For the second card, one card has already gone, so we have 3 possible cards to choose from. For each of the 4 possible first cards, there are 3 possible second cards, so there are a total of 12 possibilities for the first 2 cards:

For the third card, two cards have already gone. We only have 2 cards left to choose from. For each of the 12 possible pairs of cards from the previous step, there are 2 possible third cards, so there are a total of 24 possibilities for the first 3 cards:

There is now only one card left, so we have no choice which card to use as the final card. This means that there are 24 possible permutations of the four cards, as shown in the first diagram above.

For 4 cards the number of permutations is:

$$ 4 \times 3 \times 2 \times 1 = 24 $$

This is, of course, 4! (4 factorial).

In general, the number of permutations of n unique items is n factorial:

$$ n \times (n - 1) \times ... \times 2 \times 1 = 24 $$

Number of permutations of r items selected from n items

Now let's imagine we have 5 different coloured counters - red, yellow, green, blue, and black.

We will choose two counters at random. For example, we might choose:

  • A red counter then a yellow counter.
  • A green counter then a white counter.
  • A yellow counter then a red counter.

How many permutations of 2 counters are there?

The first thing to notice here is that, because we are looking at permutations, the order is important. A red counter then a yellow counter is not the same as a yellow counter then a red counter. They are considered to be different cases.

Following the previous logic, we have 5 choices for the first counter, then 4 choices for the second counter. So the number of permutations is:

$$ 5 \times 4 = 20 $$

These, of course, are the first 2 terms of 5 factorial. That isn't surprising, based on the previous section - it is just the first two stages of calculating the total number of permutations.

In general, the number of permutations of r items from n is given by the first r terms of n factorial. However, this can be expressed more succinctly:

If we divide 5 factorial by 3 factorial, the last 3 terms cancel out, so we are left with just the first 2 terms, which is exactly what we want. This leads to the following formula for the number of permutations of r from n:

$$ \frac {n!}{(n-r)!} $$

Permutations of n items with repetition

In some situations, values are allowed to be repeated. Consider the case of a Personal Identification Number (PIN), which might be used to access a cash machine. This is often a 4 digit number. A PIN can contain repeated digits, for example 1662.

How many possible 4 digit PINs are there? This is a permutations question because the order of the digits matters (for example 1662 and 6261 are different PINs). But unlike the card example, the same digit can be repeated. So:

  • The first digit can be any number from 0 to 9, so there are 10 possibilities.
  • The second digit can also be any number from 0 to 9, so there are 10 possibilities.
  • Similar for the third and fourth digit, of course.

So the total number of permutations is:

$$ 10 \times 10 \times 10 \times 10 = 10^4 = 10000 $$

Generally, the number of permutations of r items from n when repetitions are allowed is:

$$ n ^ r $$

Permutations with repetition are often used where an item is chosen and then put back so it can be chosen again. For example, if you have a deck of ordinary playing cards:

  • You could shuffle the deck and deal 3 cards. In that case card 1, card 2, and card 3 are a simple permutation - the same card can't appear twice.
  • Alternatively you could do shuffle the deck and deal card 1 then put it back in the deck. Shuffle again and deal card 2, then but it back. Shuffle again and deal card 3. In that case, it is possible (though quite unlikely) that the same card is drawn twice or even three times, so the number of permutations must be calculated as a permutation with repetition.

Permutations and probability

We can use the permutation formulae to calculate the probability of a particular permutation occurring. We will take use the example of the 5 coloured counters, and assume that they are in a bag and pulled out at random.

Example 1 - if you take all 5 counters out, one by one, what is the probability that you will take them out in the exact order of red, yellow, green, blue, and black?

The number of permutations of the 5 counters is 5!, which is 120. So the probability of taking the counters out in one specific permutation is 1 in 120.

Example 2 - if you take out 3 counters, one by one, what is the probability that you will take them out in the exact order green, blue, yellow?

The number of permutations of 3 items from a set of 5 is 5!/(5-3)!, which is 60. So the probability of taking the counters out in one specific permutation is 1 in 60.

Example 3 - if you take out 3 counters, one by one, but replace them each time, what is the probability that you will take them out in the exact order green, blue, yellow?

In this case, we need to consider the number of permutations with repetition. The number of permutations of 3 items from a set of 5 with repetitions is 5 to the power 3, which is 125. So the probability of taking the counters out in one specific permutation is 1 in 125. Replacing the counters each time makes it less likely that we will select a specific permutation because there are more permutations to choose from.

Summary

We use permutations to different arrangements of items when the order of the items matters.

We can calculate the number of permutations of:

  • All the items of a set of n items.
  • Any r items taken from a set of n items.
  • r items from a set of n when the same item can be selected more than once.

We can use the number of permutations to calculate the probability of some particular permutation happening when items are selected at random.

Copyright (c) Axlesoft Ltd 2021