Counting permutations

As we’ve seen, a shift cipher is a simple type of substitution cipher: a way of jumbling up the letters of our alphabet. In this part of the course we’ll introduce mathematical concepts and notation that can be used to describe and investigate these substitution ciphers. This will also be important next week, when we look at the Enigma machine.

Permutations

Suppose that we have a collection of things (numbers, letters, fruit, anything really!) that we want to put into some order.

For example, suppose that we have three fruit – an apple ((a)), a banana ((b)) and a cherry ((c)) – that we want to arrange in a line. If we put the apple first, then the banana, then the cherry, we can represent this order by ((a,b,c)). An ordered list such as this is referred to as a permutation.

Counting permutations

You can easily check that there are six permutations of our set of three fruit, representing all possible ways of arranging an apple, a banana and a cherry in a line:

[(a,b,c), , (a,c,b), , (b,a,c), , (b,c,a), , (c,a,b), , (c,b,a).]

This leads to a natural question: if our set contains (n) objects (where (n) is some positive integer), how many different permutations of that set are there?

To answer this, consider what would happen if we were to add a fourth element to our set of fruit. (Let’s call it (d). Perhaps it’s a date.) Any permutation of these four fruit can be obtained by following a two-step procedure:

1. Choose a position in which to place the new element (d).
2. Once the element (d) has been put in its place, choose how to put the other three elements into the remaining three available positions.

Note that, at Step 1, we have four possible positions available to us (first, second, third or fourth in the line). In Step 2, no matter what choice we made in Step 1, we have three available positions in which to insert the three elements (a), (b) and (c). But we already know that there are exactly six ways to arrange those elements in the three available positions. For example, if in Step 1 we choose to put element (d) in position 2, we can get the following six permutations at the end of Step 2:

[(a,d,b,c),, (a,d,c,b), , (b,d,a,c), , (b,d,c,a), , (c,d,a,b), , (c,d,b,a).]

So the total number of permutations of our set with four elements is given by (4times 6 = 24), because we have four possibilities for where we put item (d), and then each of those possibilities gives us six permutations of the other items.

Repeating this argument for a set with five elements shows that the number of permutations will be (5times 24 = 120), and that for six elements the answer is (6times 120 = 720).

So the number of permutations of a set containing (n) elements is given by (n) times the number of permutations of a set containing ((n-1)) elements. This number is written (n!) (we say “(n) factorial”), and is given by the formula

[n! = n times (n-1) times (n-2) times (n-3)times dots times 3 times 2 times 1.]

Here are some values of (n!) for the next few values of (n):

You can see that these numbers grow quickly. For substitution ciphers, we’re interested in the number of ways in which we can permute the set of letters in the English alphabet. Since there are 26 elements in this set, the total number of permutations is given by

[26! = 403,291,461,126,605,635,584,000,000.]

That’s over 403 octillion!